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

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

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

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

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

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

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

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

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

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

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

• 

  Помещение первой вершины в охватывающий super-triangle

• 

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

• 

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

• 

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

• 

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

• 

  Убираем вершины super-triangle.

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

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

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

Учитывая итерации по объектам, в худшем случае вне зависимости от использования структурирования пространства получается сложность O(|S|²). Однако средняя оценка при структурировании снижается до O(|S| log|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 Построение super-triangle

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

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

   function BowyerWatson (pointList)
      // pointList - множество точек для триангуляции
      triangulation := пустое множество треугольников
      Добавляем super-triangle в триангуляцию
      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 // убираем вершины super-triangle
         if triangle contains a vertex from original super-triangle
            remove triangle from triangulation
      return triangulation

1.6 Pseudocode

The following pseudocode describes a basic implementation of the Bowyer-Watson algorithm. Efficiency can be improved in a number of ways. For example, the triangle connectivity can be used to locate the triangles which contain the new point in their circumcircle, without having to check all of the triangles. Pre-computing the circumcircles can save time at the expense of additional memory usage. And if the points are uniformly distributed, sorting them along a space filling Hilbert curve prior to insertion can also speed point location.

   function BowyerWatson (pointList)
      // pointList is a set of coordinates defining the points to be triangulated
      triangulation := empty triangle mesh data structure
      add super-triangle to triangulation // must be large enough to completely contain all the points in pointList
      for each point in pointList do // add all the points one at a time to the triangulation
         badTriangles := empty set
         for each triangle in triangulation do // first find all the triangles that are no longer valid due to the insertion
            if point is inside circumcircle of triangle
               add triangle to badTriangles
         polygon := empty set
         for each triangle in badTriangles do // find the boundary of the polygonal hole
            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 them from the data structure
            remove triangle from triangulation
         for each edge in polygon do // re-triangulate the polygonal hole
            newTri := form a triangle from edge to point
            add newTri to triangulation
      for each triangle in triangulation // done inserting points, now clean up
         if triangle contains a vertex from original super-triangle
            remove triangle from triangulation
      return triangulation

1.7 See also

• Fortune's algorithm
• Delaunay triangulation
• Computational geometry

1.8 References

• Шаблон:Cite journal
• Шаблон:Cite journal
• Efficient Triangulation Algorithm Suitable for Terrain Modelling generic explanations with source code examples in several languages.

Шаблон:Cite journal

Liu, Yuanxin, and Jack Snoeyink. "A comparison of five implementations of 3D Delaunay tessellation." Combinatorial and Computational Geometry 52 (2005): 439-458.