Kaksinkertaisesti yhdistetty reunalista , toinen nimi on puolireunatietorakenne , on tietorakenne , joka edustaa tasograafia tasossa tai monitahoista avaruudessa. Tämä rakenne tarjoaa tehokkaan työn tarkasteltuihin objekteihin (pisteet, reunat, pinnat) liittyvien topologisten tietojen kanssa. Sitä käytetään usein erilaisissa laskennallisen geometrian algoritmeissa tason monikulmio-osioiden, kuten tasoviivakaavion , käsittelyyn . Esimerkiksi Voronoi-kaavio esitetään yleensä DCEL:nä rajauslaatikon sisällä.
Tätä tietorakennetta ehdottivat ensin Müller ja Preparata [1] edustamaan kuperaa monitahoista .
Myöhemmin rakenteen modifioidut versiot yleistyivät, mutta nimi säilyi.
Rakenne on alun perin suunniteltu edustamaan yhdistettyjä graafisia kaavioita , mutta DCEL:iä voidaan käyttää myös irrotettujen graafien esittämiseen.
Kaksoislinkitetty reunojen luettelo koostuu objektityypeistä, kuten kärkipiste, reuna ja pinta. Nämä objektit sisältävät osoittimia muihin objekteihin. Nämä voivat olla joko C/C++-osoittimia, jotka sisältävät osoitteen muistissa, tai näiden objektien indeksejä taulukossa tai minkä tahansa muun tyyppisiä osoitteita. Välttämätön ominaisuus on mahdollisuus päästä suoraan kohteeseen, johon viitataan, etsimättä sitä. Jokainen objekteista voi sisältää myös lisätietoa, esimerkiksi kasvot voivat sisältää väri- tai nimitietoja.
Huippupiste sisältää yhden osoittimen mihin tahansa siitä kärjestä lähtevään puolireunaan. Se sisältää myös tietoa sen koordinaateista.
Puolireuna sisältää osoittimen sen alkupisteeseen, osoittimen reunan vasemmalla puolella olevaan pintaan sekä osoittimet seuraavaan puolikasreunaan, edelliseen puolikasreunaan ja kaksoispuoliskoon. reuna. Reuna on vasemmalla, joten kaksoisreuna kuvaa reunan oikeaa puolta täydentäen sen kokonaisuutena.
Kasvot sisältävät osoittimen mihin tahansa puolikkaan reunaan, joka muodostaa sen rajan. Se voi myös sisältää luettelon kaikkien reikien puolikasreunoista, yksi puolikas reuna reikää kohti.
Yksinkertainen esimerkki DCEL:n toteutuksesta C++:ssa.
struct Vertex ; struct Half_edge ; struct Face ; // Vertex struct Vertex { kaksinkertainen x , y ; puoli_reuna * puoli_reuna ; }; // Puolireunarakenne Half_edge { Half_edge * next , * twin , * prev ; Vertex * alkuperä ; Kasvot * kasvot ; }; // Kasvot reikillä struct Face { puoli_reuna * raja ; Half_edge ** reiät ; unsigned long int reikien_määrä ; };