Это приложение описывает алгоритм триангуляции по схеме «разделяй и властвуй» со слиянием подтриангуляций вдоль общих касательных. Исторически именно он был реализован в проекте первым; в основном тексте описан используемый сейчас подход на основе библиотеки CGAL. Материал ниже сохранён как дополнительный: он полезен для понимания классической схемы и тех трудностей с вырожденными конфигурациями, которые в итоге и привели к смене подхода.

За основу взят алгоритм «разделяй и властвуй» из монографии А. В. Скворцова «Триангуляция Делоне и её применение» с непосредственной перестройкой по Делоне сразу после построения каждого нового треугольника. Алгоритм имеет среднюю и худшую трудоёмкость $O(N \log N)$ относительно числа исходных точек.

Общая схема

Идея алгоритма повторяет классическую парадигму «разделяй и властвуй».

1. Множество точек рекурсивно делится прямой линией на две примерно равные части.
2. Рекурсия продолжается до тех пор, пока в каждой части не останется три или четыре точки — такие конфигурации триангулируются явно.
3. Полученные подтриангуляции попарно сшиваются вдоль общей зоны между их выпуклыми оболочками.
4. При сшивании каждое новое ребро проверяется по условию Делоне, и при необходимости пара смежных треугольников перестраивается заменой диагонали.

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

Рекурсивное разделение точек

Направление разреза выбирается по форме охватывающего прямоугольника: если он шире, чем выше, точки сортируются и делятся по горизонтальной координате, иначе — по вертикальной. Такой выбор уменьшает длину будущего шва между подтриангуляциями и поэтому уменьшает количество перестроений.

Размер двух получаемых частей подбирается так, чтобы все листовые задачи имели ровно три или четыре точки. Для больших наборов используется деление пополам, а для нескольких малых размеров применяется специальное разбиение «3 и $N-3$», гарантирующее, что в листах рекурсии не появится конфигурация из одной или двух точек. Корректность такого разбиения для любых $N \geq 6$ следует из того, что любое $N$ представимо в виде $3k$, $3(k-1)+4$ или $3(k-2)+4 \cdot 2$.

В формализованной записи рекурсивный алгоритм выглядит так.

1. Если число точек $N = 3$ — построить триангуляцию из одного треугольника.
2. Иначе, если $N = 4$, — построить триангуляцию из двух или трёх треугольников.
3. Иначе, если $N = 8$, — разбить множество на две части по четыре точки, рекурсивно применить алгоритм и склеить результаты.
4. Иначе, если $N < 12$, — разбить множество на части из трёх и $N-3$ точек, рекурсивно применить алгоритм и склеить результаты.
5. Иначе ($N \geq 12$) — разбить множество пополам, на части из $\lfloor N/2 \rfloor$ и $\lceil N/2 \rceil$ точек, рекурсивно применить алгоритм и склеить результаты.

Глубина рекурсии составляет $O(\log N)$, и на каждом уровне суммарная работа линейна по числу точек, что и даёт итоговую трудоёмкость $O(N \log N)$ в среднем и в худшем случаях (рисунок Разделение).

Базовые конфигурации

Для трёх точек существует единственная допустимая триангуляция — один треугольник, построенный непосредственно на этих трёх вершинах. Для четырёх точек возможны два случая в зависимости от их взаимного расположения (рисунок Базовые случаи).

1. Все четыре точки лежат на выпуклой оболочке. Четырёхугольник разбивается одной из двух диагоналей. Выбор определяется условием Делоне: проверяется, лежит ли одна из вершин внутри описанной окружности треугольника, построенного на оставшихся трёх точках. Та диагональ, для которой условие выполнено, и закладывается в базовую триангуляцию.
2. Одна точка находится внутри треугольника, образованного тремя другими. Внутренняя точка соединяется с каждой из вершин внешнего треугольника, и область разбивается на три треугольника.

Слияние двух подтриангуляций

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

Поиск общих касательных. Сначала на двух выпуклых оболочках находятся две общие касательные — нижняя и верхняя. Начальное приближение — ребро, соединяющее самую правую точку левой оболочки с самой левой точкой правой; затем оно итеративно сдвигается по вершинам обеих оболочек, пока не окажется снизу (или сверху) от всех остальных точек двух множеств. Между двумя касательными остаются две цепочки граничных вершин — левая и правая, — пространство между которыми и предстоит заполнить треугольниками.

Заполнение зоны слияния. Нижняя касательная объявляется текущим базовым ребром. По обе стороны от него берутся ближайшие вершины двух цепочек, и из них рассматриваются два кандидата на следующий треугольник: один с левой вершиной, второй — с правой. Допустимым считается треугольник, который не выворачивает ориентацию (внутренний угол при базовом ребре меньше развёрнутого) и не накрывает уже построенных частей сетки. Если допустимы оба кандидата, выбирается тот, у которого минимальный угол больше: такой треугольник «более равносторонний» и с меньшей вероятностью будет перестроен в дальнейшем. Открытая сторона построенного треугольника становится новым базовым ребром, и шаг повторяется, пока базовое ребро не совпадёт с верхней касательной (рисунок Слияние).

Немедленная локальная перестройка. После добавления нового треугольника его рёбра проверяются против ранее построенных соседей: если четырёхугольник, образованный новым треугольником и его соседом по ребру, нарушает условие Делоне, выполняется flip-операция. Немедленная перестройка избавляет от отдельного финального прохода по сетке и обычно уменьшает суммарное число перестроений.

Вставка рёбер-ограничений

Алгоритм выше строит триангуляцию Делоне выпуклой оболочки точек, но ничего не знает о границах расчётной области и контурах отверстий. Чтобы заданные рёбра гарантированно присутствовали в сетке, они вставляются в готовую триангуляцию отдельной операцией восстановления рёбер.

Вставка одного ребра выполняется так: находятся все треугольники, которые пересекает отрезок, и удаляются — в сетке образуется многоугольная пустота, которую вставляемый отрезок делит на две цепочки вершин, верхнюю и нижнюю; каждая цепочка независимо заполняется треугольниками заново, и ребро оказывается в сетке (рисунок Вставка ребра). После вставки ребро помечается как ограничение: flip через него запрещён, поэтому никакая последующая перестройка его не разрушит, а условие Делоне вблизи него может законно нарушаться.

В текущей версии проекта ровно эту операцию выполняет CGAL (метод insert_constraint), но логика внутри неё та же.

Почему от схемы отказались

Схема «разделяй и властвуй» опирается на построение выпуклых оболочек, поиск касательных и контроль ориентации — все эти операции сводятся к знаковым геометрическим предикатам, вычисляемым в арифметике с плавающей точкой. На «хороших» входах (общего положения) это работает, но на регулярных, осесимметричных данных, типичных для расчётной области в форме квадрата, возникают вырожденные конфигурации: множество точек на одной вертикали или горизонтали (коллинеарность) и прямоугольные четвёрки точек, лежащие на одной окружности (концикличность). В этих случаях значение предиката оказывается точным нулём, а вычисление в арифметике с плавающей точкой даёт вместо нуля «шум» произвольного знака. Поиск касательных и слияние начинают противоречить сами себе: вдоль границы появляются плоские (нулевой площади) треугольники-«веера», нарушается условие Делоне. Именно эти трудности привели к переходу на библиотечный подход с точными предикатами, описанный в основном тексте.