VORONOI maintains two doubly connected edge lists, one for the Voronoi graph and one for the Delaunay graph. Every node in these graphs is represented by a node_t data structure which is the same for both Delaunay and Voronoi nodes. Every edge in the Voronoi and Delaunay graphs is represented by an edge_t data structure which is again the same for both Voronoi and Delaunay edges and points to two structures of type node_t.
Figure 6.6: The Delaunay graph (solid lines) and Voronoi graph
(dotted lines) are stored in two Dual Doubly Connected Edge Lists.
In the basic DCEL structure, edges are oriented
from their first node to their second
node. Every edge contains 4 entries
to clockwise and
counterclockwise adjacent edges.
The two doubly connected edge lists of the Voronoi and Delaunay graphs
are cross-linked to each other according to the duality relationships
depicted in Table 6.2.