En dobbeltforbundet kantliste , et andet navn er en halvkants datastruktur , er en datastruktur , der repræsenterer en plan graf på et plan eller et polyeder i rummet. Denne struktur giver effektivt arbejde med topologisk information forbundet med de betragtede objekter (hjørner, kanter, flader). Det bruges ofte i forskellige beregningsgeometriske algoritmer til behandling af polygonpartitioner i et plan, såsom en plan linjegraf . For eksempel er et Voronoi-diagram normalt repræsenteret som en DCEL inde i en afgrænsningsramme.
Denne datastruktur blev først foreslået af Müller og Preparata [1] for at repræsentere et konveks polyeder .
Senere blev ændrede versioner af strukturen udbredt, men navnet forblev.
Strukturen blev oprindeligt designet til at repræsentere forbundne grafer , men DCEL kan også bruges til at repræsentere afbrudte grafer.
En dobbelt sammenkædet liste over kanter består af objekttyper såsom top, kant og ansigt. Disse objekter indeholder pointere til andre objekter. Disse kan enten være C/C++-pointere, der indeholder en adresse i hukommelsen, eller indekser af disse objekter i et array eller enhver anden type adressering. En uundværlig egenskab er muligheden for direkte at få adgang til det objekt, der henvises til, uden at søge efter det. Hvert af objekterne kan også indeholde yderligere information, for eksempel kan et ansigt indeholde farve- eller navneoplysninger.
Et toppunkt indeholder en enkelt pointer til en hvilken som helst halvkant, der udgår fra det toppunkt. Den indeholder også oplysninger om dens koordinater.
En halvkant indeholder en pegepind til det toppunkt, der er dens oprindelse, en pegepind til ansigtet, der ligger til venstre for kanten, samt peger til den næste halve kant, den forrige halvkant og tvillingens halv- kant. Kanten ligger til venstre, så den dobbelte halvkant beskriver højre side af kanten og fuldender den dermed til helheden.
Et ansigt indeholder en pegepind til enhver halvkant, der udgør dens grænse. Det kan også indeholde en liste over halvkanter af alle dets huller, en halvkant pr. hul.
Et simpelt eksempel på DCEL-implementering i C++.
struct Vertex ; struct Half_edge ; struktur Ansigt ; // Vertex struct Vertex { dobbelt x , y ; half_edge * half_edge ; }; // Halvkantstruktur Halvkant { Halvkant * næste , * tvilling , * forrige ; Toppunkt * oprindelse ; Ansigt * ansigt ; }; // Ansigt med huller struktur Ansigt { halvkant * grænse ; Halvkant ** huller ; unsigned long int count_of_holes ; };