search

JCash / voronoi

A C implementation for creating 2D voronoi diagrams
MIT License
632 stars 94 forks source link

Support for Polygons with islands #62

Closed esuig closed 1 year ago

esuig commented 2 years ago

Hello,

Great work!

I would like to calculate the radius of the maximum inscribed circle in a polygon with islands and I think using the Voronoi diagram could be the best approach. Something like the situation represented in the following image, were the outher boundary (black) and the islands (red) are the input, while what I want to achieve is the maximum inscribed circle (purple):

inscr_circle

Is it possible to achieve something similar with your library? If yes, is it possble to have an example of use of your library to face the problem I explained?

JCash commented 2 years ago

Hi @esuig !

Looking at this answer, it seems a Voronoi diagram could solve this.

To get the nodes, iterate over the edges for the interesting sites, and get a position that is shared amongst the interesting sites. That position should represent the center of a circle, and the size is the distance to one of those sites.

Ofc, finding the set of sites to investigate, might be the tricky part.

Also, the "outer boundary" is currently the bounding box of the sites, so you'd have to take that into account as well. E.g. if you don't find more than 2 site candidates.

esuig commented 2 years ago

Thank you for your detailked answer and sorry for my delay wriing back to you.

I've started trying the approach you suggested. I'd like to ask you a question: what do you think would be the best point spacing on the sides of the polygons (both on outer boundary and holes). I mean, if I use just the extremes of each side of the polygon I will not get what I need. I would expect something like this:

https://stackoverflow.com/questions/69237154/how-do-you-get-the-medial-axis-of-a-multipolygon-using-cgal

but I get something totally different (this is me, I'm ont understanding something in Voronoi diagrams, it is not your code the cause of course!). Maybe I can consider the segments of the boundaries in some way?

If you need any other detail I can provide you.

Many thanks!