Sign in to follow this  
ElectroDruid

Converting Voronoi Diagrams into Polygons

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by ElectroDruid
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).

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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).

Share this post


Link to post
Share on other sites
hehe, every time I sit down and get most of the way through implementing a suggestion from this thread, another, more elegant solution comes along :)

Fingers_, what you described is disturbingly close to encompassing the solution to the whole problem I was trying to solve in the first place (of which polygonising a Voronoi diagram was one part). The more I think about it, the more I wonder if I've made a lot more work for myself than is necessary. My only question is one of efficiency - Presumably with your approach you end up calculating a lot of clip planes, only to find that applying those clip planes makes no difference to the polygon (since a lot of the clip planes are outside of the polygon)?

Is there some optimisation you perform? Would it work if you sorted all of the points by distance, and applied clips starting with the closest, and stopped when you found a point far enough away that trying to apply a clip makes no difference?

Share this post


Link to post
Share on other sites
In my case, I was doing this on a starmap in "Weird Worlds: Return to Infinite Space". The number of stars tops out around 60, and with such a low number of points the polygonizing process takes a negligible amount of time even without any particular optimizations - rejecting a clipping plane is pretty quick. It would probably run in real-time if necessary but I didn't have a need for that. YMMV of course.

The sorting by distance may not work like that because you also have to take direction into account. E.g. the nearest neighbors may all be on one side, while the other side would connect to a very distant point.

If you have a large data set and use a spatial partitioning scheme, you could possibly somehow reject regions of the "map" with multiple points at once rather than testing individual points.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this