1 |
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,
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 |

2 |
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
Skeleton Retraction. |

6 | Paper I wrote on how to convert grid maps to vector maps in Word or in Adobe PDF |