# Converting Voronoi Diagrams into Polygons

This topic is 3684 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, I have some code to generate a 2D Voronoi diagram from a collection of points. It uses Fortune's Plane Sweep algorithm. Rendering the diagram is pretty easy, I can just iterate through the vertex pairs and draw a line for every pair (I think the pairs are just in the order in which they were calculated, i.e. roughly starting at the top of the diagram and working down), but what I want is to be able to work out how to turn this output into convex polygons. That is, for every original point that the Voronoi diagram was generated from, I want to know the positions of every vertex that defines the Voronoi cell corresponding to that point, ordered clockwise (or anticlockwise, I suppose - it's easy to change the winding to whatever I want, so long as it's consistent for every polygon). Does anyone know a way of doing this? Does my question make sense? (if not, I can try to draw some diagrams that show what I'm trying to do)

##### Share on other sites
You know that each region in the Voronoi diagram is going to be convex, so what you can do is start from any line and generate a convex region of a particular winding. So if your first line goes from P0 to P1, and you want a CW winding, then search through all the points connected to P1 and find the one that makes the "right turn" relative to P0->P1, and call it P2. Make a line from P1 from P2. Then find the point connected to P2 that makes another "right turn" relative to P1->P2, and continue like this until you arrive at the original point. Then chose another line to start from, and start from the beginning. Eventually all your lines will be part of one of the generated convex hulls and you can stop. This algorithm is very similar to a Graham scan except we don't have to worry about invalid points.

Disclaimer: I haven't actually tested this approach, but it seems like it would work... in theory [wink]

##### Share on other sites
Thanks, Zipster - a modified Graham Scan looks like it will do the trick, and (with some reworking of my data structures) be reasonably straightforward to implement. Sorting lists of points connected to the current point at every step doesn't seem super-optimal, and I'll need to add a post-process after generating a polygon to find out which Voronoi cell I've actually calculated, but I guess at least it has the advantage of me knowing which points are connected to which beforehand, and it's better than me having no algorithm at all and being stuck.

I was wondering if there was some property of Voronoi diagrams (or their corresponding Delaunay triangulations) that would help with defining the vertices for each cell more easily, but this approach sounds like it would work perfectly well.

##### Share on other sites
If you have the Delaunay triangulation, then the number of edges connected to each vertex in the triangulation is the number of sides in the convex polygon corresponding to the Voronoi region for that vertex. From there you should be able to perform a kNN search on each vertex, where 'k' is the number of edges. Once you have that set of points it's easy to generate the convex hull.

I don't know how this compares to the previous approach, especially once you involve the kNN search, but it's some food for thought at least.

##### Share on other sites
Thanks for the help so far - I'm halfway through implementing the Graham Scan, but I'm interested in the kNN stuff too. Could you elaborate on how it could be useful? I'm not sure I follow it well enough to know how it could help me. The Wikipedia article doesn't contain much that sounds applicable, unless I'm misunderstanding it. Whilst it's useful to know that the number of edges connected to a vertex is the same as the number of edges/vertices which make up the perimeter of the corresponding Voronoi cell (I hadn't spotted that before), I'm not sure where kNN comes in. It seems to be an algorithm for finding the nearest k "things" (vertices of the Voronoi diagram, in this case) to a given point, and then classifying that point in some way based on the results of the search.

It's easy to construct Voronoi diagrams where the nearest vertices to a cell-generating point are not necessarily the vertices of the cell itself. So the centre of the test sample can't be the point that generates a Voronoi region (aka a vertex on the Delaunay triangulation - argh, I need more words to describe each of these things).

So, are you suggesting running kNN for every vertex in the Voronoi diagram and then somehow collating the results in such a way that I can build up a list of which cells each vertex is a part of?

##### Share on other sites
Quote:
 Original post by ElectroDruidIt's easy to construct Voronoi diagrams where the nearest vertices to a cell-generating point are not necessarily the vertices of the cell itself. So the centre of the test sample can't be the point that generates a Voronoi region (aka a vertex on the Delaunay triangulation - argh, I need more words to describe each of these things).

That's true. However we also know that every edge of the Voronoi region/polygon will be perpendicular to one of the edges in the Delaunay triangulation, in particular one of edges connected to the central vertex corresponding to the Voronoi region.

I believe that terminology is getting in the way here, so I'm going to attempt to reiterate a few things. You start out with a set of points you want to generate a Voronoi diagram for. These points also happen to be vertices in the Delaunay triangulation. When you generate your Voronoi diagram, you will find that these generated points lie in the middle of Delaunay triangles, and that the edges of the Voronoi regions are perpendicular to edges in the Delaunay triangulation.

So for each vertex 'V' in the Delaunay triangulation, which also happen to be the same points you started with, you find the 'k' closest points you generated for the Voronoi diagram and create a convex polygon. If not all the edges are perpendicular to an edge in the Delaunay triangulation connected to vertex 'V' (within a certain tolerance due to floating-point error of course), then you keep expanding the search. Keep edges that are perpendicular, and only try to form perpendicular edges using new points you find. Eventually you will find a convex polygon consisting of 'k' points and sides, the latter of which are all perpendicular to an edge in the triangulation. Move on to the next vertex 'V', and repeat.

Lastly, the reason you use a kNN search has to do with the fact that you're looking for the "tightest" convex hull satisfying the above perpendicularity conditions. In this case you don't care about the classifications of the points you find, just their distances (in essence you can consider all points to have the same classification).

Hopefully I didn't confuse the issue any further. These things usually go much better with pictures!

##### Share on other sites
*sound of the penny dropping*

Aha! Suddenly the significance of kNN makes sense! I'm not sure that you're correct that every point on the Voronoi diagram lies in the middle of a Delaunay triangle (I'm using this as a reference: http://www.cs.cornell.edu/Info/People/chew/Delaunay.html and there doesn't seem to be any specific relationship between the position of Voronoi points and Delaunay triangles), but it certainly does seem to be the case that each edge of a Voronoi region has a corresponsingly perpendicular edge in the Delaunay, even if the two lines don't actually intersect.

Given that I've already computed the Voronoi diagram (and the Delaunay triangulation) by the time I come to try this (so as well as already knowing all the vertices, I know about all of the connections between them), presumably there's a shortcut I can take as well. If I find the closest 'k' Voronoi points to 'V', I don't need to actually create a convex hull from the points to test all of the edges, I can iterate through the list of edges already associated with each point (with perhaps a bias towards testing edges connected to other 'k' points first) to see if the angles are perpendicular, rather than reconstructing the hull. Would that work, or do I run the risk of generating false positives there?

As an aside, is it reasonable to assume that if the number of 'V' points is sufficiently low (very likely to be less than 50), it's reasonable to run a naive algorithm just to compute the (squared) distances of all of the other 'V' points and just do a quicksort for each polygon I want to calculate, rather than building something more sophisticated?

##### Share on other sites
You're correct, my assumptions about the relative positions of the points and edges was incorrect. My apologies if you were mislead [embarrass]

However, for some reason we've been ignoring the key relationship between the Voronoi tessellation and the Delaunay triangulation -- they are dual graphs! For every Delaunay triangle, there is a Voronoi point with three edges that corresponds to the triangle. These three edges are perpendicular to all sides of the Delaunay triangle!

So for every point in the Delaunay triangulation, find all the triangles that share this point. Then find all the Voronoi points corresponding to these triangles. All the points your find form your Voronoi region! Use the duality property to aid in your search. Let's say you find the Voronoi point 'V0' corresponding to a Delaunay triangle 'T0', and this triangle is adjacent to triangle 'T1' through edge 'E'. To get the Voronoi point 'V1' for triangle 'T1', move along the edge connected to 'V1' that's perpendicular to 'E'. Using this technique, given a winding of Delaunay triangles sharing a common vertex, you only have to search for the first Voronoi point, and then just walk the points as you walk the adjacent triangles in the winding. You may not even have to perform any searches beyond the initial ones either. All you have to do is walk both graphs simultaneously, and using something a flood-fill you can cover all the Delaunay vertices, and hence generate all the Voronoi regions.

Sorry to just drop everything we've been discussing, but looking at that app you linked gave me an epiphany [smile]

##### Share on other sites
That is... Breathtakingly elegant (and also annoyingly obvious once you spot it)...

I need to work out how best to arrange my data to walk through this stuff quickly, and I need to work out some special cases for the "open" cells around the edges (my code needs the whole thing bounded and closed off, so I've fudged in edge connections all around the edge of the Voronoi diagram, which won't have any meaningful parallel in Delaunay triangulation), but I think this is definitely the best approach for solving this. Thanks again!

##### Share on other sites
The way I approached this (for generating convex polygons for regions on a map) was quite simple. Basically it goes like this:

For each point P, create a convex polygon the size of your bounds (e.g. a square that contains the whole "map"). Iterate through all other points (P') and clip the current polygon with a line that's perpendicular to P-P' and goes through the midpoint. The end result should be what you want.

During this process it's helpful to store the "other" point for each side of the polygon created by the clip. This will provide you with the "neighbor" information between the cells (ie. construct the Delaunay graph).

1. 1
Rutin
41
2. 2
3. 3
4. 4
5. 5

• 16
• 18
• 12
• 14
• 9
• ### Forum Statistics

• Total Topics
633362
• Total Posts
3011527
• ### Who's Online (See full list)

There are no registered users currently online

×