Voronoi Resources

I've put up a C++ class for generating Voronoi diagrams.  The algorithm is a modified version of Steven Fortune's sweep line algorithm. Steven very kindly put his algorithm on his website in C code. However, this merely printed information to the screen, and also suffers from severe memory leak issues. I've fixed these up, and encapsulated the code in a class, VoronoiDiagramGenerator. The two files are VoronoiDiagramGenerator.h and VoronoiDiagramGenerator.cpp.
Using the class is very simple. There are 3 public methods,

bool generateVoronoi(float *xValues, float *yValues, int numPoints, float minX, float maxX, float minY, float maxY, float minDist=0); This takes two float arrays with the occupied points in the map. Obviously enough, xValues[0] corresponds to yValues[0], and so on. numPoints specifies the size of the two arrays - the 2 arrays must of course be the same size. minX, minY, maxX, maxY specifies the bounding box around the map, so that any lines with less than 2 end points are clipped instead of extending to infinity, and are pretty self explanatory. minDist specifies the minimum distance that must be between two occupied points for an edge between them to be accepted. This is required, since the voronoi algorithm doesn't see occupied points as grid cells - just as infinitely small points. Therefore, if this is set to 0 it will place edges between adjacent occupied cells - note that this is the correct behaviour for pure voronoi algorithms. If you set it to sqrt(8) + 0.1 , then you'll be guaranteed that there will be at least one unoccupied cell between two cells since the distance between points (0,0) and (2,2) is sqrt(8).

void resetIterator()This must be called before you start iterating through the edges - it makes the internal pointer point to the head of the list.

bool getNext(float& x1, float& y1, float& x2, float& y2)This gets the next edge. The four parameters are passed by reference and are overwritten. The method returns true if an edge was returned, false if you've reached the end of the list.

A sample usage is provided in the file voronoi_main.cpp

A more recent version of the VoronoiDiagramGenerator is available as part of the MapManager open source project on Sourceforge.  As well as being able to generate voronoi diagrams, it can also generate Delaunay triangulations, identifies the points where voronoi edges meet, as well as identifying the overall edges in the voronoi graph (rather than simply all the smaller individual lines).  You can access it at http://www.sourceforge.net/projects/mapmanager

MapViewer can turn a grid, or pixel, based map into a map of vectors using some filtering techniques and the voronoi algorithm provided above.  Click HERE for the Microsoft Word explanation of the algorithm, or HERE for the Adobe Acrobat version.