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
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 corresponds to yValues, 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.
|3||Stephan Fortune (upon whose sweep-line algorithm MapViewer's voronoi algorithm is based) wrote some documents detailing the algorithm. Click HERE for the first document, and HERE for the second.|
|4||Click HERE for a PowerPoint slide presentation on the Sweep-Line Voronoi algorithm.|
|5||Click HERE for
a paper on the pruning of Voronoi diagrams using a method called
|6||Paper I wrote on how to convert grid maps to vector maps in Word or in Adobe PDF|