Half-Edge-Datenstruktur

Eine Half-Edge-Datenstruktur oder auch Doubly-Connected Edge List (DCEL) (engl. Doppelt verkettete Kantenliste) ist eine Datenstruktur für planare Graphen. Sie besteht aus 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 unstrukturierten Gittern. Sie eignet sich daher besonders für unstrukturierte räumliche Datensätze, wie sie in Finite-Elemente-Methoden zum Einsatz kommen, sowie Computergrafik und Polygonnetze im Allgemeinen.

Aufbau

Eine Half-Edge-Datenstruktur besteht aus Knoten, Halbkanten und Flächen, die jeweils in einer Liste abgelegt sind.^[1] Zu jedem einzelnen dieser Elemente sind zumindest einige seiner „Nachbarn“ gespeichert, d. h. angrenzende („inzidente“) Elemente. Beispielsweise ist zu jeder Halbkante ihre angrenzende Fläche gespeichert (bzw. ein Zeiger auf diese Fläche).

Halbkanten

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 Halbkanten bestehen. Diese sind gegenläufig gerichtet, d. 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.

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:^[1]

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 isolierte Teilgraphen, die ihrerseits in einer anderen Fläche liegen (Siehe 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.^[1]

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

Flächen

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 Komponenten liegen. Statt diese Zusammenhangskomponenten als separates Objekt zu behandeln, wird einfach je eine Halbkante dieser Zyklen gespeichert.^[1]

Ä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.

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)

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.^[2]

Weblinks

Polygon Mesh Processing Library

Einzelnachweise

↑ ^a ^b ^c ^d 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
↑ 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

[Mark-1] 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

[Mark33-2] 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

[1]

[2]