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!
After trying to use this thread as a source for answers to my own similar question, I found that Fortune's algorithm — likely because it is the most popular & therefore most documented — was the easiest to understand.
The Wikipedia article on Fortune's algorithm keeps fresh links to source code in C, C#, and Javascript. All of them were top-notch and came with beautiful examples.
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?
The Voronoi diagram is just the dual graph of the Delaunay triangulation.
Note that the exact code depends on the internal representation you're using for the two diagrams.
I'm pretty sure that 'triangle' http://www.cs.cmu.edu/~quake/triangle.html can generate the voronoi
If optimal speed is not a consideration, the following psuedo code will generate a Voronoi diagram the hard way:
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.