Benutzer:Accountalive/Halfedge Data Structure

aka DCEL verlinken von Polygonnetz#Doppelt verkettete Kantenliste .28Half Edge.29 und DCEL

Kats für Später:

Kategorie:Algorithmische Geometrie
Kategorie:Datenstruktur

Eine Halfedge Data Structure (engl. Halbkanten-Datenstruktur) oder auch Doubly-Connected Edge List (DCEL) (engl. Doppelt verkette Kantenliste) ist eine Datenstruktur für planare Graphen. Sie besteht aus Knoten, Halbkanten und Flächen. Dabei wird jede Kante durch zwei gegenläufige Halbkanten repräsentiert, denen jeweils ihr Startknoten, angrenzende Fläche und die nächste Halbkante der selben 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 Halfedge Data Structure 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).

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 ist der Umstand, dass jede Kante durch je zwei entgegengesetzt gerichtete Halbkanten repräsentiert wird, statt durch eine "volle" ungerichtete Kante. Der Vorteil dieses Vorgehens besteht unter anderem darin, dass jeder Halbkante ein Vorgänger, Nachfolger und die angrenzende Flächen eindeutiger zugeordnet werden kann. Solche Beziehungen werden in den nächsten Abschnitten genauer erläutert. Im Klammern stehen jeweils die englischen Bezeichnungen.

Halbkanten

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

Nachfolger ("next half-edge"): Die nachfolgende zur selben Fläche inzidente Kante.
Zwilling ("twin"): Die andere, gegenläufige Halbkante der selben 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 herum laufen. 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 die

Ausgehende Kante ("Incident Edge")

gespeichert^[1].

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

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/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 der selben Kante angelangt ist, berandet eine Fläche. Ein etwas komplizierterer Zyklus, der entstehent, 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].

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]