Всё началось невинно. Шёл 2009 год, и я просто хотел портировать Earcut на Flash — для своей мини-игры. Тогда это сработало, но с годами стало понятно: простые решения перестают работать, как только хочешь выжать из них максимум.
Я углубился в теорию, и начал перебирать статьи и просматривать ролики на youtube. Сильно помогла книга А.В. Скворцова. В итоге я остановился на подходе разбиения на монотонные многоугольники. Он казался самым очевидным. И ох, сколько я набил себе шишек, пока его реализовал.
Первым прорывом стало осознание, что float нужно заменить на int. Алгоритм почти заработал - но всё равно сыпался. Он оказался крайне не устойчивым ко входным данным: самопересечения, коллинеарные рёбра, касания дыр к внешнему контуру, дегенеративные точки - всё это могло его поломать в любой момент. В итоге алгоритм вроде и работал, но мне он не нравился.
Шли года, моя рука крепла. Я написал iOverlay - булеву библиотеку, которая может устранить самопересечения и привести начальные условия в надлежащий вид. И тогда я решил вернуться к старому триангулятору и разобрать его по косточкам. На этот раз всё пошло проще - потому что я уже знал, чего ждать.
В небе начинает светить радуга, когда можно доверять входным данным. А еще я понял, что монотонное разбиение - это просто абстракция, и ее можно спокойно выкинуть. Я также отполировал условие Делоне так, что оно заблестело.
Так появился мой кастомный sweep-line алгоритм с прямым триангулированием. Он не только быстрый и простой, но и невероятно стабильный: я прогнал больше миллиарда случайных тестов - и всё сошлось бит в бит.
К делу!
Как я уже упоминал, для большинства алгоритмов такого типа формат входных данных критичен. Поэтому сразу зафиксируем жёсткие требования:
Нет самопересечений
Контуры могут касаться друг друга только точка-в-точку
Внешние контуры идут против часовой стрелки
Дырки - наоборот, по часовой стрелке
Шаг 1: выбираем направление заметающей прямой
Поскольку это sweep-line алгоритм, первым делом нужно выбрать ось, вдоль которой мы будем двигать заметающую прямую. Мне привычнее всего двигать её слева направо вдоль оси X.
Все вершины нужно отсортировать по координатам:
сначала по
x,если
xравен - поy.
Граничный случай: касания
Одним из тонких моментов является ситуация, когда в одной точке сходятся несколько контуров, например внешний и одна или несколько дыр. Такие точки могут касаться друг друга в различных конфигурациях, но есть важное свойство:
Число рёбер в точке всегда чётное, а при обходе по кругу рёбра будут чередоваться: входящее / исходящее / входящее / исходящее...
Шаг 2: структура вершины
Каждая вершина должна "знать" своих соседей по контуру, поэтому мы храним prev и next:
Должно получиться, что то вроде:
struct ChainVertex {
index: int,
this: Point,
next: Point,
prev: Point,
}
index - порядковый номер вершины. Совпадающие точки имеют одинаковый индекс.this - координаты текущей вершины.prev - предыдущая точка по контуру.next - следующая точка по контуру.
Шаг 3: классификация вершин
Теперь, нужно определить тип каждой вершины - это необходимо для правильной обработки в sweep-line алгоритме. Тип зависит от формы угла, положения соседей и направления обхода.
Вот все категории:
Start - начало выпуклого сегмента монотонного многоугольника.
End - конец монотонного многоугольника
Split - вершина, "разрезающая" многоугольник
Merge - вершина, где сливаются два монотонных многоугольника
Join - вершина равная, либо next либо prev
Steiner - искусственная точка, является некой комбинацией Split/Merge
Шаг 4: sweep и триангуляция "на лету"
Двигаясь по отсортированным вершинам, мы жадно собираем треугольники. При этом формируются временные сегменты - фактически, монотонные многоугольники, которые:
начинаются в вершинах типа Start и Split,
заканчиваются в вершинах End и Merge.
У каждого активного сегмента есть опорное ребро - обычно это либо следующее ребро по контуру, либо мостик между двумя сегментами. На анимации такие рёбра выделены синим цветом.
Работа с опорными рёбрами
Все опорные рёбра хранятся в древовидной структуре, отсортированной по вертикали. Это позволяет быстро определить, в какой сегмент попадает новая вершина: мы просто ищем ближайшее снизу ребро, которому она принадлежит или под которым находится.
Сборка треугольников
Каждый активный сегмент может содержать как одну вершину, так и цепочку рёбер. При добавлении новой вершины:
мы пытаемся сформировать один или несколько треугольников
их вершины всегда обходятся против часовой стрелки
Для хранения результата используется структура:
struct Triangle {
vertices: [IndexPoint; 3], // координата + индекс
neighbors: [int; 3], // ссылки на соседние треугольники
}
vertices - три точки, упорядоченные против часовой стрелкиneighbors - индекс соседнего треугольника по каждой стороне (если есть)
Внешние и внутренние рёбра
Каждое ребро в треугольнике может быть:
внешним - если оно принадлежит контуру (внешнему или дырке)
внутренним - если оно "разделяет" два треугольника
Если ребро внутреннее, у треугольника должен быть проставлен индекс соседнего треугольника, который примыкает с другой стороны.
Фантомные рёбра
Иногда при построении треугольника добавляется внутреннее ребро, у которого пока нет второго треугольника. В этом случае оно считается фантомным — оно "висит" в воздухе. При первом визите такое ребро конвертируется в обычное внутреннее: оно связывается с текущим треугольником.
Шаг 5 (опциональный): приведение к Делоне
На этом этапе у нас уже есть корректная триангуляция. Но если хочется сделать её ещё лучше, можно привести её к соответствию условию Делоне.
Для этого мы проходим по всем треугольникам и проверяем условие Делоне для каждого ребра, которое граничит с соседним треугольником. Я не буду подробно расписывать саму проверку - у меня есть отдельная статья с наглядной анимацией, объясняющей, что именно считается нарушением.
Если условие не выполняется, мы:
удаляем общее ребро между двумя соседними треугольниками
перестраиваем диагональ, соединяя противоположные вершины
Процесс повторяется, пока все внутренние рёбра не удовлетворяют условию Делоне.
Почему это работает?
Каждая такая операция уменьшает тупой угол в соответствующей паре треугольников. Это означает, что процесс монотонно сходится - и гарантированно завершится.
В реализациях на float здесь часто всплывает баг: из-за накопленных ошибок округления может возникнуть бесконечный цикл-флипов. Это известная проблема, ее еще часто называют проблемой "правильного шестиугольника".
С int (или fixed-point) логикой всё проще:
проверка становится строгой
все операции детерминированы
а значит — бесконечных циклов просто не возникает.
Заверните я беру
Если вам интересна моя реализация - ее можно потрогать в iTriangle.
Это Rust-библиотека, в которой помимо описанного выше, есть ещё много полезного:
тесселяция
разбиение на выпуклые многоугольники
построенние серединных многоугольников
поддержка внутренних точек
Можно попробовать интерактивные демо:
И посмотреть на бенчмарки против других популярных решений.