Delaunay Triangulation and Voronoi Diagrams
This package generates Delaunay triangulations and Voronoi diagrams of 2-dimensional point sets.
- A subdivision of the plane by edges to form a Delaunay triangulation.
- A panel that can visualize a Delaunay triangulation at any point in the process.
- A viewer that will display the that can show a visualization of the triangulation.
- An interface for classes that can display a visualization of the process as it occurs.
- A single edge in a QuadEdge data structure.
- An edge in the Voronoi graph.
- A hash table to store half-edges.
- A QuadEdge, consisting of four edges linked appropriately. The edges form a cyclical,
doubly-linked list, and each edge has a link to the next edge in a counterclockwise edge list
around its origin vertex.
- A site or vertex in the Voronoi diagram.
- A vertex in a Delaunay triangulation.
- An intermediate data structure used in building the edges between regions in a Voronoi diagram.
- A class to compute Voronoi diagrams.
This work was adapted from other authors, and as such I cannot make statements about it. I plan to create my own implementation of Delaunay triangulation and Voronoi diagram generation, but needed a fast implementation. Since some of the other code on this web site uses this module, I include it here for completeness.