Двусвязный список ребер - Doubly connected edge list

В двусвязный список ребер (DCEL), также известный как полуграничная структура данных, это структура данных представлять встраивание из планарный граф в самолет, и многогранники в 3D. Эта структура данных обеспечивает эффективную[количественно оценить ] манипулирование топологической информацией, связанной с рассматриваемыми объектами (вершины, ребра, грани). Он используется во многих алгоритмы из вычислительная геометрия для обработки многоугольных частей плоскости, обычно называемых планарные прямолинейные графики (PSLG).[1] Например, Диаграмма Вороного обычно представляет собой DCEL внутри ограничивающей рамки.

Эта структура данных была первоначально предложена Мюллером и Препаратой.[2] для представлений 3D выпуклые многогранники.

Позже несколько иная структура данных[нужна цитата ] было предложено, но название «DCEL» было сохранено.

Для простоты только связанные графы считаются[кем? ], однако структура DCEL может быть расширена для обработки отсоединенных графов, а также путем введения фиктивных ребер между отсоединенными компонентами.[3].

Структура данных

У каждого полуребра есть ровно одно предыдущее полуребро, следующее полуребро и двойник.

DCEL - это больше, чем просто двусвязный список краев. В общем случае DCEL содержит запись для каждого ребра, вершина и лицо подразделения. Каждая запись может содержать дополнительную информацию, например, лицо может содержать название области. Каждое ребро обычно ограничивает две грани, и поэтому удобно рассматривать каждое ребро как два «полуребра» (которые представлены двумя ребрами с противоположными направлениями между двумя вершинами на рисунке справа). Каждое полуребро «связано» с одной гранью и, таким образом, имеет указатель на эту грань. Все полуребра, связанные с гранью, расположены по часовой стрелке или против часовой стрелки. Например, на рисунке справа все полуребра, связанные со средней гранью (т.е. «внутренние» полуребра), повернуты против часовой стрелки. Полуребро имеет указатель на следующую половину края и предыдущую половину края той же грани. Чтобы добраться до другой грани, мы можем перейти к двойнику полуребра, а затем пройти через другую грань. Каждое полуребро также имеет указатель на свою исходную вершину (конечную вершину можно получить, запросив исходную точку своего двойника или следующего полуребра).

Каждая вершина содержит координаты вершины, а также хранит указатель на произвольное ребро, имеющее вершину в качестве источника. Каждая грань хранит указатель на некоторую половину края своей внешней границы (если грань не ограничена, указатель равен нулю). Он также имеет список полуребер, по одному для каждого отверстия, которое может быть в грани. Если вершины или грани не содержат какой-либо интересной информации, нет необходимости хранить их, что позволяет сэкономить место и уменьшить сложность структуры данных.

Смотрите также

Рекомендации

  1. ^ Определение DCEL можно найти во всех основных книги по вычислительной геометрии.
  2. ^ Мюллер, Д. Э .; Препарата, Ф. П. «Нахождение пересечения двух выпуклых многогранников», Технический отчет UIUC, 1977, 38pp, также Теоретическая информатика, Vol. 7, 1978, 217–236
  3. ^ де Берг, Марк (1997). Вычислительная геометрия, алгоритмы и приложения, третье издание. Springer-Verlag Berlin Heidelberg. п. 33. ISBN  978-3-540-77973-5.