1679
правок
Изменения
Нет описания правки
Заметим, что на плоскости можно выделить определённый порядок обхода рёбер и позже использовать эту информацию. Граф смежности же не учитывает порядок рёбер и направление. Для того, чтобы поддерживать этот порядок, используется '''рёберный список двойной связности''', '''РСДС'''(англ. ''doubly-connecned edge list'', ''DCEL'').
РСДС можно обобщить в ''cell-tuple structure'' для произвольной размерности. Она позволяет относительно просто представить информацию о смежности ячеек и порядке обхода конфигурации. Также для $\mathbb{R}^3$ существует похожая структура данных [http://en.wikipedia.org/wiki/Quad-edge_data_structure Quad-edge]
==== Представление ====
Для удобства каждое ребро разбивается на два ориентированных '''полуребра'''(''half-edges''). Каждое полуребро принадлежит только одной грани — той, которая окажется слева если идти по направлению полуребра(т.е. при обходе грани против часовой стрелки).
РСДС в общем случае содержит запись о каждой грани, полуребре и вершине конфигурации. Рассмотрим каждый список в отдельности:
# Список граней содержит данные о грани(например, номер) и указатель на произвольное полуребро, принадлежащее ей.
# Список полурёбер содержит данные о полуребре, его близнеце(''twin edge'') — противоположно противоположном направленному полуребру(оно не всегда существует, если его нет, будем хранить null), следующем(''next'') и предыдущем(''previous'') полуребру в порядке обхода грани, указатели на вершины начала(''origin'') и конца(''destination'') и соответствующую ему грань.
# Список вершин содержит данные о вершине, её координаты и указатель на любое полуребро с началом в ней.
==== Пример ====
{|align="left"
| [[Файл:sample_graph.png | 320x200 px | frame | Пример конфигурации. Номерами обозначены грани.]]
| [[Файл:dcel.png | 320x200 px | frame | Стрелками обозначены полурёбра.]]
|}
Построим часть РСДР для данной конфигурации.
{|align="left"
|
{| cellspacing="0" border="1"
|+ Список граней
! Грань
! Полуребро
|-
| 1 || GH
|-
| 2 || IH
|-
| 3 || EI
|}
|
{| cellspacing="0" border="1"
|+ Список полурёбер
! Полуребро
! Близнец
! Следующее
! Предыдущее
! Начало
! Конец
! Грань
|-
| … || … || … || … || … || … || …
|-
| GI || IG || IH || HG || G || I || 2
|-
| … || … || … || … || … || … || …
|-
| IC || null || CI || EI || I || C || 3
|-
| … || … || … || … || … || … || …
|}
|
{| cellspacing="0" border="1"
|+ Список вершин
! Вершина
! Координаты
! Полуребро
|-
| … || … || …
|-
| H || … || HI
|-
| C || … || CI
|-
| … || … || …
|}
|}
