Триангуляция Делоне и диаграмма Вороного
Также: Delaunay triangulation · Voronoi diagram · диаграмма Вороного · разбиение Дирихле · полигоны Тиссена · алгоритм Бойера — Уотсона · Bowyer–Watson algorithm · флипы Лоусона · Lawson flips · пустая окружность · наибольшая пустая окружность
Зона каждой пожарной части Алматы — точки, для которых она ближайшая, — это диаграмма Вороного, а соседи по зонам соединяются в триангуляцию Делоне, где ни одна точка не лежит внутри описанной окружности чужого треугольника. Как их строят, почему пустые окружности дают самые «круглые» треугольники и при чём тут параболоид.
В OpenStreetMap внутри границы Алматы отмечено 17 пожарных частей. Разделим город на зоны: каждой части достаются точки, до которых ей ближе всех по прямой. Получится диаграмма Вороного — многоугольники, сложенные без щелей. Соединим части, чьи зоны соприкасаются, и получим триангуляцию Делоне: в описанной окружности любого её треугольника нет ни одной другой части. Это одна структура, увиденная с двух сторон, и она отвечает на вопросы, которые иначе пришлось бы решать перебором: какая часть ближайшая, где до ближайшей дальше всего, кого с кем соединить короче всего.
Самая далёкая от частей точка города — на южной границе, в горах: 16,7 км до ближайшей части. Вопрос был задан буквально, и ответ буквальный: граница города захватывает склоны, где никто не живёт. Спросим иначе — какой из 7909 перекрёстков улиц дальше всего от частей — и получим 6,5 км. Алгоритм в обоих случаях один; разный — вопрос.
Идея
Пусть на плоскости даны точки — сайты. Ячейка Вороного сайта — все точки плоскости, для которых он ближе остальных. Точки, равноудалённые от двух сайтов, лежат на серединном перпендикуляре между ними, и ближе к сайту p, чем к q, — полуплоскость по одну сторону от него. Поэтому ячейка — пересечение полуплоскостей, выпуклый многоугольник: именно так сцена выше и строит 17 зон. Граница двух ячеек — кусок серединного перпендикуляра, вершина, где сходятся три ячейки, — точка, равноудалённая от трёх сайтов, то есть центр окружности через них.
Соединим два сайта ребром, если их ячейки имеют общую сторону. Получатся треугольники, у каждого — вершина Вороного в центре описанной окружности. В этой окружности не может быть другого сайта: её центр одинаково далёк от трёх своих сайтов и ближе к ним, чем к любому другому, — иначе он лежал бы в чужой ячейке. Это и есть определение с другой стороны.
Триангуляция Делоне множества точек — триангуляция, в которой описанная окружность каждого треугольника пуста: внутри неё нет ни одной точки множества. Если никакие четыре точки не лежат на одной окружности, такая триангуляция существует и единственна (это видно из подъёма на параболоид ниже), и её рёбра — ровно пары сайтов с общей стороной ячеек Вороного. Если четыре точки на одной окружности, как углы прямоугольника, диагональ можно провести любую: диаграмма Вороного одна, а триангуляций Делоне несколько.
У любой триангуляции n точек, из которых h лежат на границе выпуклой оболочки (вершины и точки на её сторонах), ровно 2n − 2 − h треугольников и 3n − 3 − h рёбер.
Триангуляция — плоский граф: n вершин, E рёбер и F граней, из которых T = F − 1 треугольников и одна внешняя грань. По формуле Эйлера n − E + F = 2. Посчитаем стороны граней: у каждого треугольника три, у внешней грани — h, а каждое ребро — сторона ровно двух граней. Значит, 3T + h = 2E. Подставим F = T + 1 в формулу Эйлера: E = n + T − 1. Тогда 3T + h = 2n + 2T − 2, откуда T = 2n − 2 − h и E = 3n − 3 − h.
Для 17 частей, из которых 5 на оболочке, это 27 треугольников и 43 ребра — у любой триангуляции, не только у Делоне. Важное следствие: и у триангуляции, и у диаграммы Вороного размер линейный — меньше 3n рёбер, хотя пар точек n(n − 1)/2. Всё, что нужно знать о близости точек, помещается в O(n) чисел.
Что лежит внутри
Ребро pq входит в триангуляцию Делоне, если через p и q можно провести окружность, внутри которой нет точек множества: если её раздувать, сохраняя проход через p и q, она упрётся в третью точку и станет описанной окружностью треугольника Делоне. Из этого признака сразу выходят два полезных факта.
Ближайший сосед любой точки — её сосед в триангуляции Делоне. Минимальное остовное дерево точек плоскости целиком состоит из рёбер триангуляции Делоне.
Пусть q — ближайшая к p точка. Окружность с диаметром pq лежит в круге радиуса |pq| с центром p, а внутри этого круга точек нет — иначе нашлась бы точка ближе q. Значит, окружность на диаметре pq пуста, и pq — ребро Делоне.
Пусть ребро pq входит в минимальное остовное дерево, но внутри окружности с диаметром pq есть точка r. Угол prq тогда тупой, и в треугольнике prq сторона pq — самая длинная: |pr| и |rq| меньше |pq|. Выбросим pq из дерева: оно распадётся на две части, p в одной, q в другой, а r — в одной из них, скажем вместе с p. Ребро rq соединяет части, и дерево с ним вместо pq короче — противоречие. Значит, окружность на диаметре pq пуста, и pq — ребро Делоне.
Второй факт превращает задачу о минимальном остовном дереве для точек из «рассмотреть все n(n − 1)/2 пар» в «рассмотреть меньше 3n рёбер». Листинг проверяет это на частях: дерево по 136 парам и по 43 рёбрам Делоне одно и то же, 77,3 км. В статье о минимальном остовном дереве так соединены города целой сети, и там же видно, сколько это экономит.
Третий факт — про наибольшую пустую окружность. Расстояние от точки плоскости до ближайшего сайта внутри одной ячейки Вороного растёт по мере удаления от сайта, поэтому максимум в ограниченной области достигается в вершине Вороного или на краю области — там, где край переходит из одной ячейки в другую, или в вершине края. Это конечный список кандидатов: в первой сцене их 7252 — вершины Вороного внутри города и точки на границах районов, где меняется ближайшая часть.
Как строить: Бойер — Уотсон
Самый простой способ — вставлять точки по одной, поддерживая триангуляцию Делоне уже вставленных. Начнём с огромного треугольника-рамки, внутри которого лежат все точки. Новая точка p попадает внутрь описанных окружностей нескольких треугольников — эти треугольники перестали быть треугольниками Делоне. Уберём их: останется дыра — многоугольник, каждую вершину которого видно из p. Соединим p с каждым ребром края дыры. В конце выбросим треугольники, касающиеся вершин рамки.
Почему новые треугольники — снова Делоне: окружность любого нового треугольника pab пуста, потому что старый треугольник за ребром ab не был выбит, то есть p не попала в его окружность, а через a и b проходят обе окружности. Аккуратное доказательство того, что дыра связна и вся видна из p, — в книге де Берга и соавторов «Вычислительная геометрия»; на наших данных его подтверждает проверка в листинге: все окружности пусты. Для 17 частей по ходу дела выбито 55 треугольников, в среднем по три с небольшим на точку.
Дорого здесь другое — найти выбиваемые треугольники. Простой вариант проверяет все треугольники, и на n точках это порядка n2 проверок. Быстрый находит треугольник, в который попала точка, обходом от предыдущей — шагая через ребро, справа от которого лежит точка, — а остальные выбиваемые ищет только среди соседей: дыра связна. Если вставлять точки в случайном порядке, ожидаемое число выбитых треугольников на точку ограничено константой, а вся работа — O(n log n); это показали Леонидас Гибас, Дональд Кнут и Миша Шарир в 1992 году. Сцена ниже строит так триангуляцию всех перекрёстков центральной части города.
7909 точек дают 15 800 треугольников — ровно 2n − 2 − h, у этого облака на оболочке 16 точек. Каждая вставка выбивает в среднем меньше шести треугольников, и проверок «внутри окружности» около ста тысяч вместо шестидесяти с лишним миллионов у простого варианта. Переключите на ячейки Вороного: улицы видны как цепочки вытянутых ячеек, кварталы — как крупные.
Отдельная тема — точность. Проверка «внутри ли окружности» — знак определителя, и на почти соосных точках — а на сетке улиц таких много — погрешность плавающей точки может его перевернуть, после чего триангуляция ломается: треугольники перекрываются или в ней появляются дыры. Сцена считает знак сначала быстро, в плавающей точке, с оценкой погрешности по Джонатану Шевчуку, а когда оценка не ручается за ответ, пересчитывает в длинной арифметике. Листинг на Python считает сразу в целых числах — координаты в метрах, и ошибок округления там нет.
Флипы: из любой триангуляции
Есть второй путь, и он объясняет, чем триангуляция Делоне хороша. Возьмём любую триангуляцию, например «веер»: точки по возрастанию x, каждая новая соединяется со всеми рёбрами оболочки, которые она видит. Посмотрим на ребро ac между треугольниками abc и acd. Если d внутри окружности abc, ребро плохое: заменим его другой диагональю четырёхугольника, bd. Это флип. Повторяем, пока плохие рёбра есть. Чарлз Лоусон описал этот способ в 1977 году.
У частей веер получается с 15 углами меньше 10°. После 13 флипов таких углов шесть, и получилась ровно триангуляция Делоне. Это не совпадение: среди всех триангуляций данных точек у Делоне наименьший угол наибольший (Лоусон, 1977), а если сравнивать отсортированные углы по порядку — она лучшая по всему списку (Робин Сибсон, 1978). Поэтому её берут для сеток: в методе конечных элементов вытянутые треугольники портят точность, а Делоне избегает их, насколько точки позволяют. Самые маленькие углы, 0,5° и 0,6°, остаются и после флипов. Это один треугольник: три северные части — №19, СПЧ-14 и ПЧ-4 — стоят почти на одной прямой у края оболочки, и раз у Делоне наименьший угол наибольший, у любой другой триангуляции он не больше.
Параболоид
Почему флипы когда-нибудь кончаются и почему пустых окружностей хватает, чтобы триангуляция была одна, видно в трёх измерениях. Поднимем каждую точку (x, y) на параболоид — в точку (x, y, x2 + y2).
Точка d лежит внутри окружности, проходящей через a, b, c, тогда и только тогда, когда поднятая точка d′ лежит ниже плоскости, проходящей через поднятые a′, b′, c′.
Плоскость через a′, b′, c′ — это z = αx + βy + γ при каких-то α, β, γ (она не вертикальна, раз a, b, c не на одной прямой). Поднятая точка (x, y) лежит ниже неё, когда x2 + y2 < αx + βy + γ, то есть (x − α/2)2 + (y − β/2)2 < γ + (α2 + β2)/4. Это внутренность круга. Его граница — точки, где поднятая точка лежит в самой плоскости, а там лежат a′, b′, c′. Значит, это круг, ограниченный окружностью через a, b, c.
Отсюда всё остальное. Треугольник abc — Делоне, когда все поднятые точки выше его плоскости, то есть когда поднятый треугольник — грань нижней стороны выпуклой оболочки поднятых точек. Триангуляция Делоне — проекция нижней оболочки, поэтому она существует, а если никакие четыре поднятые точки не лежат в одной плоскости, то есть никакие четыре точки не на одной окружности, — единственна. Флип плохого ребра заменяет два поднятых треугольника двумя, лежащими ниже: поверхность из треугольников всё время опускается, повториться не может, а триангуляций конечное число — значит, флипы кончаются.
Если в триангуляции нет плохих рёбер, она — триангуляция Делоне.
Поднимем все треугольники на параболоид: получится поверхность над выпуклой оболочкой точек, функция f(x, y), линейная на каждом треугольнике. Ребро не плохое — значит, по утверждению выше, поднятая противоположная вершина соседнего треугольника лежит не ниже плоскости этого треугольника: на каждом ребре поверхность изгибается вверх или не изгибается. Функция, линейная на кусках и выпуклая на каждом стыке кусков, выпукла на всей выпуклой области. Нижняя оболочка поднятых точек — наибольшая выпуклая функция, не превосходящая поднятых значений в самих точках. Наша f выпукла и в точках совпадает с ними, поэтому f не выше оболочки. А оболочка на каждом треугольнике не выше линейной интерполяции значений в его вершинах — по выпуклости, — то есть не выше f. Значит, f и есть нижняя оболочка, а триангуляция — её проекция.
Ту же связь между пустыми окружностями и выпуклыми оболочками заметил Кевин Браун в 1979 году, и она даёт ещё одно следствие: построить триангуляцию Делоне не проще, чем отсортировать числа. Числа x1, …, xn превращаются в точки на параболе, как в статье о выпуклой оболочке, и из триангуляции порядок читается за O(n). Значит, быстрее O(n log n) сравнениями не выйдет.
Код
Листинг строит триангуляцию 17 частей Бойером — Уотсоном в целых числах, проверяет пустоту всех окружностей и формулу Эйлера, сравнивает минимальное остовное дерево по всем парам и по рёбрам Делоне, ищет место, дальше всего от частей, во всём городе и среди перекрёстков, а в конце строит веер и переворачивает в нём рёбра, пока не получится то же самое.
В Go проверка «внутри окружности» с огромной рамкой не помещается в 64 бита, и листинг считает её через math/big; в Python целые числа длинные сами. Поиск самого далёкого места обходит все стороны границ районов: на каждой стороне он начинает с ближайшей части в её начале и находит, где по ходу стороны ближайшей становится другая, — это точки пересечения стороны с рёбрами Вороного.
Сколько это стоит
Выходные данные линейны: меньше 2n треугольников и 3n рёбер. Время зависит от способа.
| Способ | Время | Замечание |
|---|---|---|
| Бойер — Уотсон, проверка всех треугольников | O(n2) | просто, годится для сотен точек |
| Бойер — Уотсон, обход и случайный порядок | O(n log n) в среднем | худший случай O(n2); на практике — самый распространённый |
| флипы Лоусона от произвольной триангуляции | O(n2) флипов в худшем случае | удобны, чтобы чинить сетку после правок |
| заметающая прямая Форчуна | O(n log n) | строит сразу диаграмму Вороного |
| «разделяй и властвуй» | O(n log n) | деление по x и склейка двух триангуляций |
Запрос «ближайший сайт к точке» после построения решается спуском по структуре поиска точки за O(log n); на практике часто проще k-d дерево, а для десятка сайтов — перебор, как в сцене. Память — O(n): у треугольника три вершины и три соседа.
Варианты
По дорогам, а не по прямой. Настоящая зона пожарной части определяется временем в пути. Это диаграмма Вороного на графе: Дейкстра из всех частей сразу, с одной общей очередью, раскрашивает каждый перекрёсток в цвет той части, до которой ближе. Реки, горы и улицы с односторонним движением делают такие зоны совсем не похожими на многоугольники.
С заданными рёбрами. Если некоторые отрезки обязаны войти в триангуляцию — береговая линия, дорога, край детали, — строят ограниченную триангуляцию Делоне: окружности пусты, но точки, заслонённые обязательным ребром, не считаются. Добавляя в нужных местах новые точки, из неё делают сетки, где у всех треугольников углы не меньше заданного, — так работают генераторы сеток для расчётов.
С весами. Если у сайтов разная «сила» — мощность передатчика, размер магазина, — граница ячеек сдвигается или искривляется: так получаются диаграммы мощности и мультипликативно взвешенные диаграммы.
На сфере. Для точек на глобусе подъём не нужен: триангуляция Делоне на сфере — это выпуклая оболочка самих точек в пространстве, по той же причине, по которой окружность на плоскости — сечение параболоида плоскостью.
Где работает
Карты и логистика. Ближайший объект, зона обслуживания, место для нового объекта — задачи этой статьи. Гидрологи считают средние осадки по площади, деля её на зоны станций, — эти зоны у них называются полигонами Тиссена, по имени метеоролога, который предложил их в 1911 году.
Рельеф и интерполяция. По разбросанным точкам с высотами строят поверхность из треугольников — нерегулярную сеть, и для неё берут триангуляцию Делоне: длинные тонкие треугольники связали бы далёкие точки. Робин Сибсон в 1981 году предложил интерполяцию по естественным соседям, которая берёт веса из того, сколько площади отнимает у соседних ячеек Вороного новая точка.
Расчёты. Метод конечных элементов делит деталь на треугольники или тетраэдры, и от формы ячеек зависит точность. Генераторы сеток строят ограниченную триангуляцию Делоне и уточняют её.
Графика и игры. Ячейки Вороного случайных точек дают «клеточную» текстуру — камень, чешую, трещины; функцию, которая по точке возвращает расстояние до ближайшего сайта, Стивен Уорли описал в 1996 году, и она стала стандартным шумом в графике. Генераторы карт делят мир на ячейки Вороного, а путь, который держится подальше от препятствий, идёт по рёбрам диаграммы Вороного.
История
Ячейки ближайшей точки появились в теории чисел. В 1850 году Густав Лежён Дирихле рассматривал их для точек решётки, изучая квадратичные формы, и в части литературы они называются разбиением Дирихле. Георгий Вороной в 1908 году развил теорию для решёток в пространстве любой размерности, и в работах о вычислениях закрепилось его имя. В 1934 году Борис Делоне напечатал статью «Sur la sphère vide» — «О пустой сфере», посвящённую памяти Вороного: в ней и появилось условие пустой окружности и двойственная к ячейкам триангуляция. Независимо те же ячейки находили в метеорологии (Альфред Тиссен, 1911) и в физике кристаллов (Юджин Вигнер и Фредерик Зейтц, 1933).
В информатику диаграммы Вороного привели Майкл Шеймос и Дэн Хоуи в 1975 году: они показали, что многие задачи о близости точек решаются через неё за O(n log n). Флипы Лоусона — 1977 год, свойство наибольшего наименьшего угла у Сибсона — 1978-й, связь с параболоидом у Брауна — 1979-й. Адриан Бойер и Дэвид Уотсон независимо описали вставку с выбиванием треугольников в одном и том же номере журнала The Computer Journal в 1981 году, а Стивен Форчун в 1987 году — заметающую прямую, которая строит диаграмму Вороного сразу. Оценку O(n log n) для случайного порядка вставки доказали Гибас, Кнут и Шарир в 1992 году.
Задачи
Сколько треугольников Где поставить новую частьДанные: Пожарные части Алматы © участники OpenStreetMap, ODbL (выгрузка 17.10.2026) Дороги Алматы © участники OpenStreetMap, ODbL