Calculate Voronoi around polygon

Question

I need to generate a Voronoi diagram around a concave (non-convex) inside polygon. I have looked for methods online, but I haven't been able to figure out how to do this. Basically, I generate the convex hull of the points, calculate the dual points and build an edge network between these points. However, when meeting the edges of the inside polygon, it has to look like the edge of the shape, just like the convex hull. So, by doing this and clipping all the edges at the borders, I should end up with a Voronoi diagram that has nice edges to the borders of the inside polygon and no cells that are on both sides of the inside polygon.

Let me give you an example:

The problem with this is that the cells cross the inside polygon edges and there is no visual relation between the cell structure and the polygon shape.

Does anybody know how to approach this problem? Is there some algorithm that already does this or gets close to what I'm trying to achieve?

Thank you so much for any kind of input!

Answer 1

You might be able to build a conforming Delaunay triangulation (i.e. a triangulation that includes the polygon edges as constraints) and then form the Voronoi diagram as the dual. A conforming triangulation will ensure that no edge in the triangulation intersects with a constraint edge - all constraint edges will be an edge in the triangulation.

Have a look at the Triangle package here, as a reference for this type of approach. In my experience it's a fast and robust library, although it's written in c not java.

I'm not sure I understand at this stage how the points (the Voronoi centres) are generated in your diagram. If you're actually looking to do mesh generation in a polygonal domain, then there may be other approaches to consider, although the Triangle package supports (conforming) Delaunay refinement mesh generation.

EDIT: It looks like you can also directly form the Voronoi diagram for general line segments, check out the VRONI library, here. Addressing your comment - I'm not sure that you can always expect to have a uniform Voronoi diagram that also conforms to a general polygonal boundary. I would expect that the shape of the polygonal boundary would impose a maximum dimension on the boundary Voronoi cells.

Hope this helps.