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

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

Эта структура данных была первоначально предложена Мюллером и Препаратой ^[1] для представления трехмерных выпуклых многогранников . Упрощенные версии структуры данных, описанные здесь, рассматривают только связные графы , но структура DCEL может быть расширена для обработки также несвязных графов путем введения фиктивных ребер между несвязными компонентами. ^[2]

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

Каждое полуребро имеет ровно одно предыдущее полуребро, следующее полуребро и близнеца.

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

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

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

Ссылки

^ Muller, DE; Preparata, FP (1978). «Нахождение пересечения двух выпуклых многогранников». Теоретическая информатика . 7 (2): 217– 236. doi : 10.1016/0304-3975(78)90051-8 . hdl : 2142/74093 .
^ де Берг, Марк; Чеонг, Отфрид; ван Кревелд, Марк; Овермарс, Марк (2008). Вычислительная геометрия, алгоритмы и приложения (3-е изд.). Спрингер. стр. 29–33 . ISBN. 978-3-540-77973-5.

[1] Muller, DE; Preparata, FP (1978). «Нахождение пересечения двух выпуклых многогранников». Теоретическая информатика . 7 (2): 217– 236. doi : 10.1016/0304-3975(78)90051-8 . hdl : 2142/74093 .

[2] де Берг, Марк; Чеонг, Отфрид; ван Кревелд, Марк; Овермарс, Марк (2008). Вычислительная геометрия, алгоритмы и приложения (3-е изд.). Спрингер. стр. 29–33 . ISBN. 978-3-540-77973-5.