6.3.1 The Dual Doubly Connected Edge Lists (DCELs)



next up previous contents index
Next: Access Macros Up: 6.3 Data Structures Previous: 6.3 Data Structures

6.3.1 The Dual Doubly Connected Edge Lists (DCELs)

       

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 entriesgif 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.





Martin Stiftinger
Thu Oct 13 13:51:43 MET 1994