WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

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

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии