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

Google Maps показывает ближайший магазин мгновенно среди миллионов объектов. GPS-навигатор делает это с поправкой на пробки в реальном времени. За этим стоят алгоритмы вычислительной геометрии - выпуклые оболочки, диаграммы Вороного, триангуляции.

• **GIS и картография:** PostGIS использует алгоритмы Делоне и Вороного для пространственных запросов в PostgreSQL
• **Компьютерные игры:** mesh navigation для AI персонажей строится через триангуляцию Делоне - основа навигационных сеток
• **Робототехника:** диаграмма Вороного задаёт 'скелет' свободного пространства - траектории, максимально удалённые от препятствий

Предварительные знания

• Coordinate Geometry
• Geometry in Computer Science

Выпуклая оболочка: алгоритмы Джарвиса и Грэма

Google Maps вычисляет границы регионов через выпуклую оболочку за O(n log n) - алгоритм Грэхема на n GPS-точках. Выпуклая оболочка множества точек - наименьшее выпуклое множество, содержащее все точки. Визуально: резинка, натянутая на гвозди. Два классических алгоритма: Джарвис (обход подарка) с O(nh) и Грэм с O(n log n).

Алгоритм Джарвиса (Jarvis march): O(nh), где h - число вершин оболочки. Оптимален когда h мало (h << log n). Алгоритм Грэма: O(n log n) независимо от h. Алгоритм Чана: O(n log h) - оптимальный output-sensitive алгоритм.

Триангуляция Делоне

Триангуляция - разбиение множества точек на треугольники. Триангуляция Делоне - оптимальная: она максимизирует минимальный угол всех треугольников, избегая вырожденных 'тонких' треугольников. Ключевое условие: окружность, описанная вокруг любого треугольника, не содержит других точек.

Ребро AB является ребром Делоне, если для двух треугольников, sharing это ребро (ABC и ABD), точка D не лежит внутри описанной окружности треугольника ABC. Проверяется через determinant 4x4.

Диаграмма Вороного

Диаграмма Вороного для множества точек (сайтов) делит плоскость на области: каждая область содержит точки, ближайшие к одному сайту. Это двойственная структура к триангуляции Делоне: рёбра Вороного перпендикулярны рёбрам Делоне.

Диаграмма Вороного и триангуляция Делоне - двойственные графы: соединим два сайта, если их ячейки Вороного граничат - получим Делоне. Нарисуем центры описанных окружностей Делоне и соединим соседние - получим Вороного. Одна структура немедленно даёт другую.

Алгоритмы в GIS и реальных задачах

Вычислительная геометрия - ядро GIS (Geographic Information Systems), компьютерной графики, роботехники и игровых движков. Алгоритмы выпуклой оболочки, Делоне и Вороного реализованы в CGAL, Shapely, SciPy и PostGIS.

Найти пару ближайших точек за O(n log n): используется divide-and-conquer. Разделить на половины, рекурсивно найти ближайшие пары, потом проверить полосу вдоль линии разделения (не более 8 точек в критической полосе - ключевое наблюдение).

Ключевые идеи

• **Выпуклая оболочка:** Джарвис O(nh) для мало вершин, Грэм O(n log n) - универсальный выбор
• **Критерий Делоне:** описанная окружность треугольника не содержит других точек - максимизирует минимальный угол
• **Алгоритм Форчуна:** sweep line для диаграммы Вороного за O(n log n)
• **Двойственность:** Делоне и Вороного - двойственные структуры, каждая из которых восстанавливает другую

Связанные темы

Вычислительная геометрия объединяет алгоритмы и классическую геометрию:

• Геометрия в Computer Science — Базовые алгоритмы: cross product, point-in-polygon, расстояния
• Координатная геометрия — Аналитическая база для всех вычислений в алгоритмах
• Дискретная геометрия — Упаковки, решётки и дискретные структуры связаны с вычислительными задачами

Вопросы для размышления

• Как диаграмма Вороного применяется при проектировании сети вышек сотовой связи?
• Почему триангуляция Делоне предпочтительна для метода конечных элементов (FEM)?
• Что такое output-sensitive алгоритм и почему алгоритм Чана O(n log h) считается оптимальным для выпуклой оболочки?

Связанные уроки

• alg-12-bfs