Двусвязный список рёбер

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

Примечания

[править | править код]
  1. ↑ Muller, D. E.; Preparata, F. P. «Finding the Intersection of Two Convex Polyhedra», Tech. Rept. UIUC, 1977, 38pp, also Theoretical Computer Science ", Vol. 7, 1978, 217—236

Ссылки

[править | править код]