1679
правок
Изменения
Нет описания правки
Заметим, что на плоскости можно выделить определённый порядок обхода рёбер и позже использовать эту информацию. Граф смежности же не учитывает порядок рёбер и направление. Для того, чтобы поддерживать этот порядок, используется '''рёберный список двойной связности''', '''РСДС'''(англ. ''doubly-connecned edge list'', ''DCEL'').
Для удобства каждое ребро разбивается на два ориентированных '''полуребра'''(''half-edges''). Каждое полуребро принадлежит только одной грани — той, которая окажется слева если идти по направлению полуребра(т.е. при обходе грани против часовой стрелки). РСДС в общем случае содержит запись о каждой грани, полуребре и вершине конфигурации. Рассмотрим каждый список в отдельности:# Список граней содержит данные о грани(например, номер) и указатель на произвольное полуребро, принадлежащее ей.# Список полурёбер содержит данные о полуребре, его близнеце(''twin edge'') — противоположно направленному полуребру, следующем(''next'') и предыдущем(''previous'') полуребру в порядке обхода грани, указатели на вершины начала(''origin'') и конца(''destination'') и соответствующую ему грань.# Список вершин содержит данные о вершине, её координаты и указатель на любое полуребро с началом в ней. РСДС можно обобщить в ''cell-tuple structure'' для произвольной размерности. Она позволяет относительно просто представить информацию о смежности ячеек и порядке обхода конфигурации.Также для $\mathbb{R}^3$ существует похожая структура данных [http://en.wikipedia.org/wiki/Quad-edge_data_structure Quad-edge]
==== Пример ====
== Источники ==
* Goodman J.E., O'Rourke J. Handbook of discrete and computational geometry. p. 537, 2004, 2nd edition.
* [http://en.wikipedia.org/wiki/Doubly_connected_edge_list Wikipedia — Doubly connected edge list]
</wikitex>
