Разрезать на монотонные части: заметание и вершины расщепления и слияния

Коротко

Многоугольник монотонен по x ровно тогда, когда у него нет двух видов вершин: расщепления (оба соседа правее, угол внутрь больше 180° - карман, открытый вправо) и слияния (оба соседа левее, угол больше 180°). Значит, чтобы разрезать многоугольник на монотонные части, достаточно от каждой такой вершины провести диагональ. Куда её вести, подсказывает заметающая прямая: она держит рёбра, над которыми лежит многоугольник, и у каждого ребра - помощника, последнюю вершину над ним, к которой можно провести диагональ. Разрезание стоит n · log n, затем каждая часть триангулируется стеком за линию - итого любой многоугольник триангулируется за n · log n.

Если ты знаешь пять типов вершин, почему монотонность ломают только расщепление и слияние и как заметание с помощниками рёбер находит диагонали, листай до «Теперь сам».

Как думаешь, где резать

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

Ответь себе до чтения: сколько диагоналей нужно и от каких вершин? Нужно ли резать у каждой вмятины? Ответ: вмятины бывают безобидными - на нижней или верхней цепи, - и опасны только две вершины, где граница разворачивается назад по x. Диагоналей нужно две.

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

Река с островами. Плывёшь вниз по течению на лодке и следишь за тем, сколько рукавов у реки на твоей вертикали. Рукав раздваивается у острова - точка расщепления. Два рукава сливаются за островом - точка слияния. Чтобы разрезать реку на «простые» куски без развилок, у каждой развилки надо провести черту к какому-нибудь ближайшему берегу, уже замеченному лодкой.

Механизм: пять типов вершин и помощники

Типы вершин для прямой, идущей слева направо:

начало        оба соседа правее, угол меньше 180°
конец         оба соседа левее, угол меньше 180°
расщепление   оба соседа правее, угол больше 180° - карман вправо
слияние       оба соседа левее, угол больше 180° - карман влево
обычная       один сосед левее, другой правее

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

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

расщепление v:  ребро прямо под v; диагональ v - его помощник;
                помощником становится v
слияние v:      диагональ от v откладывается: v становится помощником
                ребра под ней; диагональ проводит следующая вершина,
                которая сменит этого помощника
конец, обычная: если помощник уходящего ребра - слияние, диагональ к нему

Слияние нельзя разрешить сразу: его карман открыт влево, а диагональ должна уйти вправо, к вершине, которой прямая ещё не видела. Поэтому слияние ждёт, пока его не сменит другая вершина в роли помощника. Сама вершина-слияние тоже может закрыть так прежнее слияние: она правее его и для него - та самая «следующая вершина».

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

Обычная вершина бывает двух видов. Если предыдущая вершина левее, v на нижней цепи (обход против часовой идёт по низу вправо): её левое ребро уходит из статуса, правое приходит. Иначе v на верхней цепи: статус не меняется, v становится помощником ребра под ней.

Расщепление 5 соединено с помощником 2 - нижней вершиной, к которой прямая уже подошла. Слияние 9 дождалось вершины 7, сменившей его в роли помощника. Две диагонали - три монотонные части.

Правило

Многоугольник монотонен по x, если у него нет вершин расщепления и слияния. Заметание слева направо со статусом рёбер и помощниками проводит от каждой такой вершины диагональ: от расщепления - к помощнику ребра под ней, к слиянию - от вершины, которая сменит его в роли помощника. Время O(n · log n) при статусе в сбалансированном дереве; вместе с триангуляцией частей стеком - O(n · log n) на любой многоугольник.

Разбор: типы вершин зала

def povorot(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def vid(poly, i):
    # тип вершины для прямой, идущей слева направо (все x разные)
    n = len(poly)
    a = poly[(i - 1) % n]
    v = poly[i]
    b = poly[(i + 1) % n]
    vypuklaya = povorot(a, v, b) > 0
    if a[0] > v[0] and b[0] > v[0]:
        if vypuklaya:
            return "начало"
        return "расщепление"
    if a[0] < v[0] and b[0] < v[0]:
        if vypuklaya:
            return "конец"
        return "слияние"
    return "обычная"

# зал с карманом справа (вершина 5) и карманом слева (вершина 9)
zal = [[0, 4], [3, 0], [7, 2], [11, 0], [14, 5], [10, 8], [12, 11],
       [6, 9], [2, 11], [5, 6]]
for i in range(len(zal)):
    print(i, zal[i], vid(zal, i))

0 [0, 4] начало
1 [3, 0] обычная
2 [7, 2] обычная
3 [11, 0] обычная
4 [14, 5] конец
5 [10, 8] расщепление
6 [12, 11] конец
7 [6, 9] обычная
8 [2, 11] начало
9 [5, 6] слияние

Два начала (0 и 8) и два конца (4 и 6) - у зала две левые и две правые «оконечности». Вершина 2 - вмятина на нижней цепи, но обычная: один сосед левее, другой правее, и вертикаль через неё пересекает зал по одному отрезку. Вершина 5 - расщепление: оба соседа правее, угол внутрь больше 180°, справа от неё карман. Вершина 9 - слияние: оба соседа левее, карман слева.

Разбор: диагонали и их проверка

Заметание целиком, на зале и на звёздном многоугольнике из 30 вершин. Каждую диагональ проверяем независимо: середина внутри зала (луч и чётность, координаты удвоены, чтобы середина была целой), ни одного ребра она не пересекает и через чужие вершины не проходит. vyshe_v сравнивает высоты без деления: высота отрезка в точке, умноженная на удвоенную ширину отрезка по x, - целое число, а две такие дроби с положительными знаменателями сравниваются крест-накрест.

def povorot(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def vid(poly, i):
    # тип вершины для прямой, идущей слева направо (все x разные)
    n = len(poly)
    a = poly[(i - 1) % n]
    v = poly[i]
    b = poly[(i + 1) % n]
    vypuklaya = povorot(a, v, b) > 0
    if a[0] > v[0] and b[0] > v[0]:
        if vypuklaya:
            return "начало"
        return "расщепление"
    if a[0] < v[0] and b[0] < v[0]:
        if vypuklaya:
            return "конец"
        return "слияние"
    return "обычная"

def vyshe_v(s, t, x2):
    # выше ли отрезок s отрезка t в точке x = x2 / 2, точно в целых
    a, b = s
    c, d = t
    ys = a[1] * 2 * (b[0] - a[0]) + (x2 - 2 * a[0]) * (b[1] - a[1])
    yt = c[1] * 2 * (d[0] - c[0]) + (x2 - 2 * c[0]) * (d[1] - c[1])
    return ys * 2 * (d[0] - c[0]) > yt * 2 * (b[0] - a[0])

def pod(poly, status, v):
    # ребро статуса прямо под точкой v
    luchshee = -1
    for e in status:
        a = poly[e]
        b = poly[(e + 1) % len(poly)]
        if povorot(a, b, v) > 0:
            if luchshee == -1:
                luchshee = e
            else:
                c = poly[luchshee]
                d = poly[(luchshee + 1) % len(poly)]
                if vyshe_v([a, b], [c, d], 2 * v[0]):
                    luchshee = e
    return luchshee

def na_monotonnye(poly):
    # статус - рёбра (e, e + 1) вправо; многоугольник над ними
    n = len(poly)
    vidy = []
    pary = []
    for i in range(n):
        vidy.append(vid(poly, i))
        pary.append([poly[i][0], i])
    pary.sort()
    status = []
    pomoshchnik = {}
    diag = []
    for x, i in pary:
        v = poly[i]
        k = vidy[i]
        pred = (i - 1) % n
        if k == "начало" or k == "расщепление":
            if k == "расщепление":
                e = pod(poly, status, v)
                diag.append([i, pomoshchnik[e]])
                pomoshchnik[e] = i
            status.append(i)
            pomoshchnik[i] = i
        elif k == "конец" or k == "слияние":
            if vidy[pomoshchnik[pred]] == "слияние":
                diag.append([i, pomoshchnik[pred]])
            status.remove(pred)
            if k == "слияние":
                e = pod(poly, status, v)
                if vidy[pomoshchnik[e]] == "слияние":
                    diag.append([i, pomoshchnik[e]])
                pomoshchnik[e] = i
        elif poly[pred][0] < v[0]:
            # нижняя цепь: многоугольник над v
            if vidy[pomoshchnik[pred]] == "слияние":
                diag.append([i, pomoshchnik[pred]])
            status.remove(pred)
            status.append(i)
            pomoshchnik[i] = i
        else:
            e = pod(poly, status, v)
            if vidy[pomoshchnik[e]] == "слияние":
                diag.append([i, pomoshchnik[e]])
            pomoshchnik[e] = i
    return [vidy, diag]
import math
import random

def proverit(poly, diag):
    # у каждой диагонали середина внутри, и рёбер она не режет
    n = len(poly)
    vse = True
    for a, b in diag:
        p = poly[a]
        q = poly[b]
        m2 = [p[0] + q[0], p[1] + q[1]]
        schet = 0
        for i in range(n):
            u = [2 * poly[i][0], 2 * poly[i][1]]
            w = [2 * poly[(i + 1) % n][0], 2 * poly[(i + 1) % n][1]]
            if (u[1] > m2[1]) != (w[1] > m2[1]):
                z = povorot(u, w, m2)
                if (w[1] > u[1] and z > 0) or (w[1] < u[1] and z < 0):
                    schet = schet + 1
            c = poly[i]
            d = poly[(i + 1) % n]
            if povorot(c, d, p) * povorot(c, d, q) < 0:
                if povorot(p, q, c) * povorot(p, q, d) < 0:
                    vse = False
            # чужая вершина на самой диагонали (все x разные)
            if c != p and c != q and povorot(p, q, c) == 0:
                if min(p[0], q[0]) < c[0] and c[0] < max(p[0], q[0]):
                    vse = False
        if schet % 2 == 0:
            vse = False
    return vse

def zvezda(n):
    # звёздный многоугольник: углы по возрастанию, радиусы случайные
    ugly = []
    for i in range(n):
        ugly.append(random.uniform(0, 2 * math.pi))
    ugly.sort()
    poly = []
    for u in ugly:
        r = random.uniform(100, 450)
        x = round(500 + r * math.cos(u))
        poly.append([x, round(500 + r * math.sin(u))])
    return poly

zal = [[0, 4], [3, 0], [7, 2], [11, 0], [14, 5], [10, 8], [12, 11],
       [6, 9], [2, 11], [5, 6]]
random.seed(1)
for poly in [zal, zvezda(30)]:
    vidy, diag = na_monotonnye(poly)
    plohih = 0
    for k in vidy:
        if k == "расщепление" or k == "слияние":
            plohih = plohih + 1
    print(len(poly), plohih, len(diag), proverit(poly, diag))
print(na_monotonnye(zal)[1])

10 2 2 True
30 5 5 True
[[7, 9], [5, 2]]

У зала две «плохие» вершины и две диагонали, обе внутри. У звезды пять и пять. Последняя строка - диагонали зала: 7 - 9 закрывает слияние (вершина 7 первой сменила его в роли помощника), 5 - 2 - расщепление (вершина 2 - последняя пройденная над нижним ребром).

Статус здесь - список с перебором при поиске ребра под вершиной, то есть O(n) на событие; в сбалансированном дереве это log n. Учебные допущения те же, что во всей главе: все x различны. Равные x доопределяют порядком по y - как поворот системы координат на бесконечно малый угол, - но одной сортировки мало: типы вершин и сравнение высот (у вертикального ребра ширина ноль) надо переписать под этот порядок. Резать контур по диагоналям на части - отдельный шаг.

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

Резать у каждой вмятины. Вмятина на цепи - обычная вершина, монотонность она не портит. Лишние диагонали дают лишние куски и тонкие треугольники.

Разрешать слияние сразу. Диагональ влево слияние не чинит: карман открыт влево, и вертикаль слева от него входит в зал дважды. Нужна вершина справа.

Монотонность по y, когда вход продуман по x. Типы вершин считаются для выбранного направления прямой. Сменил направление - пересчитай типы.

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

Это стандартный путь от любого многоугольника к треугольникам за n · log n: монотонные части плюс стек. Те же типы вершин нужны при закраске многоугольников построчно - строка развёртки встречает «расщепление» как появление нового отрезка закраски и «слияние» как его конец. Теоретически триангуляция возможна и за O(n) (Шазелл, 1991), но этот алгоритм так сложен, что на практике его не используют; в библиотеках - заметание или отрезание ушей.

Теперь сам

Вершина (5, 5) с соседями (8, 2) и (8, 9), угол внутрь больше 180°. Какой это тип?
У многоугольника нет ни одного расщепления и слияния, но есть пять вмятин. Монотонен ли он по x?
Почему слиянию диагональ проводит не оно само, а следующая вершина?

Ответ. 1. Оба соседа правее, угол больше 180° - расщепление: справа от неё карман.

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

Главное

Монотонность ломают только вершины, где граница разворачивается назад внутрь: расщепление и слияние. Заметание с помощниками рёбер ведёт от каждой из них диагональ - и любой многоугольник за n · log n режется на монотонные части, которые стек триангулирует за линию.