Конспект: триангуляция многоугольника и задача о галерее

Понятия

Диагональ - отрезок между вершинами, целиком внутри многоугольника. Триангуляция многоугольника - разрезание диагоналями на треугольники.

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

Монотонный по x многоугольник - любая вертикаль пересекает его по одному отрезку; граница - две цепи.

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

Что унести

СЧЁТ
треугольников n − 2, диагоналей n − 3 (сумма углов (n − 2) · 180°)
треугольники триангуляции - дерево по диагоналям
два уха (Майстерс, 1975): у дерева два листа

ОТРЕЗАНИЕ УШЕЙ                                O(n²)
ухо = выпуклый угол И пустой треугольник (нестрого: и на сторонах)
отрезать - перепроверить только двух соседей
стрелка из 9 вершин: 7 треугольников, площади 69 = 69
звёзды 10/20/40: 85, 387, 1667 поворотов - n²
earcut в веб-картах: + пространственный хеш для проверки

ГАЛЕРЕЯ (Хватал 1975, Фиск 1978)              ⌊n/3⌋ хватает всегда
триангуляция → раскраска в 3 цвета обходом дерева треугольников
→ охранники в вершинах самого редкого цвета
гребёнка: ⌊n/3⌋ необходимо (кончики зубцов не видят общих точек)
стрелка: 2 охранника при гарантии 3
ортогональные залы (углы 90° и 270°): ⌊n/4⌋;  с h дырами: до ⌊(n + h)/3⌋
наименьшее число: NP-трудно (Ли, Лин 1986), ∃ℝ-полно (2018)

МОНОТОННЫЙ + СТЕК                             O(n)
сортировка = слияние двух цепей
другая цепь: диагонали ко всему стеку, стек = [пред, u]
та же цепь: снимать, пока диагональ внутри
    (нижняя цепь - поворот налево, верхняя - направо)
80 вершин: 40 поворотов против 9746 у ушей

РАЗРЕЗАНИЕ НА МОНОТОННЫЕ                      O(n · log n)
монотонен ⇔ нет расщеплений и слияний
статус: рёбра, над которыми многоугольник, с помощниками
расщепление: диагональ к помощнику ребра под ней
слияние: ждёт - диагональ проведёт вершина, сменившая его
итог: любой многоугольник - n · log n; Шазелл O(n) - только теория
зал из 10 вершин: 2 опасные вершины, 2 диагонали

Ловушки джокера

Проверить у уха только выпуклость. Треугольник выходит за контур через вмятину.

Строгая проверка «внутри». Вершина на стороне треугольника пропускается - гребёнка это ловит.

Обход по часовой стрелке. Все знаки «выпуклый угол» переворачиваются.

Считать раскраску оптимумом. Это гарантия для худшего зала, а не минимум для данного.

Стек на немонотонном многоугольнике. Диагонали выходят наружу.

Резать у каждой вмятины. Опасны только расщепление и слияние.

Разрешать слияние сразу. Диагональ влево уходит в карман.

Проверь себя

Почему у многоугольника всегда есть два уха и сколько в триангуляции треугольников? Какие два условия делают вершину ухом? Почему раскраска в три цвета существует и даёт ⌊n/3⌋ охранников, а гребёнке меньше нельзя? Почему стек линеен и почему только на монотонном многоугольнике? Какие вершины ломают монотонность и куда от них ведёт диагональ?

• Граф видимости соединяет углы препятствий, старт и финиш допустимыми отрезками; Дейкстра на длинах находит кратчайший путь точечного робота. Для переноса формы R запрещены P+(-R), вращение требует дополнительной координаты.