|
Half-Edge-DatenstrukturEine 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. AufbauEine 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 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.  Jeder Halbkante werden bis zu drei weitere Kanten zugeordnet, in Klammern stehen jeweils die englischen Bezeichnungen:[1]
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:
KnotenDa der Großteil der Konnektivitätsinformationen bereits in den Halbkanten steckt, wird zu den einzelnen Knoten lediglich eine
gespeichert.[1] Da Knoten meist Punkte in einem Raum sind, werden meist zusätzlich die Koordinaten gespeichert. Flächen 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]
Kombinierte Anfragen bzw. OperationenMittels Kombination der verschiedenen Relationen können komplexe Anfragen beantwortet werden:
BeispielcodeBeispielcode 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 InformationenSelbst 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] WeblinksEinzelnachweise
|
Portal di Ensiklopedia Dunia
