O listă de margini dublu conectată , un alt nume este o structură de date cu jumătate de muchie , este o structură de date care reprezintă un grafic plan pe un plan sau un poliedru în spațiu. Această structură asigură lucrul eficient cu informații topologice asociate cu obiectele luate în considerare (vârfurile, muchiile, fețele). Este adesea folosit în diverși algoritmi de geometrie computațională pentru procesarea partițiilor poligonale ale unui plan, cum ar fi un grafic cu linii plane . De exemplu, o diagramă Voronoi este de obicei reprezentată ca un DCEL în interiorul unei casete de delimitare.
Această structură de date a fost propusă pentru prima dată de Müller și Preparata [1] pentru a reprezenta un poliedru convex .
Ulterior, versiunile modificate ale structurii au devenit larg răspândite, dar numele a rămas.
Structura a fost concepută inițial pentru a reprezenta grafice conectate , dar DCEL poate fi folosit și pentru a reprezenta grafice deconectate.
O listă de margini dublu legată constă din tipuri de obiecte, cum ar fi vârf, muchie și față. Aceste obiecte conțin pointeri către alte obiecte. Acestea pot fi fie pointeri C/C++ care conțin o adresă în memorie, fie indecși ai acestor obiecte într-o matrice, fie orice alt tip de adresare. O proprietate indispensabilă este capacitatea de a accesa direct obiectul la care se face referire, fără a-l căuta. Fiecare dintre obiecte poate conține, de asemenea, informații suplimentare, de exemplu, o față poate conține informații despre culoare sau nume.
Un vârf conține un singur indicator către orice jumătate de muchie care iese din acel vârf. Conține și informații despre coordonatele sale.
O jumătate de muchie conține un indicator către vârful care este originea sa, un indicator către fața situată în stânga muchiei, precum și indicatori către următoarea jumătate de muchie, jumătatea anterioară și jumătatea gemenului. margine. Marginea se află pe stânga, astfel încât jumătatea de margine dublă descrie partea dreaptă a marginii, completând-o astfel în întregime.
O față conține un indicator către orice jumătate de muchie care formează limita sa. Poate conține, de asemenea, o listă de jumătăți de muchii ale tuturor găurilor sale, câte o jumătate de muchie per gaură.
Un exemplu simplu de implementare DCEL în C++.
struct Vertex ; struct Half_edge ; struct Face ; // Structură de vârf Vârf { dublu x , y ; jumătate_de margine * jumătate_de margine ; }; // Structură pe jumătate de margine Half_edge { Half_edge * next , * twin , * prev ; Vârf * origine ; Față * față ; }; // Față cu găuri struct Față { jumatate_margine * limita ; Half_edge ** gauri ; unsigned long int count_of_holes ; };