petosegan / rust_voronoi Goto Github PK
View Code? Open in Web Editor NEWRust implementation of Fortune's algorithm for generating Voronoi diagrams
License: MIT License
Rust implementation of Fortune's algorithm for generating Voronoi diagrams
License: MIT License
I think it would be nice to create a VoronoiDiagram
struct which provides a place to put Voronoi-specific features (for example: make_polys) while keeping DCEL generic. We could also implement logic for linking cells to the points list and excluding the border cell here too.
Idea for API:
(note: I used the impl
syntax for brevity, actual implementation would use concrete types so it works on stable Rust)
struct VoronoiDiagram {
/// DCEL is public allowing low-level access
pub dcel: DCEL
}
impl VoronoiDiagram {
/// Returns an iterator of the cells in the diagram
pub fn cells(&self) -> impl Iterator<Item=VoronoiCell>;
/// Returns an iterator over line segments in the diagram
pub fn segments(&self) -> impl Iterator<Item=(Point, Point)>;
/// Returns an iterator over Voronoi points in the diagram (excluding border points?)
pub fn points(&self) -> impl Iterator<Item=Point>;
}
struct VoronoiCell {
/// No public attributes
}
impl VoronoiCell {
/// Returns the index of the point in the original points array that this cell was generated from
pub fn index(&self) -> usize;
/// Computes the centroid of the cell
pub fn centroid(&self) -> Point;
/// Returns an iterator of the points that border the cell
pub fn points(&self) -> impl Iterator<Item=Point>;
}
The voronoi
function would be changed to return a VoronoiDiagram
instead of the DCEL
.
Let me know if you have any thoughts.
I discovered this while writing a toy program to learn Rust, https://github.com/ctrlcctrlv/interactive-voronoi
For some inputs, strange results are returned, for example:
Creating Voronoi plot for points: [(177.0, 289.0), (195.0, 290.0), (210.0, 293.0), (224.0, 293.0)]
Drawing polygon: [(179.5, 406.5), (156.0, 600.0), (0.0, 600.0), (0.0, 0.0), (202.1, 0.0)]
Drawing polygon: [(239.7, 0.0), (217.0, 0.0), (202.1, 0.0), (0.0, 0.0), (0.0, 600.0), (156.0, 600.0), (600.0, 600.0), (600.0, 0.0)]
You can see if I add one more point, the strange polygon that covers the entire screen goes away:
Creating Voronoi plot for points: [(177.0, 289.0), (195.0, 290.0), (210.0, 293.0), (224.0, 293.0), (328.0, 409.0)]
Drawing polygon: [(217.0, 403.9), (174.6, 447.0), (179.5, 406.5), (217.0, 219.0)]
Drawing polygon: [(217.0, 219.0), (179.5, 406.5), (202.1, 0.0), (239.7, 0.0)]
Drawing polygon: [(174.6, 447.0), (217.0, 403.9), (600.0, 60.5), (600.0, 600.0), (53.0, 600.0)]
Drawing polygon: [(217.0, 403.9), (217.0, 219.0), (239.7, 0.0), (600.0, 0.0), (600.0, 60.5)]
Drawing polygon: [(179.5, 406.5), (174.6, 447.0), (53.0, 600.0), (0.0, 600.0), (0.0, 0.0), (202.1, 0.0)]
Looks like there's something wrong with the library in these cases. ๐
The bounding box is a little confusing. You provide a "box size" but it isn't clear whether the box goes from 0 to box_size or -box_size to box_size.
Instead I think we should get the user to provide a Rect
struct with four attributes: top, left, right, bottom and change the voronoi
function to accept a Rect
instead of a box size. This should make it clearer where exactly the bounds will be.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.