How to construct a voronoi diagram inside a polygon?

Question

I need an algorithm that fills a 2D non-convex polygon that may have holes with points randomly, and then constructs a voronoi diagram on them. The diagram should be bounded with the polygon and the algorithm should run in O(n log n).

My idea was to fill the poly by testing random points inside the polys bounding box and taking only the points inside the poly, and than building voronoi on them, and than clipping the edges of the diagram that exit the polygon.

The problem is, testing random points and clipping the edges is O(n^2).

Can this be done in boost, or is there another small library, or anything else really?

Answer 1

I guess with "holes" you man self-intersections of a single, closed polygon.

Do a Delaunay triangulation of your polygon first:

• Calculate section points between segments; add these points, split the segments and rearrange the input so that "inside" is always on the same side of the edge when traversing the polygon's points.
• Trangulate all points in your polygon.
• Delete the triangles that lie outside your polygon. These will be the concavities and holes created by self-intersections. You can identify them by walking along your polygon and deleting all triangles that lie outside an edge. You need the connectivity of the edges, but that's a byproduct of the triangulation.

You now have the starting point for further triangulation with the Bowyer-Watson algorithm, which triangulates by successively adding points to a parent triangle. So, to add a random point, we can pick a point and update the triangulation in one go:

• Pick a random triangle, where the probability for each triangle to be picked is proportional to its area.

• Chose a random location inside that riangle by picking barycentric coordinates s in [0, 1], t in[0, 1]and withs + t < 1`. Your new point is then:

  {P} = s * ({N2} - {N1}) + t * ({N3} - {N1})
  

• Add your point and retriangulate the parent triangle and other triangles whose circumcircle contains the new point.

• The set of triangles to pick has now changed.

You now have a Delaunay triangulation, but you want a Voronoi diagram, which you can easily obtain by connecting the centres of all circumcircles of adjacent triangles. Again, the Delaunay triangulation provides you with the information on the circumcircles and on which triangles are adjacent.

You can use the Bowyer-Watson algorithm on your initial triangulation when you create a large dummy triangle that encloses all your points.

I'm not aware of any triangulation libraries for C++, but this question might get you started.