Dubbelkopplad kantlista
Den dubbelanslutna kantlistan ( DCEL ), även känd som halvkantsdatastruktur , är en datastruktur för att representera en inbäddning av en plan graf i planet och polytoper i 3D . Denna datastruktur ger effektiv [ kvantifiera ] manipulation av den topologiska informationen som är associerad med objekten i fråga (hörn, kanter, ytor). Det används i många algoritmer för beräkningsgeometri för att hantera polygonala indelningar av planet, vanligtvis kallade plana raka linjediagram ( PSLG). Till exempel representeras ett Voronoi-diagram vanligtvis av en DCEL inuti en begränsningsram.
Denna datastruktur föreslogs ursprungligen av Muller och Preparata för representationer av 3D konvexa polyedrar .
föreslogs en något annan datastruktur [ citat behövs ] men namnet "DCEL" behölls.
För enkelhetens skull betraktas endast sammankopplade grafer [ av vem? ] , dock kan DCEL-strukturen utökas för att hantera frånkopplade grafer också genom att introducera dummykanter mellan frånkopplade komponenter.
Datastruktur
DCEL är mer än bara en dubbelt länkad lista över kanter. I det allmänna fallet innehåller en DCEL ett register för varje kant, vertex och yta av underavdelningen. Varje post kan innehålla ytterligare information, till exempel kan ett ansikte innehålla namnet på området. Varje kant avgränsar vanligtvis två ytor och det är därför lämpligt att betrakta varje kant som två "halvkanter" (som representeras av de två kanterna med motsatta riktningar, mellan två hörn, i bilden till höger). Varje halvkant är "associerad" med ett enda ansikte och har alltså en pekare till det ansiktet. Alla halvkanter som är associerade med ett ansikte är medurs eller moturs. Till exempel, på bilden till höger, är alla halvkanter associerade med mittenytan (dvs. de "inre" halvkanterna) moturs. En halvkant har en pekare till nästa halvkant och föregående halvkant av samma sida. För att nå det andra ansiktet kan vi gå till halvkantens tvilling och sedan korsa det andra ansiktet. Varje halvkant har också en pekare till dess ursprungspunkt (destinationspunkten kan erhållas genom att fråga ursprunget för dess tvilling eller nästa halvkant).
Varje vertex innehåller koordinaterna för vertex och lagrar även en pekare till en godtycklig kant som har vertex som ursprung. Varje yta lagrar en pekare till någon halvkant av dess yttre gräns (om ytan är obegränsad är pekaren noll). Den har också en lista med halvkanter, en för varje hål som kan inträffa i ansiktet. Om hörnen eller ytorna inte innehåller någon intressant information finns det inget behov av att lagra dem, vilket sparar utrymme och minskar datastrukturens komplexitet.