How do I derive a Voronoi diagram given its point set and its Delaunay triangulation?

Question

I'm working on a game where I create a random map of provinces (a la Risk or Diplomacy). To create that map, I'm first generating a series of semi-random points, then figuring the Delaunay triangulations of those points.

With that done, I am now looking to create a Voronoi diagram of the points to serve as a starting point for the province borders. My data at this point (no pun intended) consists of the original series of points and a collection of the Delaunay triangles.

I've seen a number of ways to do this on the web, but most of them are tied up with how the Delaunay was derived. I'd love to find something that doesn't need to be integrated to the Delaunay, but can work based off the data alone. Failing that, I'm looking for something comprehensible to a relative geometry newbie, as opposed to optimal speed. Thanks!

Answer 1

I'm pretty sure that 'triangle' http://www.cs.cmu.edu/~quake/triangle.html can generate the voronoi

Answer 2

The Voronoi diagram is just the dual of the Delaunay triangulation. So, the edges of the Voronoi diagram are along the perpendicular bisectors of the edges of the Delaunay triangulation, so compute those lines. Then, compute the vertices of the Voronoi diagram by finding the intersections of adjacent edges. Finally, the edges are then the subsets of the lines you computed which lie between the corresponding vertices. Note that the exact code depends on the internal representation you're using for the two diagrams.

Answer 3

Well the reason why things are tied together is because the Delaunay triangulation and the Voronoi diagram are dual structures. Meaning it is a no brainer to go from voronoi to delaunay and vice versa.

Meaning that if you have a voronoi diagram, all you need to do is connect the points who share an edge and you'll have the delaunay triangulation (and vice versa).

Answer 4

If optimal speed is not a consideration, the following psuedo code will generate a Voronoi diagram the hard way:

for yloop = 0 to height-1
  for xloop = 0 to width-1

    // Generate maximal value
    closest_distance = width * height

    for point = 0 to number_of_points-1
      // calls function to calc distance
      point_distance = distance(point, xloop, yloop)

      if point_distance < closest_distance
        closest_point = point
      end if
    next

  // place result in array of point types
  points[xloop, yloop] = point

  next
next

Assuming you have a 'point' class or structure, if you assign them random colours, then you'll see the familiar voronoi pattern when you display the output.

Answer 5

Each of your Delaunay triangles contains a single point of the Voronoi diagram.

You can compute this point by finding the intersection of the three perpendicular bisectors for each triangle.

Your Voronoi diagram will connect this set of points, each with it's nearest three neighbors. (each neighbor shares a side of the Delaunay triangle)

How do you plan on approaching the edge cases?

Answer 6

(months later) Do you really want Voronoi, or just a pretty near point, "something comprehensible" ?
If the latter, ANN, Approximate Nearest Neighor, methods are waaaay simpler than Delaunay / Voronoi.
Take a look at Kd tree.
Also the source for matplotlib/delaunay has a nice Python wrapper with test funcs ! and plot helpers !

(Fwiw, to quantify "simpler", triangle is 16k lines of C (including a 1000-line help), ANN 1.1.1 4k lines C++ --
both I think high quality code and 3-sigma doc.)