Двусвязный список рёбер
Двусвязный список рёбер (англ. doubly connected edge list) другое название — полурёберная структура данных (англ. half-edge data structure) — это структура данных, которая представляет планарный граф на плоскости или многогранник в пространстве. Эта структура обеспечивает эффективную работу с топологической информацией, связанной с рассматриваемыми объектами (вершинами, рёбрами, гранями). Её часто применяют в различных алгоритмах вычислительной геометрии для обработки разбиений плоскости на многоугольники, таких как планарный линейный граф. Например, диаграмму Вороного обычно представляют в виде DCEL внутри ограничивающего прямоугольника.
Эту структуру данных впервые предложили Мюллер и Препарата[1] для представления выпуклого многогранника.
Позже распространение получили изменённые варианты структуры, но название осталось.
Изначально структура создавалась для представления связных графов, однако DCEL можно использовать и для представления несвязных графов.
Структура данных
Двусвязный список рёбер состоит из таких типов объектов как: вершина, ребро и грань. Эти объекты содержат указатели на другие объекты. Это могут быть как указатели C/C++, содержащие адрес в памяти, так и индексы этих объектов в массиве или любой другой тип адресации. Непременным свойством является возможность прямого доступа к объекту на который ссылаются, без его поиска. Каждый из объектов может также содержать дополнительную информацию, например грань может содержать информацию о цвете или имени.
Вершина
Вершина содержит единственный указатель на любое полуребро, исходящее из этой вершины. Также содержит информацию о своих координатах.
Полуребро
Полуребро содержит указатель на вершину, являющуюся его началом, указатель на грань, лежащую слева от ребра, а также указатели на следующее полуребро, предыдущее полуребро и полуребро близнеца. Грань лежит слева, потому полуребро близнец описывает правую сторону ребра, дополняя тем самым его до целого.
Грань
Грань содержит указатель на любое полуребро, составляющее его границу. Также может содержать список полуребер всех своих отверстий по одному полуребру на отверстие.
Реализация
Простой пример реализации DCEL на языке C++.
struct Vertex;
struct Half_edge;
struct Face;
// Вершина
struct Vertex {
double x, y;
Half_edge *half_edge;
};
// Полуребро
struct Half_edge {
Half_edge *next, *twin, *prev;
Vertex *origin;
Face *face;
};
// Грань с отверстиями
struct Face {
Half_edge *boundary;
Half_edge **holes;
unsigned long int count_of_holes;
};