Untereinander mit Kanten verbundene Punkte bilden in der Computergrafik ein Polygonnetz, das die Gestalt eines Polyeders definiert. Dreiecksnetze und Vierecksnetze sind hier am geläufigsten. Zur Speicherung von Polygonnetzen und Polygonen gibt es eine Reihe bekannter Datenstrukturen. Die bekanntesten Strukturen sind die Knotenliste, Kantenliste, Winged Edge und die doppelt verkettete Kantenliste (doubly connected halfedge list).

Jeder Knoten muss mindestens eine Verbindung zum Restnetz haben, um Mitglied des Netzes zu sein. Daraus folgt, dass jeder Knoten von jedem anderen im Netz erreichbar ist. In der Graphentheorie sind Polygonnetze als ungerichtete Graphen ohne Mehrfachkanten darstellbar.^[1][2]

Folgende Eigenschaften kann ein Netz haben, keine davon ist allerdings für ein Polygonnetz erforderlich:^[1]

• Strukturiertheit: Ein Polygonnetz wird als strukturiert bezeichnet, wenn jeder innere Punkt die gleiche Anzahl anliegender Kanten und Flächen hat.
• Regularität: Ein Polygonnetz ist regulär, wenn die Kantenlängen in jede Richtung konstant sind. Diese Eigenschaft baut auf der Strukturiertheit auf.
• Orthogonalität: Ein Polygonnetz wird als orthogonal bezeichnet, wenn die Netzkanten rechte Winkel bilden. Die Orthogonalität baut auf die Eigenschaft der Strukturiertheit und der Regularität auf.

Das Polygonnetz als Dreiecksnetz ist eine weit verbreitete Form des Polygonnetzes. Es ist vor allem bei Triangulationen und beim Meshing von Bedeutung.

(TIN)

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.

• Drahtgittermodell
• Meshing
• Garland-Heckbert-Algorithmus

• Polygon Mesh Processing Library

1. ↑ ^{a b} Jens Neumann: Verfahren zur adhoc-Modellierung und -Simulation räumlicher Feder-Masse-Systeme für den Einsatz in VirtualReality-basierten Handhabungssimulationen. Technische Universität Berlin, Fraunhofer IRB Verlag, 2009, ISBN 978-3-8167-7954-4.
2. ↑ Oliver Burgert: Modellbildung II – Nodale Netze – Medizinische Planungs- und Simulationssysteme. (Memento des Originals vom 10. August 2007 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/www.iccas.de (PDF) Universität Leipzig, 2005.