Монотонный многоугольник: триангуляция одним проходом со стеком

Коротко

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

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

Как думаешь, бывает ли быстрее квадрата

Отрезание ушей стоит не меньше n². На контуре из миллиона вершин это триллион шагов. Но многие контуры устроены просто: силуэт горного хребта, профиль дороги, график функции, замкнутый снизу. У них нет «карманов», куда вертикаль входила бы дважды.

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

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

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

Механизм: две цепи и стек

Монотонность. Самая левая и самая правая вершины делят границу на две цепи. Если обе идут по x слева направо без возвратов, многоугольник монотонен по x. Сортировка вершин по x - слияние двух упорядоченных цепей, O(n).

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

Шаг для новой вершины u.

u на ДРУГОЙ цепи, чем вершина стека:
    u видит все вершины стека - диагонали ко всем, кроме дна
    (треугольники u, v, следующая в стеке), очистить стек
    в стек: предыдущая вершина по x и u
u на ТОЙ ЖЕ цепи:
    снять верхнюю v; пока диагональ от u к новой верхней
    проходит внутри (поворот в нужную сторону) - треугольник
    u, v, она и снять дальше; вернуть последнюю снятую и u
последняя вершина: провести диагонали ко всему стеку

Нижняя цепь 0-4 - выпуклая вверх дуга: каждая её вершина заслоняет предыдущие, и стек копится. Вершина 6 с верхней цепи видит все и снимает их веером пунктирных диагоналей.

Почему линейно. За шаг в стек кладутся не больше двух вершин, значит, всего не больше 2n, и снятий не больше. Каждый поворот либо снимает вершину, либо останавливает снятие - поворотов тоже O(n) - тот же амортизированный довод, что в цепочке Эндрю.

Правило

Монотонный по x многоугольник: сортировка вершин слиянием цепей, затем проход слева направо со стеком. Вершина с другой цепи соединяется со всем стеком; вершина с той же цепи снимает со стека, пока диагональ проходит внутри. Получается n − 2 треугольника за O(n).

Разбор: выпуклая вверх дуга

Многоугольник, где нижняя цепь - выпуклая вверх дуга, а на верхней одна вершина. Журнал печатает вершину, её цепь и стек после шага.

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

def monotonnyj(poly, zhurnal):
    # poly против часовой стрелки и монотонен по x, все x разные.
    # От самой левой вершины против часовой идёт нижняя цепь.
    n = len(poly)
    L = 0
    R = 0
    for i in range(n):
        if poly[i][0] < poly[L][0]:
            L = i
        if poly[i][0] > poly[R][0]:
            R = i
    cep = [1] * n
    i = L
    while i != R:
        cep[i] = 0
        i = (i + 1) % n
    pary = []
    for i in range(n):
        pary.append([poly[i][0], i])
    pary.sort()
    poryadok = []
    for p in pary:
        poryadok.append(p[1])
    stek = [poryadok[0], poryadok[1]]
    treug = []
    for j in range(2, n - 1):
        u = poryadok[j]
        if cep[u] != cep[stek[-1]]:
            # другая цепь: u видит всех в стеке
            while len(stek) > 1:
                v = stek.pop()
                treug.append([u, v, stek[-1]])
            stek = [poryadok[j - 1], u]
        else:
            # та же цепь: снимаем, пока диагональ к стеку внутри
            v = stek.pop()
            while len(stek) > 0:
                w = stek[-1]
                z = povorot(poly[w], poly[v], poly[u])
                if (cep[u] == 0 and z <= 0) or (cep[u] == 1 and z >= 0):
                    break
                treug.append([u, v, w])
                v = stek.pop()
            stek.append(v)
            stek.append(u)
        if zhurnal:
            print(u, ["низ", "верх"][cep[u]], stek)
    u = poryadok[n - 1]
    while len(stek) > 1:
        v = stek.pop()
        treug.append([u, v, stek[-1]])
    return treug

def proverit(poly, treug):
    s_poly = 0
    for i in range(len(poly)):
        a = poly[i]
        b = poly[(i + 1) % len(poly)]
        s_poly = s_poly + a[0] * b[1] - a[1] * b[0]
    s = 0
    nol = 0
    for a, b, c in treug:
        z = abs(povorot(poly[a], poly[b], poly[c]))
        s = s + z
        if z == 0:
            nol = nol + 1
    return [len(treug), s_poly, s, nol]
# нижняя цепь - выпуклая вверх дуга: её вершины заслоняют друг друга,
# и стек копится, пока не придёт вершина верхней цепи
poly = [[0, 20], [2, 28], [4, 32], [6, 34], [8, 35], [10, 20], [9, 60]]
treug = monotonnyj(poly, True)
print(treug)
print(proverit(poly, treug))

2 низ [0, 1, 2]
3 низ [0, 1, 2, 3]
4 низ [0, 1, 2, 3, 4]
6 верх [4, 6]
[[6, 4, 3], [6, 3, 2], [6, 2, 1], [6, 1, 0], [5, 6, 4]]
[5, 204, 204, 0]

Вершины 1-4 нижней цепи легли в стек без единой диагонали: от вершины 3 к вершине 1 прямая проходит под вершиной 2, то есть вне многоугольника. Вершина 6 - с верхней цепи - видит весь стек, и четыре диагонали сразу дают треугольники 6, 4, 3, 6, 3, 2, 6, 2, 1, 6, 1, 0. Последняя вершина 5 закрывает треугольник 5, 6, 4. Проверка: 5 треугольников из 7 вершин, удвоенные площади 204 и 204, вырожденных нет.

Знак поворота w, v, u говорит, где v относительно отрезка wu: на нижней цепи z > 0 значит, что v ниже, и диагональ uw идёт над ней - внутри. Для краткости программа сортирует sort за n · log n; линейно - слить две цепи, они уже упорядочены.

Разбор: стек против ушей

Случайные монотонные многоугольники на 20, 40 и 80 вершин: повороты стека и повороты отрезания ушей.

schet = [0]

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

def uho(poly, ost, k):
    m = len(ost)
    a = poly[ost[(k - 1) % m]]
    b = poly[ost[k]]
    c = poly[ost[(k + 1) % m]]
    if povorot(a, b, c) <= 0:
        return False
    for j in ost:
        p = poly[j]
        if p == a or p == b or p == c:
            continue
        if povorot(a, b, p) >= 0 and povorot(b, c, p) >= 0:
            if povorot(c, a, p) >= 0:
                return False
    return True

def otrezat_ushi(poly):
    ost = list(range(len(poly)))
    treug = []
    while len(ost) > 3:
        k = 0
        while not uho(poly, ost, k):
            k = k + 1
        m = len(ost)
        treug.append([ost[(k - 1) % m], ost[k], ost[(k + 1) % m]])
        ost.pop(k)
    treug.append(ost)
    return treug
def monotonnyj(poly, zhurnal):
    # poly против часовой стрелки и монотонен по x, все x разные.
    # От самой левой вершины против часовой идёт нижняя цепь.
    n = len(poly)
    L = 0
    R = 0
    for i in range(n):
        if poly[i][0] < poly[L][0]:
            L = i
        if poly[i][0] > poly[R][0]:
            R = i
    cep = [1] * n
    i = L
    while i != R:
        cep[i] = 0
        i = (i + 1) % n
    pary = []
    for i in range(n):
        pary.append([poly[i][0], i])
    pary.sort()
    poryadok = []
    for p in pary:
        poryadok.append(p[1])
    stek = [poryadok[0], poryadok[1]]
    treug = []
    for j in range(2, n - 1):
        u = poryadok[j]
        if cep[u] != cep[stek[-1]]:
            while len(stek) > 1:
                v = stek.pop()
                treug.append([u, v, stek[-1]])
            stek = [poryadok[j - 1], u]
        else:
            v = stek.pop()
            while len(stek) > 0:
                w = stek[-1]
                z = povorot(poly[w], poly[v], poly[u])
                if (cep[u] == 0 and z <= 0) or (cep[u] == 1 and z >= 0):
                    break
                treug.append([u, v, w])
                v = stek.pop()
            stek.append(v)
            stek.append(u)
        if zhurnal:
            print(u, ["низ", "верх"][cep[u]], stek)
    u = poryadok[n - 1]
    while len(stek) > 1:
        v = stek.pop()
        treug.append([u, v, stek[-1]])
    return treug

def proverit(poly, treug):
    s_poly = 0
    for i in range(len(poly)):
        a = poly[i]
        b = poly[(i + 1) % len(poly)]
        s_poly = s_poly + a[0] * b[1] - a[1] * b[0]
    s = 0
    nol = 0
    for a, b, c in treug:
        z = abs(povorot(poly[a], poly[b], poly[c]))
        s = s + z
        if z == 0:
            nol = nol + 1
    return [len(treug), s_poly, s, nol]
import random

def sluchajnyj(n):
    # монотонный по x: нижняя цепь ниже 50, верхняя выше 50
    niz = []
    verh = []
    for i in range(1, n - 1):
        x = 3 * i + random.randint(0, 2)
        if random.randint(0, 1) == 0:
            niz.append([x, random.randint(0, 49)])
        else:
            verh.append([x, random.randint(51, 100)])
    return [[0, 50]] + niz + [[3 * n, 50]] + verh[::-1]

random.seed(3)
for n in [20, 40, 80]:
    poly = sluchajnyj(n)
    schet[0] = 0
    t1 = monotonnyj(poly, False)
    s1 = schet[0]
    schet[0] = 0
    t2 = otrezat_ushi(poly)
    print(n, s1, schet[0], proverit(poly, t1)[1:], len(t1), len(t2))

20 8 673 [6285, 6285, 0] 18 18
40 16 3187 [11376, 11376, 0] 38 38
80 40 9746 [24696, 24696, 0] 78 78

Стек: 8, 16, 40 поворотов - растёт линейно, и поворотов даже меньше вершин: повороты нужны только для вершин на той же цепи, а на случайном многоугольнике цепи часто чередуются. Отрезание ушей: 673, 3187, 9746 - n². Обе триангуляции честные - n − 2 треугольника, площади сходятся, - разница только в цене.

Граница применимости: стек работает только на монотонных многоугольниках. На многоугольнике с карманом «другая цепь» не видит весь стек, и диагонали выходят наружу. Как разрезать любой многоугольник на монотонные части - следующий урок.

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

Неверный знак проверки «диагональ внутри». Для нижней и верхней цепи он разный: внутренность выше нижней цепи и ниже верхней. Один знак на обе цепи даёт диагонали снаружи.

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

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

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

Монотонные многоугольники встречаются сами по себе: профили местности, графики, развёртки. И это вторая половина алгоритма n · log n для любого многоугольника: сначала заметание режет его на монотонные части, потом каждая триангулируется стеком.

Теперь сам

Монотонен ли по x многоугольник (0, 0), (4, 0), (4, 4), (2, 1), (0, 4)? А по y?
Почему вершина на другой цепи видит все вершины стека?
Сколько диагоналей проведёт алгоритм на монотонном многоугольнике из 50 вершин?

Ответ. 1. По x - да: любая вертикаль пересекает его по одному отрезку - снизу сторона y = 0, сверху ломаная через вмятину (2, 1). Только вертикальные стороны на краях требуют договора о равных x. По y - нет: горизонталь y = 2 пересекает его по двум отрезкам, вмятина делит верх пополам.

Вершины стека - с одной цепи и все левее u, а все вершины между дном стека и u по x лежат в самом стеке: чужих там нет. Отрезок от u к любой из них идёт через полосу, где граница - только две цепи, и пересечь цепь стека он не может, потому что углы стека - вмятины, обращённые от u.
n − 3 = 47.

Главное

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