Eine Half-Edge-Datenstruktur oder auch Doubly-Connected Edge List (DCEL) (engl. Doppelt verkette 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ä...