The doubly connectededge list, also known as half-edge data structure, is a data structure to represent an embedding of a planar graph in the plane, and polytopes in 3D. This data structure provides efficient manipulation of the topological information associated with the objects in question. It is used in many algorithms of computational geometry to handle polygonal subdivisions of the plane, commonly called planar straight-line graphs. For example, a Voronoi diagram is commonly represented by a DCEL inside a bounding box. This data structure was originally suggested by Muller and Preparata for representations of 3Dconvex polyhedra. Later, a somewhat different data structure was suggested, but the name "DCEL" was retained. For simplicity, only connected graphs are considered, however the DCEL structure may be extended to handle disconnected graphs as well by introducing dummy edges between disconnected components.
Data structure
DCEL is more than just a doubly linked list of edges. In the general case, a DCEL contains a record for each edge, vertex and face of the subdivision. Each record may contain additional information, for example, a face may contain the name of the area. Each edge usually bounds two faces and it is, therefore, convenient to regard each edge as two "half-edges". Each half-edge is "associated" with a single face and thus has a pointer to that face. All half-edges associated with a face are clockwise or counter-clockwise. For example, in the picture on the right, all half-edges associated with the middle face are counter-clockwise. A half-edge has a pointer to the next half-edge and previous half-edge of the same face. To reach the other face, we can go to the twin of the half-edge and then traverse the other face. Each half-edge also has a pointer to its origin vertex. Each vertex contains the coordinates of the vertex and also stores a pointer to an arbitrary edge that has the vertex as its origin. Each face stores a pointer to some half-edge of its outer boundary. It also has a list of half-edges, one for each hole that may be incident within the face. If the vertices or faces do not hold any interesting information, there is no need tostore them, thus saving space and reducing the data structure's complexity.
