Участник:D.Polykovskiy/Алгоритм Бойера-Ватсона

Алгоритм Бойера–Ватсона --- метод, позволяющий построить триангуляцию Делоне конечного множества точек в пространстве любой размерности. Как следствие, алгоритм позволяет получить диаграму Вороного.

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Алгоритм Бойера–Ватсона позволяет построить триангуляцию Деолне конечного множества точек в пространстве любой размерности. Он относится к семейству инкрементальных, т.е. проводит построение путем поочередного добавления точек, получая при этом на каждом шаге корректную триангуляцию Делоне текущего подмножества точек.

1.2 Математическое описание алгоритма

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

Итерации алгоритма строятся следующим образом: На нулевой итерации строится треугольник (супер-треугольник), покрывающий все точки множества (таким образом множество S пополняется тремя вспомогательными точками). Начальное множество треугольников состоит только из этого треугольника. Далее итеративно выполняются следующие действия:

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

Доказано, что после завершения каждой итерации будет получена корректная триангуляция Делоне.

На последнем шаге алгоритма выкидываются треугольники, содержащие в качестве вершины вспомогательную.

• 

  Помещение первой вершины в охватывающий супер-треугольник

• 

  Вторая вершина

• 

  Третья вершина

• 

  Четвертая вершина

• 

  Пятая вергина

• 

  Убираем вершины супер-треугольника.

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

Большая часть времени работы алгоритма приходится на поиск поврежденных треугольников. В простейшей реализации это делается за O(|S|), однако эта сложность может быть в среднем уменьшена до O(log|S|) при структурировании пространства (нпр., KD-деревом). Тем не менее в худшем случае поиск все равно будет требовать O(|S|) действий.

1.4 Макроструктура алгоритма

1.4.1 Проверка на вхождение в описанную окружность

Для работы алгоритма требуется уметь проверять точку D на принадлежность описанной окружности треугольника ABC. Для двумерного случая это может быть сделано при помощи перехода в 3D пространство по схеме (x, y) -> (x, y, x²+y²) В новом пространстве точке расположены на параболоиде. Утверждается, что четыре точки коцикличны в (x, y) тогда и только тогда, когда они компланарны в пространстве (x, y, x²+y²). Пользуясь выпуклостью парабалоида, можно сформулировать критерий принадлежности точки описанной окружности: достаточно проверить неотрицательность определителя матрицы (предполагается, что точки расположены против часовой стрелки)

[math]\begin{vmatrix} A_x & A_y & A_x^2 + A_y^2 & 1\\ B_x & B_y & B_x^2 + B_y^2 & 1\\ C_x & C_y & C_x^2 + C_y^2 & 1\\ D_x & D_y & D_x^2 + D_y^2 & 1 \end{vmatrix} = \begin{vmatrix} A_x - D_x & A_y - D_y & (A_x^2 - D_x^2) + (A_y^2 - D_y^2) \\ B_x - D_x & B_y - D_y & (B_x^2 - D_x^2) + (B_y^2 - D_y^2) \\ C_x - D_x & C_y - D_y & (C_x^2 - D_x^2) + (C_y^2 - D_y^2) \end{vmatrix} \gt 0 [/math]

1.4.2 Построение супер-треугольника

Построить супер-треугольник можно множеством способов. Например, можно найти разброс (max-min) значений координат точек вдоль каждой из осей. Затем можно вычислить максимальное среди этих значений, обозначив его за w. После этого можно взять центр масс точек S и отступить от него вверх на 2w (точка A), вниз на 2w и влево на 2w (точка B) и, наконец, вниз на 2w и вправо на 2w (точка C). Треугольник ABC будет заведомо содержать все точки из S.

1.4.3 Поиск границы объединения треугольников

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

1.5 Схема реализации последовательного алгоритма

   function BowyerWatson (pointList)
      // pointList - множество точек для триангуляции
      triangulation := пустое множество треугольников
      Добавляем супер-треугольник в триангуляцию
      for each point in pointList do // последовательно добавляем точки
         badTriangles := empty set
         for each triangle in triangulation do // находим поврежденные треугольники
            if point is inside circumcircle of triangle
               add triangle to badTriangles
         polygon := empty set
         for each triangle in badTriangles do // находим границу дырки
            for each edge in triangle do
               if edge is not shared by any other triangles in badTriangles
                  add edge to polygon
         for each triangle in badTriangles do // удаляем поврежденные треугольники
            remove triangle from triangulation
         for each edge in polygon do // заполняем дырку
            newTri := form a triangle from edge to point
            add newTri to triangulation
      for each triangle in triangulation // убираем вершины супер-треугольника
         if triangle contains a vertex from original super-triangle
            remove triangle from triangulation
      return triangulation

1.6 Последовательная сложность алгоритма

В среднем число поврежденных треугольников оказывается малым, поэтому все действия кроме поиска выполняются в среднем за O(1).

В худшем случае вне зависимости от использования структурирования пространства получается сложность O(|S|²). Однако средняя оценка при структурировании снижается до O(|S| log|S|).

1.7 Информационный граф

Информационный граф рассматриваемого алгоритма получается напрямую из его описания:

1.8 Ресурс параллелизма алгоритма

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

1.9 Входные и выходные данные алгоритма

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

2 Программная реализация алгоритма

2.7 Существующие реализации алгоритма

Реализации данного алгоритма не присутствуют в популярных пакетах. Тем не менее, существует несколько доступных реализаций на github:

• https://github.com/axelboc/voronoi-delaunay
• https://github.com/ayron/delaunay
• https://github.com/Bl4ckb0ne/delaunay-triangulation