Уши многоугольника: почему любой многоугольник режется на треугольники

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

Как думаешь, всегда ли получится

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

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

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

Обрезка торта. Торт - многоугольник со вмятинами. Нож ты ставишь только так, чтобы отрезать кусок-треугольник у одного угла, и не задеть остальной торт. Если угол острый и выпирает наружу, а внутри отрезаемого треугольника нет других углов торта, - режь. Остаток - снова торт, только на угол меньше. Ухо - угол, у которого можно отрезать кусок одним разрезом.

Механизм: диагональ существует, ушей два

Сумма углов и счёт. Сумма внутренних углов простого многоугольника - (n − 2) · 180°, а у каждого треугольника 180°. Значит, если триангуляция есть, треугольников в ней n − 2. Каждая диагональ увеличивает число частей на одну: из одного многоугольника n − 2 части получаются за n − 3 разреза.

Почему диагональ всегда есть. Возьми самую левую вершину v (из нескольких самых левых - самую нижнюю) и её соседей u и w. Угол при v выпуклый - левее нет ничего. Если отрезок uw целиком внутри, это диагональ. Если нет, внутри треугольника u, v, w есть другие вершины, и самая далёкая от прямой uw из них, x, соединяется с v диагональю. Почему: проведи через x прямую, параллельную uw. Часть треугольника между ней и v не содержит вершин - x самая далёкая. Пусть ребро контура пересекает vx. Из точки пересечения оно уходит в обе стороны, а параллельную прямую отрезок пересекает не больше раза - значит, одна его половина остаётся в этой части. Выйти через uv или vw она не может - это рёбра контура, - значит, кончается вершиной внутри части. А вершин там нет. Диагональ режет многоугольник на два меньших, и по индукции каждый триангулируется.

Два уха (Майстерс, 1975). В триангуляции из n − 2 треугольников треугольники соединены в дерево: соседние - те, что делят диагональ. Цикла нет: каждая диагональ режет многоугольник на две части, и убрать её из графа соседства - значит разорвать его надвое; связный граф, который рвётся от удаления любого ребра, - дерево. У дерева с хотя бы двумя узлами хотя бы два листа. Лист-треугольник имеет две стороны на границе многоугольника, а третья - диагональ, то есть это ухо. Два листа - два уха.

Отрезание ушей. Пока вершин больше трёх: найти ухо, записать его треугольник, выкинуть вершину. Проверка уха - один поворот на выпуклость и проход по оставшимся вершинам, не попала ли какая-нибудь в треугольник. Если каждый раз искать ухо с начала, выходит O(n³) в худшем случае. Если помнить, кто ухо, а после отрезания перепроверять только двух соседей, - O(n²): у остальных вершин треугольник не изменился, а их ответ «ухо или нет» не меняется - отрезок, не касающийся отрезанной вершины, не может зайти в треугольник уха: вершин там нет, а выйти пришлось бы через стороны многоугольника.

Правило

Простой многоугольник с n вершинами всегда триангулируется: n − 2 треугольника, n − 3 диагонали. У него есть хотя бы два уха - вершины с выпуклым углом и пустым треугольником с соседями. Отрезание ушей строит триангуляцию за O(n²), если поддерживать признак «ухо» и перепроверять только соседей отрезанной вершины.

Разбор: стрелка

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

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):
    # вершина 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):
    # 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
# стрелка: невыпуклый многоугольник из девяти вершин
strelka = [[0, 2], [6, 2], [6, 0], [10, 4], [6, 8], [6, 6], [0, 6],
           [3, 4], [1, 3]]
treug = otrezat_ushi(strelka)
print(len(strelka), len(treug))
print(treug[:4])
print(treug[4:])
s_poly = 0
for i in range(len(strelka)):
    a = strelka[i]
    b = strelka[(i + 1) % len(strelka)]
    s_poly = s_poly + a[0] * b[1] - a[1] * b[0]
s_treug = 0
for a, b, c in treug:
    s_treug = s_treug + povorot(strelka[a], strelka[b], strelka[c])
print(s_poly, s_treug)

9 7
[[8, 0, 1], [1, 2, 3], [8, 1, 3], [3, 4, 5]]
[[3, 5, 6], [3, 6, 7], [3, 7, 8]]
69 69

Семь треугольников - 9 − 2. Первое ухо - при вершине 0, его треугольник 8, 0, 1. Вершина 7 - вершина выемки: угол там больше 180°, ухом она быть не может, и треугольник 3, 7, 8 стал последним. Последняя строка - проверка: удвоенная площадь многоугольника по формуле шнурка и сумма удвоенных площадей треугольников, обе 69. Это свидетель, а не доказательство: перекрытие и пропуск по отдельности сумму бы испортили, хотя вместе могли бы и уравновеситься.

Почему проверка «внутри треугольника» нестрогая: вершина, лежащая на стороне будущего треугольника, тоже мешает. Иначе отрезанный треугольник касался бы контура изнутри, и в соседнем месте осталась бы дыра.

Разбор: цена на звёздах

Звёзды с 10, 20 и 40 вершинами: лучи и впадины через одну.

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):
    # вершина 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):
    # 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
import math

def zvezda(n):
    # n вершин по кругу, через одну - на внутреннем радиусе
    poly = []
    for i in range(n):
        r = 1000
        if i % 2 == 1:
            r = 400
        ugol = 2 * math.pi * i / n
        x = round(r * math.cos(ugol))
        poly.append([x, round(r * math.sin(ugol))])
    return poly

for n in [10, 20, 40]:
    schet[0] = 0
    treug = otrezat_ushi(zvezda(n))
    print(n, len(treug), schet[0])

10 8 85
20 18 387
40 38 1667

Удвоение n увеличивает число поворотов в 4,3-4,6 раза - это n². У звезды каждый луч - ухо, и поиск находит ухо сразу, поэтому цена одного отрезания - проход по оставшимся вершинам, а всего - сумма m по m от n до 3. На контурах, где ухо далеко от начала списка, наивный поиск даёт n³; признак «ухо», который хранится и обновляется только у соседей, возвращает n². Устроено это так: у каждой вершины флаг «ухо», посчитанный один раз; отрезание вершины меняет треугольники только двух её соседей, и флаги перепроверяются у них - за O(n) каждый, а следующее ухо - любая вершина с флагом. Программа урока этого не делает и ищет с начала списка - ради краткости.

n² на миллионе вершин - уже много. Поэтому библиотеки отрезания ушей (например, earcut в веб-картах) ускоряют проверку «внутри треугольника»: вершины раскладываются по пространственному хешу, и проверяются только близкие к треугольнику.

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

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

Обход по часовой стрелке. Знак поворота «выпуклый угол» переворачивается, и алгоритм ищет уши среди вершин вмятин. Сначала проверь знак формулы шнурка и при необходимости разверни контур.

Многоугольник с дырами. Ушей не хватает: дыра не граница внешнего обхода. Дыры соединяют с внешним контуром «мостами» - парой совпадающих рёбер - и получают один контур без дыр.

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

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

Теперь сам

1. Сколько треугольников и диагоналей у триангуляции многоугольника из 100 вершин?
2. Многоугольник (0, 0), (2, 1), (4, 4), (0, 4). Какие у него уши?
3. Почему у многоугольника не может быть меньше двух ушей, если n ≥ 4?