petosegan / rust_voronoi Goto Github PK

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.