Алгоритм Боуэра — Ватсона

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

Описание

Алгоритм Боуэра-Ватсона работает путем добавления точек к действительной триангуляции Делоне по одной. После каждой вставки все треугольники, описанные окружности которых содержат точку, удаляются, оставляя многоугольную пустоту, которая повторно триангулируется с использованием следующей точки. Используя связность триангуляции для эффективного определения местоположения треугольников для удаления, алгоритм может выполнить ${\displaystyle {\mathcal {O}}(N\log {N})}$ операций для триангуляции N точек, хотя существуют особые вырожденные случаи, когда это достигает ${\displaystyle {\mathcal {O}}(N^{2})}$^[1].

• 
  Вставьте точку в структуру «супер»-треугольник
• 
  Вставить вторую точку
• 
  Вставьте третью точку
• 
  Вставьте четвертую точку
• 
  Вставьте пятую, последнюю, точку
• 
  Удалите структуру «супер»-треугольника

История

Алгоритм известен так же, как алгоритм Бойера или алгоритм Ватсона. Эдриан Боуэр и Дэвид Ватсон разработали его независимо друг от друга в одно и то же время, и каждый из них опубликовал статью об этом в одном номере журнала The Computer Journal (см. ниже)^[2].

Псевдокод

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

  function BowyerWatson (pointList)
   // pointList - набор координат триангулируемых точек.
   triangulation := empty triangle mesh data structure
   add super-triangle to 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. Rebay, S. Efficient Unstructured Mesh Generation by Means of Delaunay Triangulation and Bowyer-Watson Algorithm. Journal of Computational Physics Volume 106 Issue 1, May 1993, p. 127.
2. Liu, Yuanxin, and Jack Snoeyink. «A comparison of five implementations of 3D Delaunay tessellation.» Combinatorial and Computational Geometry 52 (2005): 439—458.

Ссылки

• RafaelKuebler/DelaunayVoronoi: реализация на языке C#.
• jmespadero/pyDelaunay2D: реализация на языке Python.
• Bl4ckb0ne/delaunay-triangulation: реализация на языке C++.
• Rukh/DelaunayVoronoi2D: реализация на языке Swift.