Вычислительная геометрия

Триангуляция полигонов

Почти каждая 3D-игра, инженерное моделирование и ГИС-система опираются на разбиение областей на треугольники. Треугольник - минимальный строительный блок: любую поверхность, любой полигон можно представить как набор треугольников. Но от качества этих треугольников зависят точность расчётов и скорость рендеринга.

**Конечные элементы (FEM)** - в ANSYS, Abaqus: качество сетки напрямую влияет на точность расчёта напряжений
**Навигационные меши** - в играх (Unity, Unreal): агенты ходят по триангулированным полигонам
**ГИС** - рельеф местности (TIN - Triangulated Irregular Network) строится алгоритмами триангуляции
**Компьютерная графика** - любой полигональный меш - это триангуляция поверхности

Ear Clipping: алгоритм отсечения ушей

Любой простой полигон без дыр можно разбить на треугольники. Но как это сделать алгоритмически? В 1975 году Мейстер доказал: у любого простого полигона с n > 3 вершинами есть хотя бы два «уха» - вершины, треугольник которых полностью лежит внутри полигона. Отрезай ухо, повторяй - получишь n-2 треугольника.

**Теорема Мейстера (Two Ears Theorem):** у каждого простого полигона с n ≥ 4 вершинами есть не менее двух ушей. Исключение - треугольник (n=3), у которого все вершины - уши. Это гарантирует, что алгоритм всегда найдёт ухо и завершится.

Сколько треугольников получится при триангуляции простого полигона с n вершинами?

Монотонный полигон и триангуляция за O(n log n)

Ear Clipping работает за O(n²). Есть способ быстрее: разбить произвольный полигон на монотонные части, а каждую монотонную часть триангулировать за O(n). Алгоритм Ли-Препараты 1977 года даёт O(n log n) для любого простого полигона.

**O(n log n) - оптимальная сложность** для триангуляции в общем случае: нижняя оценка через сортировку доказывает, что быстрее нельзя (для полигонов без дополнительных ограничений на структуру). Алгоритм Чазелля 1991 года - O(n), но столь сложный в реализации, что на практике используют O(n log n).

Полигон является y-монотонным, если:

Constrained Delaunay Triangulation

Обычная триангуляция Делоне максимизирует минимальный угол среди всех треугольников - лучшее качество для численных методов. Но что если есть ограничения: стены здания, берег реки, граница домена? Constrained Delaunay Triangulation (CDT) уважает эти ограничения, оставаясь как можно ближе к Делоне.

**Применения CDT:** конечно-элементное моделирование (FEM), компьютерная графика (навигационные меши), ГИС (рельеф с учётом дорог и рек). Constraints гарантируют, что граница домена точно воспроизведена в сетке - без constraint-ребра триангулятор мог бы 'срезать' угол.

В чём ключевое отличие Constrained Delaunay Triangulation от обычной триангуляции Делоне?

Quality Triangulation и алгоритм Руппера

Для численных методов (конечные элементы, уравнения в частных производных) важно качество треугольников: очень тупые или очень острые треугольники ухудшают точность вычислений. Алгоритм Руппера (1995) строит triangulyation с гарантированным минимальным углом - классически 20.7°.

**Теорема о завершении Руппера:** если нет constraint-рёбер короче определённого порога, алгоритм завершается и производит триангуляцию с минимальным углом ≥ 20.7°. Граница 20.7° не случайна - при большем пороге алгоритм может зациклиться из-за конфликта Steiner-точек.

Зачем алгоритм Руппера добавляет Steiner-точки (центры описанных окружностей плохих треугольников)?