imported>Crazy1880: Vorlagen-fix (Ort)

2023-11-11T20:44:09Z

Vorlagen-fix (Ort)

Neue Seite

{{Begriffsklärungshinweis|Zur aus Halbkanten bestehenden Datenstruktur siehe [[Half-Edge-Datenstruktur]].}}

Die '''Doubly-connected edge list''' ('''DCEL''', ''doppelt verkettete Kantenliste'') ist eine [[Datenstruktur]], die einen [[Zusammenhang von Graphen|zusammenhängenden]] [[Planarer Graph|planaren Graphen]] repräsentiert, der in die Ebene eingebettet ist. Die Datenstruktur wird in der [[Algorithmische Geometrie|algorithmischen Geometrie]] verwendet.

== Definition ==
Sei G = (V,E) ein planarer Graph, V = <math>\{v_1,v_2,...,v_n\}</math> die Menge der Knoten, E = <math>\{e_1,e_2,...,e_m\}</math> die Menge der Kanten.

Die ''DCEL'' speichert für jede Kante <math>e_i</math> des Graphens einen Eintrag mit den Daten (<math>V_1, V_2, F_1, F_2, P_1, P_2</math>):
* <math>V_1</math>: Startknoten der Kante <math>e_i</math>
* <math>V_2</math>: Endknoten der Kante <math>e_i</math>
* <math>F_1</math>: Name der Fläche auf der linken Seite der Kante
* <math>F_2</math>: Name der Fläche auf der rechten Seite der Kante
* <math>P_1</math>: Zeiger auf die erste Kante mit Knoten <math>V_1</math>, auf die man trifft, wenn man die Kante <math>e_i</math> gegen den Uhrzeigersinn um <math>V_1</math> dreht
* <math>P_2</math>: Analog zu <math>P_1</math>, diesmal mit Knoten <math>V_2</math>

== Beispiel ==
[[Datei:Dcel graph.svg|mini|Beispielgraph]]
Für den Graphen in der Abbildung werden folgende Einträge gespeichert:
{| class="wikitable"
!
!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 der Verweise auf die Nachfolgekanten können effizient alle Kanten mit vorgegebenen Endpunkt bestimmt werden, ebenso alle Kanten auf dem Rand einer gegebenen Fläche.

Als ''Doubly-connected edge list'' wird ebenfalls die etwas anders aufgebaute [[Half-Edge-Datenstruktur]] bezeichnet. DCEL ist eine Variante der ''[[Winged edge|winged-edge-Datenstruktur]]''.

Fügt man zusätzlich die Kanten ein, die man erhält, wenn man <math>e_i</math> im Uhrzeigersinn um <math>V_1</math> und <math>V_2</math> 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 [[Dualer Graph|dualen Graphen]] erhält, wenn jede Kante durch ihre jeweilige duale Kante ersetzt wird.<ref>Rolf Klein: ''Algorithmische Geometrie'', 2005, {{nowrap|S. 19–20}}.</ref>

== Literatur ==
* {{Literatur
|Autor=Franco P. Preparata, Michael Ian Shamos
|Titel=Computational geometry: an introduction
|Verlag=Springer-Verlag
|Ort=New York
|Datum=1985
|ISBN=0-387-96131-3
|Seiten=15
|Sprache=en}}
* {{Literatur
|Autor=Dinesh P. Mehta, Sartaj Sahni
|Titel=Handbook of data structures and applications
|Verlag=[[CRC Press]]
|Datum=2004
|ISBN=1-58488-435-5
|Seiten=17–7
|Sprache=en}}
* {{Literatur
|Autor=Rolf Klein
|Titel=Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen
|Auflage=2.
|Verlag=Springer
|Ort=Berlin [u. a.]
|Datum=2005
|ISBN=3-540-20956-5
|Seiten=19}}

== Einzelnachweise ==
<references />

[[Kategorie:Datenstruktur]]
[[Kategorie:Algorithmische Geometrie]]
[[Kategorie:Geometrische Graphentheorie]]

Doubly-connected edge list - Versionsgeschichte

imported>Crazy1880: Vorlagen-fix (Ort)