Quelltext der Seite Half-Edge-Datenstruktur

Eine '''Half-Edge-Datenstruktur''' oder auch '''Doubly-Connected Edge List''' ('''DCEL''') ([[Englische Sprache|engl.]] Doppelt verkettete Kantenliste) ist eine [[Datenstruktur]] für [[Planarer Graph|planare Graphen]]. Sie besteht aus [[Knoten (Graphentheorie)|Knoten]], Halbkanten (half-edges) und Flächen. Dabei wird jede Kante durch zwei gerichtete gegenläufige Halbkanten repräsentiert, denen jeweils ihr Startknoten, angrenzende Fläche, andere Halbkante derselben Kante und die nächste Halbkante derselben Fläche zugeordnet sind. Umgekehrt „kennen“ auch Knoten und Flächen ihre jeweiligen Nachbarn.

Diese Struktur erlaubt eine schnelle Beantwortung von Nachbarschaftsfragen und effiziente Iteration um Flächen und Knoten insbesondere auch auf [[Meshing#Unstrukturierte Gitter|unstrukturierten]] Gittern. Sie eignet sich daher besonders für unstrukturierte räumliche Datensätze, wie sie in [[Finite-Elemente-Methode]]n zum Einsatz kommen, sowie [[Computergrafik]] und [[Polygonnetz]]e im Allgemeinen.

== Aufbau ==
Eine Half-Edge-Datenstruktur besteht aus Knoten, Halbkanten und Flächen, die jeweils in einer Liste abgelegt sind.<ref name="Mark">Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: ''Computational Geometry: Algorithms and Applications''. Springer-Verlag, Berlin / Heidelberg / New York 2000, ISBN 3-540-65620-0, S. 31–32</ref> Zu jedem einzelnen dieser Elemente sind zumindest einige seiner „Nachbarn“ gespeichert, d.&nbsp;h. angrenzende ([[Inzidenz (Graphentheorie)|„inzidente“]]) Elemente. Beispielsweise ist zu jeder Halbkante ihre angrenzende Fläche gespeichert (bzw. ein [[Zeiger (Informatik)|Zeiger]] auf diese Fläche).

=== Halbkanten ===
[[Datei:Dcel-halfedge-connectivity.svg|mini|Ausschnitt einer DCEL. Exemplarisch gekennzeichnet sind eine Kante e, ihr Nachfolger next(e), ihr Vorgänger prev(e), sowie ihr Zwilling twin(e)]]

Charakteristisch und namengebend für die ''Half-Edge''-Datenstruktur ist der Umstand, dass Verbindungen zwischen zwei Punkten nicht durch eine einzelne („volle“) Kante repräsentiert werden, sondern aus genau ''zwei'' sogenannten ''Halb''kanten bestehen. Diese sind gegenläufig [[Gerichtete Kante|gerichtet]], d.&nbsp;h. der Zielknoten der einen Halbkante ist der Startknoten der anderen Halbkante und umgekehrt.
Der Vorteil dieses Vorgehens besteht unter anderem darin, dass jeder Halbkante Vorgänger, Nachfolger und angrenzende Fläche eindeutig zugeordnet werden können. Solche Beziehungen werden in den nächsten Abschnitten genauer erläutert.

[[Datei:dcel-nexts.svg|mini|Die grauen Pfeile symbolisieren die Verknüpfung der jeweiligen Halbkante zu dessen Nachfolger. Unten rechts tritt ein Spezialfall auf: Der Nachfolger der Halbkante ist gleichzeitig ihr Zwilling!]]

Jeder Halbkante werden bis zu drei weitere Kanten zugeordnet, in Klammern stehen jeweils die englischen Bezeichnungen:<ref name="Mark" />
* Nachfolger („next half-edge“): die ''nachfolgende'' zur selben Fläche inzidente Kante.
* Zwilling („twin“): Die andere, gegenläufige Halbkante derselben Kante.
* Vorgänger („previous half-edge“): Die ''vorhergehende'' zur selben Fläche inzidente Kante.

Als „nächste“ Kante wird anschaulich diejenige Kante definiert, auf die man zuerst trifft, wenn man im Uhrzeigersinn ''um den Zielknoten'' herumläuft.

Man kann es sich auch so vorstellen, dass die Halbkanten ''gegen'' den Uhrzeigersinn um die inzidente Fläche herumlaufen. Dabei ist jedoch zu beachten, dass diese Anschauung für [[Zusammenhang von Graphen|isolierte Teilgraphen]], die ihrerseits in einer anderen Fläche liegen ''(Siehe [[#Flächen|Abschnitt Flächen]])'', unintuitiv sein kann, da die äußeren Halbkanten dieses Teilgraphen scheinbar ''im'' Uhrzeigersinn verlaufen.

Weiter werden zu jeder Kante gespeichert:
* Startknoten („origin“, „source“)
* inzidente Fläche („face“): die Fläche auf der linken Seite der Halbkante.

=== Knoten ===
Da der Großteil der Konnektivitätsinformationen bereits in den Halbkanten steckt, wird zu den einzelnen Knoten lediglich eine
* Ausgehende Kante („Incident Edge“)
gespeichert.<ref name="Mark" />

Da Knoten meist Punkte in einem Raum sind, werden meist zusätzlich die Koordinaten gespeichert.

=== Flächen ===
[[Datei:Dcel-components.svg|mini|Fläche ''F'' in hellgrau und ihre äußere Komponente und die, in diesem Fall zwei, inneren Komponenten – jeweils identifiziert über eine zur Fläche inzidente Halbkante der Komponente.]]
Flächen werden durch die sie berandenden Zyklen aus Halbkanten definiert. Das können mehrere Zyklen sein, wenn in der Fläche selbst weitere [[Zusammenhang von Graphen|Komponenten]] liegen. Statt diese Zusammenhangskomponenten als separates Objekt zu behandeln, wird einfach je eine Halbkante dieser Zyklen gespeichert.<ref name="Mark" />
* Äußere Komponente („Outer Component“): Zyklus, der die Fläche nach außen hin umrandet
* Innere Komponenten („Inner Components“): Liste von Zyklen, die innerhalb der Fläche liegen.

== Kombinierte Anfragen bzw. Operationen ==

Mittels Kombination der verschiedenen Relationen können komplexe Anfragen beantwortet werden:
* Zielknoten einer Halbkante = Startknoten des Zwillings
* Nachbarfläche entlang einer Halbkante = inzidente Fläche des Zwillings der Halbkante
* Alle zu einer Fläche inzidenten Halbkanten:
** erste Halbkante = äußere Komponente der Fläche (innere Komponenten analog)
** So lange jeweils dem Nachfolger folgen, bis man wieder an der ersten Halbkante angelangt ist.
* Alle zu einem Knoten inzidenten Flächen: Siehe Beispielcode unten.

=== Beispielcode ===
Beispielcode für die Iteration über alle zu einem Knoten inzidenten Flächen. Der Algorithmus entspricht dem für die Iteration über alle inzidenten Halbkanten, mit dem Unterschied, dass jeweils noch die Fläche der aktuellen Halbkante ermittelt werden muss, mit der dann irgendetwas getan werden kann.
<syntaxhighlight lang="C">
erste_halbkante = incidentEdge(knoten);
aktuelle_halbkante = erste_halbkante;
do {
    tue_irgendwas( incidentFace(aktuelle_halbkante));
    aktuelle_halbkante = next(twin(aktuelle_halbkante));
} while( aktuelle_halbkante != erste_halbkante)
</syntaxhighlight>

''Siehe auch [[Polygonnetz#Laufzeitvergleich]] für weitere Anfrageklassen und Laufzeitvergleiche.''

== Redundanz und implizite Informationen ==

Selbst eine Datenstruktur, die nur aus Halbkanten, der Zwillings- und der Nachfolger-Relation besteht, bietet bereits einen Großteil des Funktionsumfangs! So ist eine [[Traversierung]] des Graphen bereits möglich. Auch Flächen und Knoten sind implizit bereits enthalten. Der Zyklus, der sich ergibt, wenn man von einer Halbkante aus so lange die Nachfolger entlanggeht, bis man wieder an derselben Kante angelangt ist, berandet eine Fläche. Ein etwas komplizierterer Zyklus, der entsteht, indem man abwechselnd Zwilling und Nachfolger entlanggeht, identifiziert einen Knoten.

Solche minimalistischen Lösungen sind in seltenen Fällen bereits ausreichend. Beispielsweise wenn die von den Kanten berandeten Flächen keine praktische Rolle spielen wie im Falle von Straßennetzen oder Flüssen.<ref name="Mark33">Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: ''Computational Geometry: Algorithms and Applications''. Springer-Verlag, Berlin / Heidelberg / New York 2000, ISBN 3-540-65620-0, S. 33</ref>

== Weblinks ==
* [https://www.pmp-library.org/ Polygon Mesh Processing Library]

== Einzelnachweise ==
<references />

{{SORTIERUNG:Halfedgedatenstruktur}}
[[Kategorie:Algorithmische Geometrie]]
[[Kategorie:Datenstruktur]]