search

andreesteve / voronoice

A nice and fast way to construct 2D Voronoi Diagrams
MIT License
34 stars 9 forks source link

Some way to have circular bounds? #7

Open iMplode-nZ opened 3 years ago

iMplode-nZ commented 3 years ago

I would like to have a circular boundary for my voronoi diagram, or at least a close approximation using polygons. This could be done by replacing the bounding-box with a Polygon type.

andreesteve commented 3 years ago

This sounds very interesting! In principle, as you pointed out, the bounding box would have to be replaced with a more generic construct. The code does have some assumptions right now that the constraint is a rectangle so the clipping logic would have to be changed as well. I wonder if all assumptions currently made for clipping on a box would apply to a generic convex polygon.

iMplode-nZ commented 3 years ago

Perhaps just assume that the points are generated within the polygon or bounding box but clip all the lines to it?

SPuntte commented 2 years ago

I realize this issue is over a year old, but what I've been doing in my fork recently seems closely related. I can't honestly claim to understand all the details of the diagram generation logic in this library yet but so far it certainly seems to generalize pretty straightforwardly to arbitrary convex polygons.

@andreesteve, maybe a separate issue would be appropriate if you're interested in collaborating on this?

andreesteve commented 2 years ago

Hi @SPuntte - thanks for looking into this ! I believe indeed generalizing the bounding box into a convex polygon and the clipping algorithm into Sutherland–Hodgman is a good way to go, and would be a great addition to the library.

I think such a change would be welcomed to the library. Especially if we can bring the generalization with similar benchmark results when the polygon is a bounding box.

We can use this issue or file a new one. No preference from my side. If we file a new one, I'd duplicate this issue against that. Let me know your thoughts.