Вычислительная геометрия
Триангуляция Делоне
1988 год, ANSYS CFD симуляция течения воздуха вокруг крыла самолёта Boeing 757. Mesh из 2 миллионов тетраэдров построен автоматически алгоритмом Делоне. Без Делоне инженер тратил недели на ручное mesh generation. Алгоритм занял 20 минут. Результат: правильное распределение давления, предсказание lift coefficient с погрешностью 0.3% от экспериментальных данных. Сегодня automotive, aerospace и biomedical индустрия строит физические симуляции на миллиардах тетраэдров через Делоне. Это алгоритм, который проектирует самолёты.
- **Ansys Fluent**: автоматическое 3D mesh generation через Delaunay тетраэдрализацию для CFD симуляций
- **Google Maps Terrain**: триангуляция Делоне для построения terrain mesh из SRTM elevation data (90m resolution)
- **Medical imaging**: Delaunay-based surface reconstruction из МРТ сканов для 3D визуализации органов и хирургического планирования
Борис Делоне (1934)
В 1934 году советский математик Борис Николаевич Делоне (правнук французского альпиниста Огюста Делоне) опубликовал работу 'Sur la sphère vide' (О пустой сфере) в трудах Академии наук СССР. Он описал класс триангуляций с критерием пустого описанного круга в двух измерениях и пустой сферы в трёх. Работа была чисто теоретической. Практическое значение обнаружилось в 1970-е с развитием FEM. Алгоритмы построения: Bowyer-Watson (1981), Fortune (1987). Делоне прожил до 1980 года и увидел практическое применение своей теории - он был и математиком, и альпинистом, и шахматистом. Триангуляция Делоне стала фундаментом computational geometry и FEM mesh generation; через диаграмму Вороного связала половину задач proximity в компьютерных науках
Критерий Делоне: пустой описанный круг
Триангуляция Делоне для множества точек P - такая триангуляция, что для каждого треугольника описанный круг не содержит других точек из P в своём interior. Это максимизирует минимальный угол среди всех треугольников - треугольники становятся 'как можно более равносторонними'. Гарантирует единственность (при отсутствии 4 коциклических точек).
Триангуляция Делоне - двойственный граф **диаграммы Вороного**: центры описанных кругов Делоне треугольников - вершины диаграммы Вороного. Это связывает два важнейших объекта вычислительной геометрии. Применения: mesh generation, interpolation (natural neighbor), terrain modeling, 3D reconstruction.
Почему критерий пустого описанного круга максимизирует минимальный угол треугольников?
Flip операция: локальная оптимизация
**Flip** - локальная операция изменения диагонали в четырёхугольнике, образованном двумя смежными треугольниками. Если диагональ ab нарушает критерий Делоне (точка c или d находится внутри описанного круга треугольника), её 'переворачивают' на cd. Одного флипа достаточно для локального восстановления Делоне.
Теорема Лоусона: любую триангуляцию можно превратить в триангуляцию Делоне последовательными flip операциями. Максимальное число flip'ов: O(n²). Это основа **Incremental Delaunay**: добавить точку, локально нарушить триангуляцию, восстановить флипами.
Когда flip операция применяется к паре треугольников, что именно она изменяет?
Инкрементальный алгоритм: O(n log n)
Инкрементальный алгоритм Делоне: добавлять точки по одной. Для каждой новой точки: 1) найти треугольник, содержащий точку (point location), 2) разбить его на 3 (или 2 при попадании на ребро), 3) выполнить Lawson flip cascade для восстановления Делоне. Ожидаемая сложность: O(n log n) при случайных данных.
**Fortune's sweep line** (1987) - O(n log n) worst-case алгоритм (инкрементальный - O(n²) worst-case при деградации). Fortune обходит плоскость scan line, поддерживая beach line из парабол. Практически оба алгоритма O(n log n) на случайных данных. Scipy использует QHull - один из лучших промышленных вариантов.
Почему инкрементальный алгоритм Делоне требует flip cascade, а не одного flip после вставки точки?
Свойства и применения Делоне
Ключевые свойства триангуляции Делоне: 1) **максимизирует минимальный угол** - нет вырожденных треугольников; 2) **единственна** при отсутствии коциклических точек; 3) **двойственна диаграмме Вороного** - центры описанных кругов = вершины Вороного; 4) содержит **ближайшего соседа**: для каждой точки её ближайший сосед соединён ребром Делоне.
Применения Делоне: **FEM mesh generation** (физические симуляции - CFD, структурный анализ), **Terrain reconstruction** из LiDAR точек, **Natural neighbor interpolation** для карт погоды, **Alpha shapes** для shape reconstruction из точечного облака, **Computational graphics** - Delaunay-based subdivision surfaces.
Триангуляция Делоне минимизирует суммарную длину рёбер (minimum spanning triangulation)
Делоне максимизирует минимальный угол, что не то же самое, что минимизация длины рёбер - задача minimum weight triangulation NP-hard
Greedy edge-length minimization создаёт вырожденные треугольники; Делоне балансирует shape качество через угловой критерий, что полезнее для numerical applications
Почему триангуляция Делоне предпочтительна для Finite Element Method mesh generation?
Ключевые идеи
- **Критерий Делоне**: описанный круг каждого треугольника пуст - максимизирует минимальный угол
- **Flip операция**: замена диагонали в четырёхугольнике восстанавливает локальный критерий Делоне
- **Инкрементальный алгоритм**: O(n log n) ожидаемое время - вставка точки + flip cascade
- **Двойственность с Вороного**: центры описанных кругов = вершины Вороного диаграммы
Вопросы для размышления
- Как суперструктура (super-triangle) в инкрементальном алгоритме влияет на граничные случаи, и как её удаление в конце корректно обрабатывает граничные треугольники?
- При каких конфигурациях 4 точек триангуляция Делоне неоднозначна (оба варианта flip эквивалентны), и как это влияет на алгоритм?
- Почему Fortune's sweep line O(n log n) worst-case, а incremental алгоритм только O(n log n) expected - какие вырожденные случаи ломают incremental?