DCEL: как сшить пересечения в карту

Если механизм уже знаком - листай до «Теперь сам».

Как думаешь: что нужно сохранить

Есть карта районов и карта зон затопления. Заметающая прямая нашла все пересечения границ. Можно ли теперь для каждой полученной области сказать, какой район и какая зона ей соответствуют? Одного списка координат недостаточно: у пересечения несколько выходящих рёбер, и нужно выбрать правильное продолжение границы. Нарисуй две пересекающиеся окружности. Их пересечения одинаковы при обходе любой области, а сами области различаются.

На что это похоже

Представь перекрёсток с двусторонними улицами. Для движения по кварталу важна сторона улицы: идя туда, ты оставляешь слева один квартал, обратно - другой. Поэтому одна геометрическая улица получает две записи. В каждой записан следующий поворот при обходе конкретного квартала. Координаты описывают положение дороги, а указатели - то, куда можно продолжить обход.

Механизм: от определения к алгоритму

DCEL - двусвязный список рёбер плоского разбиения. Каждое геометрическое ребро представляют два противоположно направленных полуребра. В записи хранят origin, twin, next, prev, face. Конец можно получить как начало близнеца. Грань находится слева от направления обхода: внешнюю границу ограниченной грани обходят против часовой стрелки, границы дыр - по часовой.

У грани нужен представитель каждой компоненты границы. Одна ссылка не позволит обойти и внешний контур, и две внутренние дырки. У вершины достаточно ссылки на одно исходящее полуребро; чередование переходов через близнеца и соседнее полуребро позволяет обходить её окружение. Обратные ссылки дают проверяемые равенства: twin[twin[e]] == e, prev[next[e]] == e.

Для наложения разбиений соедини геометрические рёбра двух входов, найди пересечения заметанием и разрежь каждое затронутое ребро. В вершине упорядочь исходящие направления, чтобы сшить границы новых граней. Потом перенеси исходные метки. Каждая новая грань принадлежит паре старых граней. При n исходных рёбрах и k пересечениях типичная оценка заметания - O((n+k) log n). Она предполагает корректную обработку совпадений и вырожденностей, а не только общего положения.

Правило

Связи DCEL должны одновременно сохранять геометрию ребра, обход каждой компоненты границы и грань слева; найденные пересечения необходимо превратить в вершины и новые полурёбра.

Разбор: проследим вычисление

Построим ограниченную квадратную грань и внешнюю грань. Четыре стороны дают восемь полурёбер. Программа проверяет обратные связи, непрерывность обхода и противоположность направлений. Она не строит наложение: это минимальная проверка структуры после геометрического этапа. Для внешней грани направление обхода противоположно внутреннему.

points = [(0, 0), (3, 0), (3, 2), (0, 2)]
origin = [0, 1, 2, 3, 1, 2, 3, 0]
twin = [4, 5, 6, 7, 0, 1, 2, 3]
nxt = [1, 2, 3, 0, 7, 4, 5, 6]
prev = [3, 0, 1, 2, 5, 6, 7, 4]
face = [0] * 4 + [1] * 4

def boundary(start):
    edges = []
    e = start
    while True:
        edges.append(e)
        e = nxt[e]
        if e == start:
            return edges
        assert len(edges) <= len(origin)

for e in range(len(origin)):
    assert twin[twin[e]] == e
    assert prev[nxt[e]] == e
    assert nxt[prev[e]] == e
    assert face[nxt[e]] == face[e]
    assert origin[nxt[e]] == origin[twin[e]]

for start in (0, 4):
    edges = boundary(start)
    vertices = [points[origin[e]] for e in edges]
    area2 = 0
    for i, a in enumerate(vertices):
        b = vertices[(i + 1) % len(vertices)]
        area2 += a[0] * b[1] - a[1] * b[0]
    print("грань", face[start], "обход", edges, "площадь*2", area2)
print("полурёбер", len(origin))

грань 0 обход [0, 1, 2, 3] площадь*2 12
грань 1 обход [4, 7, 6, 5] площадь*2 -12
полурёбер 8

Разбор: где проходит граница

Добавь внутренний квадрат, который не касается внешнего. Между квадратами находится одна грань с дырой. Если сохранить только внешний цикл, обход формально замкнётся и все локальные ссылки будут правильны, но дыра исчезнет из представления. Поэтому проверки указателей не заменяют проверку числа компонент границ. Это другой вид дефекта: структура согласована локально, но не описывает исходную карту целиком.

Что ломается без этого

Если не разделить ребро в точке пересечения, обход перепрыгивает через вершину другой карты. Если перепутать близнеца и следующий элемент, граница уходит на соседнюю грань. При одинаковых углах и наложившихся отрезках нельзя полагаться на случайный порядок сортировки: нужны правила объединения совпадающих частей и меток обоих входов. Погрешности вычисления координат способны создать две почти одинаковые вершины вместо одной.

Зачем это в работе

В геоинформационной системе объединяют кадастр с охранными зонами. После наложения нужны площади частей, их соседи и принадлежность исходным объектам. Эти запросы используют связи граней, а не повторный поиск пересечений. Проверять DCEL удобно сразу после каждой локальной правки: ошибка близнеца тогда привязана к одному разрезанному ребру, а не к последующему обходу.

Теперь сам

У ограниченной грани внешняя граница из пяти рёбер и одна треугольная дыра. Сколько представителей компонент ей нужно, и сколько полурёбер непосредственно входит в её границу?