Doubly-connected edge list

The title of this article is ambiguous. For the data structure consisting of half- edges, see Half-Edge Data Structure .

The doubly connected edge list ( DCEL , doubly linked list of edges ) is a data structure having a continuous planar graph representing embedded in the layer. The data structure is used in algorithmic geometry .

definition

Let G = (V, E) be a planar graph, V = the set of nodes, E = the set of edges. ${\displaystyle \{v_{1},v_{2},...,v_{n}\}}$ ${\displaystyle \{e_{1},e_{2},...,e_{m}\}}$

The DCEL stores an entry with the data ( ) for each edge of the graph : ${\displaystyle e_{i}}$ ${\displaystyle V_{1},V_{2},F_{1},F_{2},P_{1},P_{2}}$

• ${\displaystyle V_{1}}$: Start node of the edge ${\displaystyle e_{i}}$
• ${\displaystyle V_{2}}$: End node of the edge ${\displaystyle e_{i}}$
• ${\displaystyle F_{1}}$: Name of the face on the left side of the edge
• ${\displaystyle F_{2}}$: Name of the face on the right side of the edge
• ${\displaystyle P_{1}}$: Pointer to the first edge node , encountered when the edge counter-clockwise to rotate ${\displaystyle V_{1}}$ ${\displaystyle e_{i}}$ ${\displaystyle V_{1}}$
• ${\displaystyle P_{2}}$: Analogous to , this time with knots ${\displaystyle P_{1}}$ ${\displaystyle V_{2}}$

example

Sample graph

The following entries are saved for the graph in the figure:

	V1	V2	F1	F2	P1	P2
e1	v1	v2	f1	f2	e6	e2
e2	v2	v3	f1	f2	e1	e3
e3	v3	v1	f3	f2	e4	e1
e4	v3	v4	f1	f3	e2	e6
e5	v4	v5	f1	f1	e4	e5
e6	v4	v1	f1	f3	e5	e3

Applications and miscellaneous

With the help of the references to the following edges, all edges with a given end point can be determined efficiently, as well as all edges on the edge of a given surface.

The slightly differently structured half-edge data structure is also referred to as the doubly-connected edge list . DCEL is a variant of the winged-edge data structure .

If you also add the edges that you get when you turn around and clockwise , you get the quad edge data structure ( QEDS ). It can be used to traverse the edges of surfaces and edges starting from a node in both directions. Another advantage is that the QEDS of the dual graph is obtained when each edge is replaced by its respective dual edge. ${\displaystyle e_{i}}$ ${\displaystyle V_{1}}$ ${\displaystyle V_{2}}$

literature

• Franco P. Preparata, Michael Ian Shamos: Computational geometry: an introduction . New York: Springer-Verlag, c1985., ISBN 0-387-96131-3 , p. 15
• Dinesh P. Mehta, Sartaj Sahni: Handbook of data structures and applications CRC Press , 2004, ISBN 1-58488-435-5 , pp. 17-7.
• Rolf Klein: Algorithmic Geometry: Fundamentals, Methods, Applications . 2nd Edition. Springer, Berlin, Berlin [a. a.] 2005, ISBN 3-540-20956-5 , pp. 19 .

Individual evidence

1. ^ Rolf Klein: Algorithmische Geometrie , 2005, pp. 19-20 .