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!

Noticeable

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.

Swoon

Darren, I am generating the Voronoi centres with a Poisson disk sampler (devmag.org.za/2009/05/03/poisson-disk-sampling) to generate voronoi cells that are relatively equal in size. Next, I remove the points that are too close to the inside polygon to reduce artifacts. – Noticeable

I think Triangle will able to help me. If I'm right, I should generate a triangle mesh of the shape and then use that mesh, generate the dual points and build my Voronoi from there? – Noticeable

@Alex: Yup - that was what I was thinking. I think you'll still have to be careful at boundaries though. In some cases forcing a triangulation to conform to a set of constraint edges can locally sacrifice the Delaunay criteria - potentially leading to boundary triangles with external circumcentres (Voronoi vertices). If you allow sufficient boundary refinement I think it's possible to get a conforming, genuinely Delaunay triangulation, although I'd need to think about this a bit harder... – Swoon

the only problem is, it is essential that the triangles generated have to be of similar surface area (give or take a factor 2), so I won't have the luxury of doing a lot of boundary refinement. On the other hand, the inside polygon is quite simple (not many vertices), that could make it easier? – Noticeable

Answer 2

Clearly you need to generate your Voronoi diagram to the constraints of the greater polygon. Although you refer to it as a polygon, I notice that your example diagram has spline-based edges. Let's forget that for now.

What you want to do is to ensure that you start out with the containing polygon (whether generated by you or from another source) having edges of fairly equal length; a variance factor would make this look more natural. I would probably go for a variance of 10-20%.

Now that you have your containing polygon bounded by lines segments of approximately equal length, you have a basis from which to begin generating your Voronoi diagram. For each edge on your container:

• Determine the edge normal (perp line jutting inward from centre of that segment).
• Use the edge normal as a sliding scale on which to place a new Voronoi node centre. The distance away from the edge itself would be determined by what you want your average Voronoi cell "diameter" to be, if they were all taken as circles. In your example that looks like maybe 30 pixels (or whatever the equivalent in your world units would be). Again, you should apply a variance factor to this so that not every cell centre is placed equidistant from its source edge.
• Generate the Voronoi cell for your newly placed centre.
• Store your Voronoi cell source point in a list.

As you incrementally generate each point, you should begin to see that the algorithm subdivides each convex "constituent area" of your concave container in a radial fashion.

You may be wondering what the list is for. Well, obviously, you're not done yet, you've only generated a fraction of the total Voronoi tesselation you want. Once you have created these "boundary" cells of your concave space, you don't want new cells to be generated closer to the boundary than the boundary cells already are, you only want them inside that area. By maintaining a list of the boundary cell source points, you can then ensure that any further points you create are inside that area. It's a little bit like taking an internal Minkowski sum to ensure you have a buffer zone. Now you can randomise the rest of your cells in this derived concave space, to completion.

(Caveat emptor: You will have to be careful with this previous step. If any "passage" areas are too narrow, then the boundaries of this derived space will overlap, you will have a non-simple polygon, and you may find yourself placing points in the wrong places in spite of your efforts. The solution is to ensure that either your maximum placement distance from edges is never more than half of your minimum passage width... or use some other geometric means, including Minkowski summation as one possibility, to ensure you do not wind up with a degenerate derived polygon. It is quite possible that you will end with a multipolygon, i.e. fragments.)

I've not applied this method myself yet, but although there will certainly be bugs to work out, I think the general idea will get you started in the right direction.

Suannesuarez

Answer 3

Look for a paper called:

"Efficient computation of continuous skeletons" by Kirkpatrick, David G, written in 1979.

Here's the abstract:

An O(n lgn) algorithm is presented for the construction of skeletons of arbitrary n-line polygonal figures. This algorithm is based on an O(n lgn) algorithm for the construction of generalized Voronoi diagrams (our generalization replaces point sets by sets of line segments constrained to intersect only at end points). The generalized Voronoi diagram algorithm employs a linear time algorithm for the merging of two arbitrary (standard) Voronoi diagrams.

"Sets of line segments is the constrained to intersect only at end points" is the concave polygon you describe.

Contrabass