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]

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.

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!

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]

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).