Триангуляция по косточкам

Всё началось невинно. Шёл 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-библиотека, в которой помимо описанного выше, есть ещё много полезного:

• тесселяция

• разбиение на выпуклые многоугольники

• построенние серединных многоугольников

• поддержка внутренних точек

Можно попробовать интерактивные демо:

• Triangulation

• Tessellation

И посмотреть на бенчмарки против других популярных решений.