Open kaedroho opened 6 years ago
This looks reasonable to me. I expect that a lot of applications would want to use the underlying DCEL to get adjacency information, but this seems very useful for simple applications and plotting.
I think there is probably an efficient way to compute the Voronoi-cell-to-original-point mapping during construction of the DCEL, but I haven't thought it through.
Somewhat related: probably the boundary cropping shouldn't be happening in the voronoi method, and should instead be a method on VoronoiDiagram. This would mean that the DCEL needs to be extended to represent half-infinite edges. The main difficulty I see with this is that then you can't just remove points outside the boundaries before computing the Voronoi diagram, so the boundary cropping algorithm gets more complicated.
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)The
voronoi
function would be changed to return aVoronoiDiagram
instead of theDCEL
.Let me know if you have any thoughts.