Двусвязный список рёбер
Двусвязный список рёбер (англ. 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;
};