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

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

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

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

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

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

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

См. также

Ссылки

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

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

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

[1]

[2]