Doubly connected edge list

<h2 id="data-structure">Data structure</h2>

<p>DCEL is more than just a <a href="/facts/Doubly_linked_list/vFpCq7q2">doubly linked list</a> of edges. In the general case, a DCEL contains a record for each edge, <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertex</a> and <a href="/facts/Face_(geometry)/T2E6BTU4">face</a> 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" (which are represented by the two edges with opposite directions, between two vertices, in the picture on the right). Each half-edge is "associated" with a single face and thus has a pointer to that face. <i>All</i> 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 (i.e. the "internal" half-edges) 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 (the destination vertex can be obtained by querying the origin of its twin, or of the next half-edge).
</p><p>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 (if the face is unbounded then pointer is null). 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 to store them, thus saving space and reducing the data structure's complexity.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Quad-edge_data_structure/pSvBPGQo">Quad-edge data structure</a></li>
<li><a href="/facts/Doubly_linked_face_list/cJbXA9Cx">Doubly linked face list</a></li>
<li><a href="/facts/Winged_edge/okvcBggu">Winged edge</a></li>
<li><a href="/facts/Combinatorial_map/TlNW46sg">Combinatorial map</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Muller, D. E.; Preparata, F. P. (1978). "Finding the Intersection of Two Convex Polyhedra". Theoretical Computer Science. 7 (2): 217–236. doi:10.1016/0304-3975(78)90051-8. hdl:2142/74093. <a href="https://doi.org/10.1016%2F0304-3975%2878%2990051-8" target="_blank">https://doi.org/10.1016%2F0304-3975%2878%2990051-8</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>de Berg, Mark; Cheong, Otfried; van Kreveld, Marc; Overmars, Mark (2008). Computational Geometry, Algorithms and Applications (3rd ed.). Springer. pp. 29–33. ISBN 978-3-540-77973-5. <a href="978-3-540-77973-5" target="_blank">978-3-540-77973-5</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

Doubly connected edge list open-in-new

Doubly connected edge list