A kétszeresen összefüggő éllista , más néven fél él adatstruktúra , olyan adatstruktúra , amely sík gráfot ábrázol egy síkon vagy egy térbeli poliédert . Ez a struktúra hatékony munkát biztosít a vizsgált objektumokhoz (csúcsokhoz, élekhez, lapokhoz) társított topológiai információkkal. Gyakran használják különböző számítási geometriai algoritmusokban egy sík sokszögű partícióinak feldolgozására, például egy síkbeli vonalgráfra . Például egy Voronoi-diagramot általában DCEL-ként ábrázolnak egy határolókereten belül.
Ezt az adatstruktúrát először Müller és Preparata [1] javasolta konvex poliéder ábrázolására .
Később a szerkezet módosított változatai terjedtek el, de az elnevezés megmaradt.
A szerkezetet eredetileg összekapcsolt gráfok ábrázolására tervezték , de a DCEL használható szétválasztott gráfok ábrázolására is.
Az élek kétszeresen összekapcsolt listája olyan objektumtípusokból áll, mint a csúcs, az él és az arc. Ezek az objektumok mutatókat tartalmaznak más objektumokra. Ezek lehetnek C/C++ mutatók, amelyek címet tartalmaznak a memóriában, vagy ezen objektumok indexei egy tömbben, vagy bármilyen más típusú címzés. Nélkülözhetetlen tulajdonság az a képesség, hogy a hivatkozott objektumhoz közvetlenül hozzá lehet férni anélkül, hogy keresnénk. Mindegyik objektum tartalmazhat további információkat is, például egy arc tartalmazhat szín- vagy névinformációt.
Egy csúcs egyetlen mutatót tartalmaz az adott csúcsból kimenő bármely fél élre. Információkat is tartalmaz a koordinátáiról.
A fél él tartalmaz egy mutatót a kiindulási csúcsra, egy mutatót az éltől balra fekvő lapra, valamint mutat a következő félélre, az előző félélre és az iker félélére mutató mutatót. él. A széle a bal oldalon fekszik, így az iker félél a szél jobb oldalát írja le, így egészíti ki azt.
Az arc bármely félélére mutató mutatót tartalmaz, amely a határt alkotja. Tartalmazhat egy listát is az összes lyuk féléléről, lyukonként egy félélt.
Egy egyszerű példa a DCEL megvalósítására C++ nyelven.
struct Vertex ; struct Half_edge ; struct Face ; // Vertex struct Vertex { dupla x , y ; fél él * fél él ; }; // Fél él struktúra Half_edge { Half_edge * next , * twin , * prev ; Vertex * eredet ; Arc * arc ; }; // Lyukakkal ellátott arc struct Face { fél_él * határ ; Half_edge ** lyukak ; unsigned long int lyukak_száma ; };