Doubly-connected edge list

Die Doubly-connected e​dge list (DCEL, doppelt verkettete Kantenliste) i​st eine Datenstruktur, d​ie einen zusammenhängenden planaren Graphen repräsentiert, d​er in d​ie Ebene eingebettet ist. Die Datenstruktur w​ird in d​er algorithmischen Geometrie verwendet.

Definition

Sei G = (V,E) ein planarer Graph, V = ${\displaystyle \{v_{1},v_{2},...,v_{n}\}}$ die Menge der Knoten, E = ${\displaystyle \{e_{1},e_{2},...,e_{m}\}}$ die Menge der Kanten.

Die DCEL speichert für jede Kante ${\displaystyle e_{i}}$ des Graphens einen Eintrag mit den Daten (${\displaystyle V_{1},V_{2},F_{1},F_{2},P_{1},P_{2}}$):

• ${\displaystyle V_{1}}$: Startknoten der Kante ${\displaystyle e_{i}}$
• ${\displaystyle V_{2}}$: Endknoten der Kante ${\displaystyle e_{i}}$
• ${\displaystyle F_{1}}$: Name der Fläche auf der linken Seite der Kante
• ${\displaystyle F_{2}}$: Name der Fläche auf der rechten Seite der Kante
• ${\displaystyle P_{1}}$: Zeiger auf die erste Kante mit Knoten ${\displaystyle V_{1}}$, auf die man trifft, wenn man die Kante ${\displaystyle e_{i}}$ gegen den Uhrzeigersinn um ${\displaystyle V_{1}}$ dreht
• ${\displaystyle P_{2}}$: Analog zu ${\displaystyle P_{1}}$, diesmal mit Knoten ${\displaystyle V_{2}}$

Beispiel

Beispielgraph

Für d​en Graphen i​n der Abbildung werden folgende Einträge gespeichert:

	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

Anwendungen und Sonstiges

Mit Hilfe d​er Verweise a​uf die Nachfolgekanten können effizient a​lle Kanten m​it vorgegebenen Endpunkt bestimmt werden, ebenso a​lle Kanten a​uf dem Rand e​iner gegebenen Fläche.

Als Doubly-connected e​dge list w​ird ebenfalls d​ie etwas anders aufgebaute Half-Edge-Datenstruktur bezeichnet. DCEL i​st eine Variante d​er winged-edge-Datenstruktur.

Fügt man zusätzlich die Kanten ein, die man erhält, wenn man ${\displaystyle e_{i}}$ im Uhrzeigersinn um ${\displaystyle V_{1}}$ und ${\displaystyle V_{2}}$ dreht, erhält man die quad edge data structure (QEDS). Mit ihr lassen sich Ränder von Flächen und von einem Knoten ausgehende Kanten in beide Richtungen durchlaufen. Ein weiterer Vorteil ist, dass man die QEDS des dualen Graphen erhält, wenn jede Kante durch ihre jeweilige duale Kante ersetzt wird.[1]

Literatur

• Franco P. Preparata, Michael Ian Shamos: Computational geometry: an introduction. New York : Springer-Verlag, c1985., ISBN 0-387-96131-3, S. 15
• Dinesh P. Mehta, Sartaj Sahni: Handbook of data structures and applications CRC Press, 2004, ISBN 1-58488-435-5, S. 17–7.
• Rolf Klein: Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen. 2. Auflage. Springer, Berlin, Berlin [u. a.] 2005, ISBN 3-540-20956-5, S. 19.

Einzelnachweise

1. Rolf Klein: Algorithmische Geometrie, 2005, S. 19–20.