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.