Polygonnetz

Bei der Knotenliste werden die Punkte in einer separaten Punktliste abgelegt. Eine Fläche wird dann als eine Liste von Zeigern auf die Punkte in dieser Liste definiert. Dadurch wird eine Trennung zwischen der Geometrie (den Koordinaten der Knoten) und der Topologie (welche Knoten verbinden welche Kanten, welche Kanten begrenzen welche Flächen) realisiert.

Die Nachteile der Knotenliste werden bei der Kantenliste dadurch umgangen, dass alle Kanten in einer separaten Liste gespeichert werden. Facetten werden hier als Zeiger auf die Kantenliste definiert. Neben dem Anfangs- und Endpunkt werden auch die maximal zwei zugehörigen Facetten für jede Kante abgelegt. Die Reihenfolge der Angabe der Eckpunkte für Kanten legt eine Orientierung fest und bestimmt bei Facetten, wo innen und wo außen ist.

Generell gilt für Knoten- und Kantenlisten, dass die Suche ausgehend von einer Facette nach untergeordneten Objekten wie Kanten und Knoten sehr effizient durchführbar ist. In umgekehrter Richtung verhält es sich jedoch gegenteilig. So ist z. B. die Suche nach allen Facetten, welche eine bestimmte Ecke enthalten, immer noch nur durch eine erschöpfende Suche möglich.

Eine Datenstruktur, mit deren Hilfe sehr viele Abfragen effizient bearbeitet werden können, ist die Winged-Edge-Darstellung nach Baumgart. Zusätzlich zu den Informationen der Kantenliste werden hier noch Zeiger auf die Kanten abgelegt, die von Anfangs- und Endpunkt der aktuellen Kante abgehen. Aufgrund der Orientierung wird jede Kante einmal positiv (im Uhrzeigersinn) und einmal negativ (gegen den Uhrzeigersinn) durchlaufen.

Mit der Winged-Edge-Datenstruktur ist es möglich, in konstanter Zeit abzufragen, welche Knoten oder Facetten zu einer gegebenen Kante gehören. Hat eine Facette k Kanten, können in linearer Zeit diese Kanten nacheinander abgesucht werden (nur bei polygonalen Netzen ohne Änderung der Durchlaufrichtung eines Polygons). Andere Anfragen, insbesondere solche ausgehend von einer Ecke, die nach den Kanten oder Facetten, in denen diese Ecke enthalten ist, suchen, sind deutlich langsamer.

Die Half-Edge-Datenstruktur ist ein wenig ausgereifter als die Winged-Edge-Liste. Sie erlaubt, die meisten in der folgenden Tabelle aufgeführten Operationen in konstanter Zeit auszuführen, d. h. konstanter Zeit pro gesammelte Information. Wenn man z. B. alle zu einem Eckpunkt benachbarten Kanten herausfinden will, ist die Operation linear bezüglich der Anzahl der benachbarten Kanten aber konstant in der Zeit pro Kante. Half Edge funktioniert nur mit zweidimensionaler Mannigfaltigkeit, d. h. jede Kante ist von genau zwei Facetten (zu jeder Halbkante gibt es eine entgegengesetzte Halbkante) umgeben, d. h. T-Verbindungen, innere Polygone und Brüche sind nicht erlaubt.

Bei der Half-Edge-Struktur werden nicht Kanten, sondern Halbkanten abgelegt. Halbkanten sind gerichtet und zwei zusammengehörende Halbkanten (Paar) bilden eine Kante und zeigen in die entgegengesetzte Richtung.

Eine weitere Datenstruktur ist die Doubly-connected edge list (DCEL).

Folgende Tabelle zeigt einen Vergleich der asymptotischen Laufzeit in Abhängigkeit von den vorhandenen Elementen Knoten, Kanten und Flächen. Es gibt neun mögliche Abfragen auf die Struktur, nämlich „welche Ecke, Kante oder Fläche gehört zu welcher Ecke Kante oder Fläche“. Alle Abfragen bis auf diejenige nach den benachbarten Ecken einer gegebenen Ecke werden in der Tabelle aufgeführt. Der Vergleich zeigt, wie unterschiedlich gut die Datenstrukturen die Anfrageklassen bearbeiten.

Suchanfrage (gegeben → gesucht)	Knotenliste	Kantenliste	Winged Edge	Half Edge
Kante → Eckpunkte	N/A	${\displaystyle {\mathcal {O}}(1)}$	${\displaystyle {\mathcal {O}}(1)}$	${\displaystyle {\mathcal {O}}(1)}$
Kante → Facetten	N/A	${\displaystyle {\mathcal {O}}(1)}$	${\displaystyle {\mathcal {O}}(1)}$	${\displaystyle {\mathcal {O}}(1)}$
Kante → angrenzende Kanten	N/A	${\displaystyle {\mathcal {O}}(k)}$	${\displaystyle {\mathcal {O}}(k)}$	${\displaystyle {\mathcal {O}}(k_{v})}$
Eckpunkt → Kanten	${\displaystyle {\mathcal {O}}(f*k_{f})}$	${\displaystyle {\mathcal {O}}(k)}$	${\displaystyle {\mathcal {O}}(k)}$	${\displaystyle {\mathcal {O}}(k_{v})}$
Eckpunkt → Facetten	${\displaystyle {\mathcal {O}}(f*k_{f})}$	${\displaystyle {\mathcal {O}}(k)}$	${\displaystyle {\mathcal {O}}(k)}$	${\displaystyle {\mathcal {O}}(k_{v})}$
Facette → Kanten	${\displaystyle {\mathcal {O}}(k_{f})}$	${\displaystyle {\mathcal {O}}(k_{f})}$	${\displaystyle {\mathcal {O}}(k_{f})}$	${\displaystyle {\mathcal {O}}(k_{f})}$
Facette → Eckpunkte	${\displaystyle {\mathcal {O}}(k_{f})}$	${\displaystyle {\mathcal {O}}(k_{f})}$	${\displaystyle {\mathcal {O}}(k_{f})}$	${\displaystyle {\mathcal {O}}(k_{f})}$
Facette → benachbarte Facette	${\displaystyle {\mathcal {O}}(f*k_{f}^{2})}$	${\displaystyle {\mathcal {O}}(k_{f})}$	${\displaystyle {\mathcal {O}}(k_{f})}$	${\displaystyle {\mathcal {O}}(k_{f})}$

Hierbei bezeichnet:

• ${\displaystyle k}$: Anzahl aller Kanten
• ${\displaystyle k_{f}}$: Anzahl der Kanten einer Facette
• ${\displaystyle k_{v}}$: Anzahl der Kanten, welche zu einem Punkt gehören
• ${\displaystyle f}$: Anzahl aller Facetten

Wie man sieht, sind die Winged-Edge- und die Half-Edge-Struktur von den enthaltenen Informationen nahezu identisch. Sie weisen deshalb auch fast die gleichen Laufzeiten für das Suchen auf. Half Edge ist in den komplexeren Anfragen etwas besser. Hier müssen aufgrund des Zeigers eines Punktes auf eine zugehörige Startkante beim Suchen aller Kanten eines Punktes auch nur diese angefasst werden. Die Knotenliste scheidet von vornherein aus und die Kantenliste ist vom Suchen her genauso gut wie die Winged-Edge-Liste, benötigt jedoch etwas mehr Speicherplatz, da bei Winged Edge zu einer Facette nur eine Startkante abgelegt werden muss.