search

fesoliveira014 / voronator-rs

Delaunay triangulation and Voronoi diagram generation. Ported from Mapbox's Delaunator and d3-voronoi
MIT License
53 stars 13 forks source link

Number of cells != number of sites, number of sites != number of input points #14

Closed mmarklar closed 1 year ago

mmarklar commented 1 year ago

This might not be a bug. It might be my misunderstanding.

That being said, I expected that the number of sites to be equal to the number of input points. The behavior I see is that sites.len() is input.len() + 4. However, the number of cells == the number of input points. This causes ramifications such as the neighbor indices pointing to cells/inputs that don't exist.

From my tests it seems you can just ignore neighbors with indices > number of cells, but I wanted to raise this in case it is an actual issue.

fesoliveira014 commented 1 year ago

It has been a while since I touched the code, but from my understanding that is intended to an extent. The extra 4 points are the vertices of the enclosing bounding box for the diagram, and are added to ensure the diagram is clipped to the bounding polygon (a box by default). The reason the number of cells == number of input points is that if we didn't clip the the bounding box, they would project to infinity (i.e. would be open cells). Perhaps I could consider removing the bounding box vertices from the sites after the calculation, that is something that can studied.

I believe that the behaviour you are expecting, however, is for the resulting diagram to not be clipped. I implement this approach for the Centroid Diagram, and it should not be hard to implement an alternative without the bounding polygon for the Voronoi diagram as well. The caveat, in this case, is that we don't have the border cells, in that they don't project to infinity for the Centroid diagram. I think that for the Voronoi diagram we could have them, but I am unsure how trivial would that be.

mmarklar commented 1 year ago

Thanks for the reply, and for the library!

I see what you're talking about with the bounding box. My recommendation would be to just add to the documentation, I think the way it works currently is fine. If there is some way I can contribute that let me know. Thanks again

fesoliveira014 commented 1 year ago

No worries, thanks for reaching out! I will make a note to add it to the documentation, I can see how this can come across as an unexpected behaviour. Let me know if you have any more questions in the future :)