Doubly connected edge list

This data structure provides efficient manipulation of the topological information associated with the objects in question (vertices, edges, faces).

It is used in many algorithms of computational geometry to handle polygonal subdivisions of the plane, commonly called planar straight-line graphs (PSLG).

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[1] for representations of 3D convex polyhedra.

If the vertices or faces do not hold any interesting information, there is no need to store them, thus saving space and reducing the data structure's complexity.

Each half-edge has exactly one previous half-edge, next half-edge and twin.