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