Алговики - Вклад [ru]

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

2016-11-26T11:50:09Z

D.Polykovskiy: /* Масштабируемость алгоритма и его реализации */

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

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

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

Итерации алгоритма строятся следующим образом:
На нулевой итерации строится треугольник (супер-треугольник), покрывающий все точки множества (таким образом множество S пополняется тремя вспомогательными точками). Начальное множество треугольников состоит только из этого треугольника.
Далее итеративно выполняются следующие действия:
<ol>
<li>Добавляется новая точка</li>
<li>Из множества треугольников выкидываются все треугольники, в описанную окружность в которых попадает новая точка. Таким образом в триангуляции образуется дырка в форме многоугольника.</li>
<li>Эта дырка заполняется треугольниками, содержащими новую точку в качестве одной вершины и ребрами дырки в качестве противолежащей стороны.</li>
</ol>
Доказано, что после завершения каждой итерации будет получена корректная триангуляция Делоне.

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

<gallery>
File:Bowyer-Watson 0.png|Помещение первой вершины в охватывающий супер-треугольник
File:Bowyer-Watson 1.png|Вторая вершина
File:Bowyer-Watson 2.png|Третья вершина
File:Bowyer-Watson 3.png|Четвертая вершина
File:Bowyer-Watson 4.png|Пятая вергина
File:Bowyer-Watson 6.png|Убираем вершины супер-треугольника.
</gallery>

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

==Макроструктура алгоритма==
===Проверка на вхождение в описанную окружность===
Для работы алгоритма требуется уметь проверять точку D на принадлежность описанной окружности треугольника ABC. Для двумерного случая это может быть сделано при помощи перехода в 3D пространство по схеме <math>(x, y) \to (x, y, x^2+y^2)</math><ref>Leonidas J. Guibas, Jorge Stolfi Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics </ref>
В новом пространстве точке расположены на параболоиде. Утверждается, что четыре точки коцикличны в <math>(x, y)</math> тогда и только тогда, когда они компланарны в пространстве <math>(x, y, x^2+y^2)</math>. Пользуясь выпуклостью парабалоида, можно сформулировать критерий принадлежности точки описанной окружности: достаточно проверить неотрицательность определителя матрицы (предполагается, что точки расположены против часовой стрелки)

: <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} > 0
</math>

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

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

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

<syntaxhighlight lang="javascript">
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
</syntaxhighlight>

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

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

==Информационный граф==
Информационный граф рассматриваемого алгоритма получается напрямую из его описания:
[[Файл:BW.png|thumb|center|400px]]
==Ресурс параллелизма алгоритма==
Самая трудоемкая часть алгоритма поиск поврежденных треугольников. Это действие можно распараллелить, проводя проверку на повреждение параллельно для каждого треугольника. Поиск дублирующихся ребер также можно распараллелить, однако эта часть программы не являются ресурсоемкой: количество поврежденных треугольников редко бывает большим.

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

==Свойства алгоритма==

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==

==Масштабируемость алгоритма и его реализации==

Проведём исследование масштабируемости параллельной реализации алгоритма Бойера-Ватсона. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

Запустим реализацию на различных наборах точек и различном числе нитей (по логарифмической сетке), запросив 16 ядер Intel Xeon X5570.

Полученный график сильной масштабируемости приведен ниже.

[[File:BW_run.png]]

Видно, что при увеличении количества нитей, время работы постепенно снижается, однако когда число нитей превышает удвоенное число запрошенных ядер, эффективность реализации снижается. Это происходит из-за нарастающих накладных расходов на параллелизм. Эффект падения эффективности при 32 процессорах и числе точек 2704 связан с особенностью структуры точек: требовался многократный пересчет поврежденных треугольников.

==Динамические характеристики и эффективность реализации алгоритма==

==Выводы для классов архитектур==

==Существующие реализации алгоритма==
Реализации данного алгоритма не присутствуют в популярных пакетах. Тем не менее, существует несколько доступных реализаций на github:
<ul>
<li>https://github.com/axelboc/voronoi-delaunay</li>
<li>https://github.com/ayron/delaunay</li>
<li>https://github.com/Bl4ckb0ne/delaunay-triangulation</li>
</ul>

=Литература=
<ref>C.A.Arens The Bowyer-Watson algorithm: An efficient implementation in a database environment</ref>

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

2016-11-26T11:48:30Z

D.Polykovskiy: /* Масштабируемость алгоритма и его реализации */

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

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

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

Итерации алгоритма строятся следующим образом:
На нулевой итерации строится треугольник (супер-треугольник), покрывающий все точки множества (таким образом множество S пополняется тремя вспомогательными точками). Начальное множество треугольников состоит только из этого треугольника.
Далее итеративно выполняются следующие действия:
<ol>
<li>Добавляется новая точка</li>
<li>Из множества треугольников выкидываются все треугольники, в описанную окружность в которых попадает новая точка. Таким образом в триангуляции образуется дырка в форме многоугольника.</li>
<li>Эта дырка заполняется треугольниками, содержащими новую точку в качестве одной вершины и ребрами дырки в качестве противолежащей стороны.</li>
</ol>
Доказано, что после завершения каждой итерации будет получена корректная триангуляция Делоне.

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

<gallery>
File:Bowyer-Watson 0.png|Помещение первой вершины в охватывающий супер-треугольник
File:Bowyer-Watson 1.png|Вторая вершина
File:Bowyer-Watson 2.png|Третья вершина
File:Bowyer-Watson 3.png|Четвертая вершина
File:Bowyer-Watson 4.png|Пятая вергина
File:Bowyer-Watson 6.png|Убираем вершины супер-треугольника.
</gallery>

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

==Макроструктура алгоритма==
===Проверка на вхождение в описанную окружность===
Для работы алгоритма требуется уметь проверять точку D на принадлежность описанной окружности треугольника ABC. Для двумерного случая это может быть сделано при помощи перехода в 3D пространство по схеме <math>(x, y) \to (x, y, x^2+y^2)</math><ref>Leonidas J. Guibas, Jorge Stolfi Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics </ref>
В новом пространстве точке расположены на параболоиде. Утверждается, что четыре точки коцикличны в <math>(x, y)</math> тогда и только тогда, когда они компланарны в пространстве <math>(x, y, x^2+y^2)</math>. Пользуясь выпуклостью парабалоида, можно сформулировать критерий принадлежности точки описанной окружности: достаточно проверить неотрицательность определителя матрицы (предполагается, что точки расположены против часовой стрелки)

: <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} > 0
</math>

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

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

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

<syntaxhighlight lang="javascript">
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
</syntaxhighlight>

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

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

==Информационный граф==
Информационный граф рассматриваемого алгоритма получается напрямую из его описания:
[[Файл:BW.png|thumb|center|400px]]
==Ресурс параллелизма алгоритма==
Самая трудоемкая часть алгоритма поиск поврежденных треугольников. Это действие можно распараллелить, проводя проверку на повреждение параллельно для каждого треугольника. Поиск дублирующихся ребер также можно распараллелить, однако эта часть программы не являются ресурсоемкой: количество поврежденных треугольников редко бывает большим.

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

==Свойства алгоритма==

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==

==Масштабируемость алгоритма и его реализации==

Проведём исследование масштабируемости параллельной реализации алгоритма Бойера-Ватсона. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

Запустим реализацию на различных наборах точек и различном числе нитей (по логарифмической сетке), запросив 8 ядер Intel Xeon X5570.

Полученный график сильной масштабируемости приведен ниже.

[[File:BW_run.png]]

Видно, что при увеличении количества нитей, время работы постепенно снижается, однако когда число нитей превышает удвоенное число запрошенных ядер, эффективность реализации снижается. Это происходит из-за нарастающих накладных расходов на параллелизм. Эффект падения эффективности при 32 процессорах и числе точек 2704 связан с особенностью структуры точек: требовался многократный пересчет поврежденных треугольников.

==Динамические характеристики и эффективность реализации алгоритма==

==Выводы для классов архитектур==

==Существующие реализации алгоритма==
Реализации данного алгоритма не присутствуют в популярных пакетах. Тем не менее, существует несколько доступных реализаций на github:
<ul>
<li>https://github.com/axelboc/voronoi-delaunay</li>
<li>https://github.com/ayron/delaunay</li>
<li>https://github.com/Bl4ckb0ne/delaunay-triangulation</li>
</ul>

=Литература=
<ref>C.A.Arens The Bowyer-Watson algorithm: An efficient implementation in a database environment</ref>

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

2016-11-18T09:13:57Z

D.Polykovskiy: /* Масштабируемость алгоритма и его реализации */

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

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

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

Итерации алгоритма строятся следующим образом:
На нулевой итерации строится треугольник (супер-треугольник), покрывающий все точки множества (таким образом множество S пополняется тремя вспомогательными точками). Начальное множество треугольников состоит только из этого треугольника.
Далее итеративно выполняются следующие действия:
<ol>
<li>Добавляется новая точка</li>
<li>Из множества треугольников выкидываются все треугольники, в описанную окружность в которых попадает новая точка. Таким образом в триангуляции образуется дырка в форме многоугольника.</li>
<li>Эта дырка заполняется треугольниками, содержащими новую точку в качестве одной вершины и ребрами дырки в качестве противолежащей стороны.</li>
</ol>
Доказано, что после завершения каждой итерации будет получена корректная триангуляция Делоне.

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

<gallery>
File:Bowyer-Watson 0.png|Помещение первой вершины в охватывающий супер-треугольник
File:Bowyer-Watson 1.png|Вторая вершина
File:Bowyer-Watson 2.png|Третья вершина
File:Bowyer-Watson 3.png|Четвертая вершина
File:Bowyer-Watson 4.png|Пятая вергина
File:Bowyer-Watson 6.png|Убираем вершины супер-треугольника.
</gallery>

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

==Макроструктура алгоритма==
===Проверка на вхождение в описанную окружность===
Для работы алгоритма требуется уметь проверять точку D на принадлежность описанной окружности треугольника ABC. Для двумерного случая это может быть сделано при помощи перехода в 3D пространство по схеме <math>(x, y) \to (x, y, x^2+y^2)</math><ref>Leonidas J. Guibas, Jorge Stolfi Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics </ref>
В новом пространстве точке расположены на параболоиде. Утверждается, что четыре точки коцикличны в <math>(x, y)</math> тогда и только тогда, когда они компланарны в пространстве <math>(x, y, x^2+y^2)</math>. Пользуясь выпуклостью парабалоида, можно сформулировать критерий принадлежности точки описанной окружности: достаточно проверить неотрицательность определителя матрицы (предполагается, что точки расположены против часовой стрелки)

: <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} > 0
</math>

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

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

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

<syntaxhighlight lang="javascript">
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
</syntaxhighlight>

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

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

==Информационный граф==
Информационный граф рассматриваемого алгоритма получается напрямую из его описания:
[[Файл:BW.png|thumb|center|400px]]
==Ресурс параллелизма алгоритма==
Самая трудоемкая часть алгоритма поиск поврежденных треугольников. Это действие можно распараллелить, проводя проверку на повреждение параллельно для каждого треугольника. Поиск дублирующихся ребер также можно распараллелить, однако эта часть программы не являются ресурсоемкой: количество поврежденных треугольников редко бывает большим.

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

==Свойства алгоритма==

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==

==Масштабируемость алгоритма и его реализации==

Проведём исследование масштабируемости параллельной реализации алгоритма Бойера-Ватсона согласно [[Scalability methodology|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

Запустим реализацию на различных наборах точек и различном числе нитей (по логарифмической сетке), запросив 8 ядер Intel Xeon X5570.

Полученный график сильной масштабируемости приведен ниже.

[[File:BW_run.png]]

Видно, что при увеличении количества нитей, время работы постепенно снижается, однако когда число нитей превышает удвоенное число запрошенных ядер, эффективность реализации снижается. Это происходит из-за нарастающих накладных расходов на параллелизм. Эффект падения эффективности при 32 процессорах и числе точек 2704 связан с особенностью структуры точек: требовался многократный пересчет поврежденных треугольников.

==Динамические характеристики и эффективность реализации алгоритма==

==Выводы для классов архитектур==

==Существующие реализации алгоритма==
Реализации данного алгоритма не присутствуют в популярных пакетах. Тем не менее, существует несколько доступных реализаций на github:
<ul>
<li>https://github.com/axelboc/voronoi-delaunay</li>
<li>https://github.com/ayron/delaunay</li>
<li>https://github.com/Bl4ckb0ne/delaunay-triangulation</li>
</ul>

=Литература=
<ref>C.A.Arens The Bowyer-Watson algorithm: An efficient implementation in a database environment</ref>

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

2016-11-18T09:12:24Z

D.Polykovskiy: /* Последовательная сложность алгоритма */

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

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

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

Итерации алгоритма строятся следующим образом:
На нулевой итерации строится треугольник (супер-треугольник), покрывающий все точки множества (таким образом множество S пополняется тремя вспомогательными точками). Начальное множество треугольников состоит только из этого треугольника.
Далее итеративно выполняются следующие действия:
<ol>
<li>Добавляется новая точка</li>
<li>Из множества треугольников выкидываются все треугольники, в описанную окружность в которых попадает новая точка. Таким образом в триангуляции образуется дырка в форме многоугольника.</li>
<li>Эта дырка заполняется треугольниками, содержащими новую точку в качестве одной вершины и ребрами дырки в качестве противолежащей стороны.</li>
</ol>
Доказано, что после завершения каждой итерации будет получена корректная триангуляция Делоне.

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

<gallery>
File:Bowyer-Watson 0.png|Помещение первой вершины в охватывающий супер-треугольник
File:Bowyer-Watson 1.png|Вторая вершина
File:Bowyer-Watson 2.png|Третья вершина
File:Bowyer-Watson 3.png|Четвертая вершина
File:Bowyer-Watson 4.png|Пятая вергина
File:Bowyer-Watson 6.png|Убираем вершины супер-треугольника.
</gallery>

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

==Макроструктура алгоритма==
===Проверка на вхождение в описанную окружность===
Для работы алгоритма требуется уметь проверять точку D на принадлежность описанной окружности треугольника ABC. Для двумерного случая это может быть сделано при помощи перехода в 3D пространство по схеме <math>(x, y) \to (x, y, x^2+y^2)</math><ref>Leonidas J. Guibas, Jorge Stolfi Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics </ref>
В новом пространстве точке расположены на параболоиде. Утверждается, что четыре точки коцикличны в <math>(x, y)</math> тогда и только тогда, когда они компланарны в пространстве <math>(x, y, x^2+y^2)</math>. Пользуясь выпуклостью парабалоида, можно сформулировать критерий принадлежности точки описанной окружности: достаточно проверить неотрицательность определителя матрицы (предполагается, что точки расположены против часовой стрелки)

: <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} > 0
</math>

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

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

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

<syntaxhighlight lang="javascript">
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
</syntaxhighlight>

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

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

==Информационный граф==
Информационный граф рассматриваемого алгоритма получается напрямую из его описания:
[[Файл:BW.png|thumb|center|400px]]
==Ресурс параллелизма алгоритма==
Самая трудоемкая часть алгоритма поиск поврежденных треугольников. Это действие можно распараллелить, проводя проверку на повреждение параллельно для каждого треугольника. Поиск дублирующихся ребер также можно распараллелить, однако эта часть программы не являются ресурсоемкой: количество поврежденных треугольников редко бывает большим.

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

==Свойства алгоритма==

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==

==Масштабируемость алгоритма и его реализации==

Проведём исследование масштабируемости параллельной реализации разложения Холецкого согласно [[Scalability methodology|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

Запустим реализацию на различных наборах точек и различном числе нитей (по логарифмической сетке), запросив 8 ядер Intel Xeon X5570.

Полученный график сильной масштабируемости приведен ниже.

[[File:BW_run.png]]

Видно, что при увеличении количества нитей, время работы постепенно снижается, однако когда число нитей превышает удвоенное число запрошенных ядер, эффективность реализации снижается. Это происходит из-за нарастающих накладных расходов на параллелизм. Эффект падения эффективности при 32 процессорах и числе точек 2704 связан с особенностью структуры точек: требовался многократный пересчет поврежденных треугольников.

==Динамические характеристики и эффективность реализации алгоритма==

==Выводы для классов архитектур==

==Существующие реализации алгоритма==
Реализации данного алгоритма не присутствуют в популярных пакетах. Тем не менее, существует несколько доступных реализаций на github:
<ul>
<li>https://github.com/axelboc/voronoi-delaunay</li>
<li>https://github.com/ayron/delaunay</li>
<li>https://github.com/Bl4ckb0ne/delaunay-triangulation</li>
</ul>

=Литература=
<ref>C.A.Arens The Bowyer-Watson algorithm: An efficient implementation in a database environment</ref>

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

2016-11-18T09:11:10Z

D.Polykovskiy: /* Проверка на вхождение в описанную окружность */

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

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

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

Итерации алгоритма строятся следующим образом:
На нулевой итерации строится треугольник (супер-треугольник), покрывающий все точки множества (таким образом множество S пополняется тремя вспомогательными точками). Начальное множество треугольников состоит только из этого треугольника.
Далее итеративно выполняются следующие действия:
<ol>
<li>Добавляется новая точка</li>
<li>Из множества треугольников выкидываются все треугольники, в описанную окружность в которых попадает новая точка. Таким образом в триангуляции образуется дырка в форме многоугольника.</li>
<li>Эта дырка заполняется треугольниками, содержащими новую точку в качестве одной вершины и ребрами дырки в качестве противолежащей стороны.</li>
</ol>
Доказано, что после завершения каждой итерации будет получена корректная триангуляция Делоне.

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

<gallery>
File:Bowyer-Watson 0.png|Помещение первой вершины в охватывающий супер-треугольник
File:Bowyer-Watson 1.png|Вторая вершина
File:Bowyer-Watson 2.png|Третья вершина
File:Bowyer-Watson 3.png|Четвертая вершина
File:Bowyer-Watson 4.png|Пятая вергина
File:Bowyer-Watson 6.png|Убираем вершины супер-треугольника.
</gallery>

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

==Макроструктура алгоритма==
===Проверка на вхождение в описанную окружность===
Для работы алгоритма требуется уметь проверять точку D на принадлежность описанной окружности треугольника ABC. Для двумерного случая это может быть сделано при помощи перехода в 3D пространство по схеме <math>(x, y) \to (x, y, x^2+y^2)</math><ref>Leonidas J. Guibas, Jorge Stolfi Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics </ref>
В новом пространстве точке расположены на параболоиде. Утверждается, что четыре точки коцикличны в <math>(x, y)</math> тогда и только тогда, когда они компланарны в пространстве <math>(x, y, x^2+y^2)</math>. Пользуясь выпуклостью парабалоида, можно сформулировать критерий принадлежности точки описанной окружности: достаточно проверить неотрицательность определителя матрицы (предполагается, что точки расположены против часовой стрелки)

: <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} > 0
</math>

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

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

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

<syntaxhighlight lang="javascript">
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
</syntaxhighlight>

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

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

==Информационный граф==
Информационный граф рассматриваемого алгоритма получается напрямую из его описания:
[[Файл:BW.png|thumb|center|400px]]
==Ресурс параллелизма алгоритма==
Самая трудоемкая часть алгоритма поиск поврежденных треугольников. Это действие можно распараллелить, проводя проверку на повреждение параллельно для каждого треугольника. Поиск дублирующихся ребер также можно распараллелить, однако эта часть программы не являются ресурсоемкой: количество поврежденных треугольников редко бывает большим.

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

==Свойства алгоритма==

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==

==Масштабируемость алгоритма и его реализации==

Проведём исследование масштабируемости параллельной реализации разложения Холецкого согласно [[Scalability methodology|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

Запустим реализацию на различных наборах точек и различном числе нитей (по логарифмической сетке), запросив 8 ядер Intel Xeon X5570.

Полученный график сильной масштабируемости приведен ниже.

[[File:BW_run.png]]

Видно, что при увеличении количества нитей, время работы постепенно снижается, однако когда число нитей превышает удвоенное число запрошенных ядер, эффективность реализации снижается. Это происходит из-за нарастающих накладных расходов на параллелизм. Эффект падения эффективности при 32 процессорах и числе точек 2704 связан с особенностью структуры точек: требовался многократный пересчет поврежденных треугольников.

==Динамические характеристики и эффективность реализации алгоритма==

==Выводы для классов архитектур==

==Существующие реализации алгоритма==
Реализации данного алгоритма не присутствуют в популярных пакетах. Тем не менее, существует несколько доступных реализаций на github:
<ul>
<li>https://github.com/axelboc/voronoi-delaunay</li>
<li>https://github.com/ayron/delaunay</li>
<li>https://github.com/Bl4ckb0ne/delaunay-triangulation</li>
</ul>

=Литература=
<ref>C.A.Arens The Bowyer-Watson algorithm: An efficient implementation in a database environment</ref>

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

2016-11-18T09:09:52Z

D.Polykovskiy: /* Вычислительное ядро алгоритма */

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

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

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

Итерации алгоритма строятся следующим образом:
На нулевой итерации строится треугольник (супер-треугольник), покрывающий все точки множества (таким образом множество S пополняется тремя вспомогательными точками). Начальное множество треугольников состоит только из этого треугольника.
Далее итеративно выполняются следующие действия:
<ol>
<li>Добавляется новая точка</li>
<li>Из множества треугольников выкидываются все треугольники, в описанную окружность в которых попадает новая точка. Таким образом в триангуляции образуется дырка в форме многоугольника.</li>
<li>Эта дырка заполняется треугольниками, содержащими новую точку в качестве одной вершины и ребрами дырки в качестве противолежащей стороны.</li>
</ol>
Доказано, что после завершения каждой итерации будет получена корректная триангуляция Делоне.

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

<gallery>
File:Bowyer-Watson 0.png|Помещение первой вершины в охватывающий супер-треугольник
File:Bowyer-Watson 1.png|Вторая вершина
File:Bowyer-Watson 2.png|Третья вершина
File:Bowyer-Watson 3.png|Четвертая вершина
File:Bowyer-Watson 4.png|Пятая вергина
File:Bowyer-Watson 6.png|Убираем вершины супер-треугольника.
</gallery>

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

==Макроструктура алгоритма==
===Проверка на вхождение в описанную окружность===
Для работы алгоритма требуется уметь проверять точку D на принадлежность описанной окружности треугольника ABC. Для двумерного случая это может быть сделано при помощи перехода в 3D пространство по схеме ''(x, y) -> (x, y, x2+y2)''<ref>Leonidas J. Guibas, Jorge Stolfi Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics </ref>
В новом пространстве точке расположены на параболоиде. Утверждается, что четыре точки коцикличны в ''(x, y)'' тогда и только тогда, когда они компланарны в пространстве ''(x, y, x2+y2)''. Пользуясь выпуклостью парабалоида, можно сформулировать критерий принадлежности точки описанной окружности: достаточно проверить неотрицательность определителя матрицы (предполагается, что точки расположены против часовой стрелки)

: <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} > 0
</math>

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

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

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

<syntaxhighlight lang="javascript">
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
</syntaxhighlight>

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

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

==Информационный граф==
Информационный граф рассматриваемого алгоритма получается напрямую из его описания:
[[Файл:BW.png|thumb|center|400px]]
==Ресурс параллелизма алгоритма==
Самая трудоемкая часть алгоритма поиск поврежденных треугольников. Это действие можно распараллелить, проводя проверку на повреждение параллельно для каждого треугольника. Поиск дублирующихся ребер также можно распараллелить, однако эта часть программы не являются ресурсоемкой: количество поврежденных треугольников редко бывает большим.

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

==Свойства алгоритма==

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==

==Масштабируемость алгоритма и его реализации==

Проведём исследование масштабируемости параллельной реализации разложения Холецкого согласно [[Scalability methodology|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

Запустим реализацию на различных наборах точек и различном числе нитей (по логарифмической сетке), запросив 8 ядер Intel Xeon X5570.

Полученный график сильной масштабируемости приведен ниже.

[[File:BW_run.png]]

Видно, что при увеличении количества нитей, время работы постепенно снижается, однако когда число нитей превышает удвоенное число запрошенных ядер, эффективность реализации снижается. Это происходит из-за нарастающих накладных расходов на параллелизм. Эффект падения эффективности при 32 процессорах и числе точек 2704 связан с особенностью структуры точек: требовался многократный пересчет поврежденных треугольников.

==Динамические характеристики и эффективность реализации алгоритма==

==Выводы для классов архитектур==

==Существующие реализации алгоритма==
Реализации данного алгоритма не присутствуют в популярных пакетах. Тем не менее, существует несколько доступных реализаций на github:
<ul>
<li>https://github.com/axelboc/voronoi-delaunay</li>
<li>https://github.com/ayron/delaunay</li>
<li>https://github.com/Bl4ckb0ne/delaunay-triangulation</li>
</ul>

=Литература=
<ref>C.A.Arens The Bowyer-Watson algorithm: An efficient implementation in a database environment</ref>

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

2016-11-18T09:06:11Z

D.Polykovskiy:

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

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

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

Итерации алгоритма строятся следующим образом:
На нулевой итерации строится треугольник (супер-треугольник), покрывающий все точки множества (таким образом множество S пополняется тремя вспомогательными точками). Начальное множество треугольников состоит только из этого треугольника.
Далее итеративно выполняются следующие действия:
<ol>
<li>Добавляется новая точка</li>
<li>Из множества треугольников выкидываются все треугольники, в описанную окружность в которых попадает новая точка. Таким образом в триангуляции образуется дырка в форме многоугольника.</li>
<li>Эта дырка заполняется треугольниками, содержащими новую точку в качестве одной вершины и ребрами дырки в качестве противолежащей стороны.</li>
</ol>
Доказано, что после завершения каждой итерации будет получена корректная триангуляция Делоне.

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

<gallery>
File:Bowyer-Watson 0.png|Помещение первой вершины в охватывающий супер-треугольник
File:Bowyer-Watson 1.png|Вторая вершина
File:Bowyer-Watson 2.png|Третья вершина
File:Bowyer-Watson 3.png|Четвертая вершина
File:Bowyer-Watson 4.png|Пятая вергина
File:Bowyer-Watson 6.png|Убираем вершины супер-треугольника.
</gallery>

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

==Макроструктура алгоритма==
===Проверка на вхождение в описанную окружность===
Для работы алгоритма требуется уметь проверять точку D на принадлежность описанной окружности треугольника ABC. Для двумерного случая это может быть сделано при помощи перехода в 3D пространство по схеме ''(x, y) -> (x, y, x2+y2)''<ref>Leonidas J. Guibas, Jorge Stolfi Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics </ref>
В новом пространстве точке расположены на параболоиде. Утверждается, что четыре точки коцикличны в ''(x, y)'' тогда и только тогда, когда они компланарны в пространстве ''(x, y, x2+y2)''. Пользуясь выпуклостью парабалоида, можно сформулировать критерий принадлежности точки описанной окружности: достаточно проверить неотрицательность определителя матрицы (предполагается, что точки расположены против часовой стрелки)

: <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} > 0
</math>

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

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

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

<syntaxhighlight lang="javascript">
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
</syntaxhighlight>

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

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

==Информационный граф==
Информационный граф рассматриваемого алгоритма получается напрямую из его описания:
[[Файл:BW.png|thumb|center|400px]]
==Ресурс параллелизма алгоритма==
Самая трудоемкая часть алгоритма поиск поврежденных треугольников. Это действие можно распараллелить, проводя проверку на повреждение параллельно для каждого треугольника. Поиск дублирующихся ребер также можно распараллелить, однако эта часть программы не являются ресурсоемкой: количество поврежденных треугольников редко бывает большим.

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

==Свойства алгоритма==

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==

==Масштабируемость алгоритма и его реализации==

Проведём исследование масштабируемости параллельной реализации разложения Холецкого согласно [[Scalability methodology|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

Запустим реализацию на различных наборах точек и различном числе нитей (по логарифмической сетке), запросив 8 ядер Intel Xeon X5570.

Полученный график сильной масштабируемости приведен ниже.

[[File:BW_run.png]]

Видно, что при увеличении количества нитей, время работы постепенно снижается, однако когда число нитей превышает удвоенное число запрошенных ядер, эффективность реализации снижается. Это происходит из-за нарастающих накладных расходов на параллелизм. Эффект падения эффективности при 32 процессорах и числе точек 2704 связан с особенностью структуры точек: требовался многократный пересчет поврежденных треугольников.

==Динамические характеристики и эффективность реализации алгоритма==

==Выводы для классов архитектур==

==Существующие реализации алгоритма==
Реализации данного алгоритма не присутствуют в популярных пакетах. Тем не менее, существует несколько доступных реализаций на github:
<ul>
<li>https://github.com/axelboc/voronoi-delaunay</li>
<li>https://github.com/ayron/delaunay</li>
<li>https://github.com/Bl4ckb0ne/delaunay-triangulation</li>
</ul>

=Литература=
<ref>C.A.Arens The Bowyer-Watson algorithm: An efficient implementation in a database environment</ref>

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

2016-11-18T07:59:17Z

D.Polykovskiy: /* Масштабируемость алгоритма и его реализации */

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

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

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

Итерации алгоритма строятся следующим образом:
На нулевой итерации строится треугольник (супер-треугольник), покрывающий все точки множества (таким образом множество S пополняется тремя вспомогательными точками). Начальное множество треугольников состоит только из этого треугольника.
Далее итеративно выполняются следующие действия:
<ol>
<li>Добавляется новая точка</li>
<li>Из множества треугольников выкидываются все треугольники, в описанную окружность в которых попадает новая точка. Таким образом в триангуляции образуется дырка в форме многоугольника.</li>
<li>Эта дырка заполняется треугольниками, содержащими новую точку в качестве одной вершины и ребрами дырки в качестве противолежащей стороны.</li>
</ol>
Доказано, что после завершения каждой итерации будет получена корректная триангуляция Делоне.

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

<gallery>
File:Bowyer-Watson 0.png|Помещение первой вершины в охватывающий супер-треугольник
File:Bowyer-Watson 1.png|Вторая вершина
File:Bowyer-Watson 2.png|Третья вершина
File:Bowyer-Watson 3.png|Четвертая вершина
File:Bowyer-Watson 4.png|Пятая вергина
File:Bowyer-Watson 6.png|Убираем вершины супер-треугольника.
</gallery>

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

==Макроструктура алгоритма==
===Проверка на вхождение в описанную окружность===
Для работы алгоритма требуется уметь проверять точку D на принадлежность описанной окружности треугольника ABC. Для двумерного случая это может быть сделано при помощи перехода в 3D пространство по схеме ''(x, y) -> (x, y, x2+y2)''<ref>Leonidas J. Guibas, Jorge Stolfi Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics </ref>
В новом пространстве точке расположены на параболоиде. Утверждается, что четыре точки коцикличны в ''(x, y)'' тогда и только тогда, когда они компланарны в пространстве ''(x, y, x2+y2)''. Пользуясь выпуклостью парабалоида, можно сформулировать критерий принадлежности точки описанной окружности: достаточно проверить неотрицательность определителя матрицы (предполагается, что точки расположены против часовой стрелки)

: <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} > 0
</math>

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

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

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

<syntaxhighlight lang="javascript">
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
</syntaxhighlight>

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

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

==Информационный граф==
Информационный граф рассматриваемого алгоритма получается напрямую из его описания:
[[Файл:BW.png|thumb|center|400px]]
==Ресурс параллелизма алгоритма==
Самая трудоемкая часть алгоритма поиск поврежденных треугольников. Это действие можно распараллелить, проводя проверку на повреждение параллельно для каждого треугольника. Поиск дублирующихся ребер также можно распараллелить, однако эта часть программы не являются ресурсоемкой: количество поврежденных треугольников редко бывает большим.

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

==Свойства алгоритма==

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==

==Масштабируемость алгоритма и его реализации==

Проведём исследование масштабируемости параллельной реализации разложения Холецкого согласно [[Scalability methodology|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

Запустим реализацию на различных наборах точек и различном числе нитей (по логарифмической сетке), запросив 8 ядер Intel Xeon X5570.

Полученный график сильной масштабируемости приведен ниже.

[[File:BW_run.png]]

Видно, что при увеличении количества нитей, время работы постепенно снижается, однако когда число нитей превышает удвоенное число запрошенных ядер, эффективность реализации снижается. Это происходит из-за нарастающих накладных расходов на параллелизм. Эффект падения эффективности при 32 процессорах и числе точек 2704 связан с особенностью структуры точек: требовался многократный пересчет поврежденных треугольников.

==Динамические характеристики и эффективность реализации алгоритма==

==Выводы для классов архитектур==

==Существующие реализации алгоритма==
Реализации данного алгоритма не присутствуют в популярных пакетах. Тем не менее, существует несколько доступных реализаций на github:
<ul>
<li>https://github.com/axelboc/voronoi-delaunay</li>
<li>https://github.com/ayron/delaunay</li>
<li>https://github.com/Bl4ckb0ne/delaunay-triangulation</li>
</ul>

=Литература=
<ref>C.A.Arens The Bowyer-Watson algorithm: An efficient implementation in a database environment</ref>

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

2016-11-15T22:56:09Z

D.Polykovskiy:

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

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

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

Итерации алгоритма строятся следующим образом:
На нулевой итерации строится треугольник (супер-треугольник), покрывающий все точки множества (таким образом множество S пополняется тремя вспомогательными точками). Начальное множество треугольников состоит только из этого треугольника.
Далее итеративно выполняются следующие действия:
<ol>
<li>Добавляется новая точка</li>
<li>Из множества треугольников выкидываются все треугольники, в описанную окружность в которых попадает новая точка. Таким образом в триангуляции образуется дырка в форме многоугольника.</li>
<li>Эта дырка заполняется треугольниками, содержащими новую точку в качестве одной вершины и ребрами дырки в качестве противолежащей стороны.</li>
</ol>
Доказано, что после завершения каждой итерации будет получена корректная триангуляция Делоне.

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

<gallery>
File:Bowyer-Watson 0.png|Помещение первой вершины в охватывающий супер-треугольник
File:Bowyer-Watson 1.png|Вторая вершина
File:Bowyer-Watson 2.png|Третья вершина
File:Bowyer-Watson 3.png|Четвертая вершина
File:Bowyer-Watson 4.png|Пятая вергина
File:Bowyer-Watson 6.png|Убираем вершины супер-треугольника.
</gallery>

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

==Макроструктура алгоритма==
===Проверка на вхождение в описанную окружность===
Для работы алгоритма требуется уметь проверять точку D на принадлежность описанной окружности треугольника ABC. Для двумерного случая это может быть сделано при помощи перехода в 3D пространство по схеме ''(x, y) -> (x, y, x2+y2)''<ref>Leonidas J. Guibas, Jorge Stolfi Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics </ref>
В новом пространстве точке расположены на параболоиде. Утверждается, что четыре точки коцикличны в ''(x, y)'' тогда и только тогда, когда они компланарны в пространстве ''(x, y, x2+y2)''. Пользуясь выпуклостью парабалоида, можно сформулировать критерий принадлежности точки описанной окружности: достаточно проверить неотрицательность определителя матрицы (предполагается, что точки расположены против часовой стрелки)

: <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} > 0
</math>

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

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

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

<syntaxhighlight lang="javascript">
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
</syntaxhighlight>

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

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

==Информационный граф==
Информационный граф рассматриваемого алгоритма получается напрямую из его описания:
[[Файл:BW.png|thumb|center|400px]]
==Ресурс параллелизма алгоритма==
Самая трудоемкая часть алгоритма поиск поврежденных треугольников. Это действие можно распараллелить, проводя проверку на повреждение параллельно для каждого треугольника. Поиск дублирующихся ребер также можно распараллелить, однако эта часть программы не являются ресурсоемкой: количество поврежденных треугольников редко бывает большим.

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

==Свойства алгоритма==

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==

==Масштабируемость алгоритма и его реализации==

==Динамические характеристики и эффективность реализации алгоритма==

==Выводы для классов архитектур==

==Существующие реализации алгоритма==
Реализации данного алгоритма не присутствуют в популярных пакетах. Тем не менее, существует несколько доступных реализаций на github:
<ul>
<li>https://github.com/axelboc/voronoi-delaunay</li>
<li>https://github.com/ayron/delaunay</li>
<li>https://github.com/Bl4ckb0ne/delaunay-triangulation</li>
</ul>

=Литература=
<ref>C.A.Arens The Bowyer-Watson algorithm: An efficient implementation in a database environment</ref>

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

2016-11-15T21:06:18Z

D.Polykovskiy: /* Ресурс параллелизма алгоритма */

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

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

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

Итерации алгоритма строятся следующим образом:
На нулевой итерации строится треугольник (супер-треугольник), покрывающий все точки множества (таким образом множество S пополняется тремя вспомогательными точками). Начальное множество треугольников состоит только из этого треугольника.
Далее итеративно выполняются следующие действия:
<ol>
<li>Добавляется новая точка</li>
<li>Из множества треугольников выкидываются все треугольники, в описанную окружность в которых попадает новая точка. Таким образом в триангуляции образуется дырка в форме многоугольника.</li>
<li>Эта дырка заполняется треугольниками, содержащими новую точку в качестве одной вершины и ребрами дырки в качестве противолежащей стороны.</li>
</ol>
Доказано, что после завершения каждой итерации будет получена корректная триангуляция Делоне.

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

<gallery>
File:Bowyer-Watson 0.png|Помещение первой вершины в охватывающий супер-треугольник
File:Bowyer-Watson 1.png|Вторая вершина
File:Bowyer-Watson 2.png|Третья вершина
File:Bowyer-Watson 3.png|Четвертая вершина
File:Bowyer-Watson 4.png|Пятая вергина
File:Bowyer-Watson 6.png|Убираем вершины супер-треугольника.
</gallery>

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

==Макроструктура алгоритма==
===Проверка на вхождение в описанную окружность===
Для работы алгоритма требуется уметь проверять точку D на принадлежность описанной окружности треугольника ABC. Для двумерного случая это может быть сделано при помощи перехода в 3D пространство по схеме ''(x, y) -> (x, y, x2+y2)''<ref>Leonidas J. Guibas, Jorge Stolfi Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics </ref>
В новом пространстве точке расположены на параболоиде. Утверждается, что четыре точки коцикличны в ''(x, y)'' тогда и только тогда, когда они компланарны в пространстве ''(x, y, x2+y2)''. Пользуясь выпуклостью парабалоида, можно сформулировать критерий принадлежности точки описанной окружности: достаточно проверить неотрицательность определителя матрицы (предполагается, что точки расположены против часовой стрелки)

: <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} > 0
</math>

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

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

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

<syntaxhighlight lang="javascript">
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
</syntaxhighlight>

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

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

==Информационный граф==
Информационный граф рассматриваемого алгоритма получается напрямую из его описания:
[[Файл:BW.png|thumb|center|400px]]
==Ресурс параллелизма алгоритма==
Самая трудоемкая часть алгоритма поиск поврежденных треугольников. Это действие можно распараллелить, проводя проверку на повреждение параллельно для каждого треугольника. Поиск дублирующихся ребер также можно распараллелить, однако эта часть программы не являются ресурсоемкой: количество поврежденных треугольников редко бывает большим.

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

=Программная реализация алгоритма=
==Масштабируемость алгоритма и его реализации==

==Существующие реализации алгоритма==
Реализации данного алгоритма не присутствуют в популярных пакетах. Тем не менее, существует несколько доступных реализаций на github:
<ul>
<li>https://github.com/axelboc/voronoi-delaunay</li>
<li>https://github.com/ayron/delaunay</li>
</ul>

=Литература=
<ref>C.A.Arens The Bowyer-Watson algorithm: An efficient implementation in a database environment</ref>

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

2016-11-15T21:00:04Z

D.Polykovskiy:

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

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

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

Итерации алгоритма строятся следующим образом:
На нулевой итерации строится треугольник (супер-треугольник), покрывающий все точки множества (таким образом множество S пополняется тремя вспомогательными точками). Начальное множество треугольников состоит только из этого треугольника.
Далее итеративно выполняются следующие действия:
<ol>
<li>Добавляется новая точка</li>
<li>Из множества треугольников выкидываются все треугольники, в описанную окружность в которых попадает новая точка. Таким образом в триангуляции образуется дырка в форме многоугольника.</li>
<li>Эта дырка заполняется треугольниками, содержащими новую точку в качестве одной вершины и ребрами дырки в качестве противолежащей стороны.</li>
</ol>
Доказано, что после завершения каждой итерации будет получена корректная триангуляция Делоне.

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

<gallery>
File:Bowyer-Watson 0.png|Помещение первой вершины в охватывающий супер-треугольник
File:Bowyer-Watson 1.png|Вторая вершина
File:Bowyer-Watson 2.png|Третья вершина
File:Bowyer-Watson 3.png|Четвертая вершина
File:Bowyer-Watson 4.png|Пятая вергина
File:Bowyer-Watson 6.png|Убираем вершины супер-треугольника.
</gallery>

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

==Макроструктура алгоритма==
===Проверка на вхождение в описанную окружность===
Для работы алгоритма требуется уметь проверять точку D на принадлежность описанной окружности треугольника ABC. Для двумерного случая это может быть сделано при помощи перехода в 3D пространство по схеме ''(x, y) -> (x, y, x2+y2)''<ref>Leonidas J. Guibas, Jorge Stolfi Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics </ref>
В новом пространстве точке расположены на параболоиде. Утверждается, что четыре точки коцикличны в ''(x, y)'' тогда и только тогда, когда они компланарны в пространстве ''(x, y, x2+y2)''. Пользуясь выпуклостью парабалоида, можно сформулировать критерий принадлежности точки описанной окружности: достаточно проверить неотрицательность определителя матрицы (предполагается, что точки расположены против часовой стрелки)

: <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} > 0
</math>

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

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

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

<syntaxhighlight lang="javascript">
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
</syntaxhighlight>

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

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

==Информационный граф==
Информационный граф рассматриваемого алгоритма получается напрямую из его описания:
[[Файл:BW.png|thumb|center|400px]]
==Ресурс параллелизма алгоритма==
Самая трудоемкая часть --- поиск

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

=Программная реализация алгоритма=
==Масштабируемость алгоритма и его реализации==

==Существующие реализации алгоритма==
Реализации данного алгоритма не присутствуют в популярных пакетах. Тем не менее, существует несколько доступных реализаций на github:
<ul>
<li>https://github.com/axelboc/voronoi-delaunay</li>
<li>https://github.com/ayron/delaunay</li>
</ul>

=Литература=
<ref>C.A.Arens The Bowyer-Watson algorithm: An efficient implementation in a database environment</ref>

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

2016-11-12T23:10:45Z

D.Polykovskiy:

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

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

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

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

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

<gallery>
File:Bowyer-Watson 0.png|Помещение первой вершины в охватывающий super-triangle
File:Bowyer-Watson 1.png|Вторая вершина
File:Bowyer-Watson 2.png|Третья вершина
File:Bowyer-Watson 3.png|Четвертая вершина
File:Bowyer-Watson 4.png|Пятая вергина
File:Bowyer-Watson 6.png|Убираем вершины super-triangle.
</gallery>

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

==Макроструктура алгоритма==
===Проверка на вхождение в описанную окружность===
Для работы алгоритма требуется уметь проверять точку D на принадлежность описанной окружности треугольника ABC. Для двумерного случая это может быть сделано при помощи перехода в 3D пространство по схеме ''(x, y) -> (x, y, x2+y2)''<ref>Leonidas J. Guibas, Jorge Stolfi Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics </ref>
В новом пространстве точке расположены на параболоиде. Утверждается, что четыре точки коцикличны в ''(x, y)'' тогда и только тогда, когда они компланарны в пространстве ''(x, y, x2+y2)''. Пользуясь выпуклостью парабалоида, можно сформулировать критерий принадлежности точки описанной окружности: достаточно проверить неотрицательность определителя матрицы (предполагается, что точки расположены против часовой стрелки)

: <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} > 0
</math>

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

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

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

<syntaxhighlight lang="javascript">
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
</syntaxhighlight>

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

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

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

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

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

=Программная реализация алгоритма=
==Масштабируемость алгоритма и его реализации==

==Существующие реализации алгоритма==
Реализации данного алгоритма не присутствуют в популярных пакетах. Тем не менее, существует несколько доступных реализаций на github:
<ul>
<li>https://github.com/axelboc/voronoi-delaunay</li>
<li>https://github.com/ayron/delaunay</li>
</ul>

=Литература=
<ref>C.A.Arens The Bowyer-Watson algorithm: An efficient implementation in a database environment</ref>

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

2016-11-12T22:36:03Z

D.Polykovskiy:

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

2016-11-12T22:28:20Z

D.Polykovskiy: /* Схема реализации последовательного алгоритма */

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

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

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

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

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

<gallery>
File:Bowyer-Watson 0.png|Помещение первой вершины в охватывающий super-triangle
File:Bowyer-Watson 1.png|Вторая вершина
File:Bowyer-Watson 2.png|Третья вершина
File:Bowyer-Watson 3.png|Четвертая вершина
File:Bowyer-Watson 4.png|Пятая вергина
File:Bowyer-Watson 6.png|Убираем вершины super-triangle.
</gallery>

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

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

Учитывая итерации по объектам, в худшем случае вне зависимости от использования структурирования пространства получается сложность ''O(|S|2)''. Однако средняя оценка при структурировании снижается до ''O(|S| log|S|)''.

==Макроструктура алгоритма==
===Проверка на вхождение в описанную окружность===
Для работы алгоритма требуется уметь проверять точку D на принадлежность описанной окружности треугольника ABC. Для двумерного случая это может быть сделано при помощи перехода в 3D пространство по схеме ''(x, y) -> (x, y, x2+y2)''<ref>{{cite journal
| last1 = Guibas
| first1 = Leonidas
| authorlink1 = Leonidas J. Guibas
| last2 = Stolfi
| first2 = Jorge
| authorlink2 = Jorge Stolfi
| title = Primitives for the manipulation of general subdivisions and the computation of Voronoi
| journal = [[ACM Transactions on Graphics]]
| volume = 4
| pages = 74–123
| year = 1985
| doi = 10.1145/282918.282923
| issue = 2
| url = http://portal.acm.org/citation.cfm?id=282923 }}
</ref>. В новом пространстве точке расположены на параболоиде. Утверждается, что четыре точки коцикличны в ''(x, y)'' тогда и только тогда, когда они компланарны в пространстве ''(x, y, x2+y2)''. Пользуясь выпуклостью парабалоида, можно сформулировать критерий принадлежности точки описанной окружности: достаточно проверить неотрицательность определителя матрицы (предполагается, что точки расположены против часовой стрелки)

: <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} > 0
</math>

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

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

<syntaxhighlight lang="javascript">
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
</syntaxhighlight>

==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.<ref>Liu, Yuanxin, and Jack Snoeyink. "A comparison of five implementations of 3D Delaunay tessellation." Combinatorial and Computational Geometry 52 (2005): 439-458.</ref>

<syntaxhighlight lang="javascript">
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
</syntaxhighlight>

== See also ==
* [[Fortune's algorithm]]
* [[Delaunay triangulation]]
* [[Computational geometry]]

==References==
{{reflist}}
*{{Cite journal | last1 = Bowyer | first1 = Adrian |author1-link=Adrian Bowyer| title = Computing Dirichlet tessellations | doi = 10.1093/comjnl/24.2.162 | journal = [[The Computer Journal|Comput. J.]] | volume = 24 | issue = 2 | pages = 162–166 | year = 1981 | pmid = | pmc = }}
*{{Cite journal | last1 = Watson | first1 = David F. | authorlink1 = | title = Computing the ''n''-dimensional Delaunay tessellation with application to Voronoi polytopes | doi = 10.1093/comjnl/24.2.167 | journal = [[The Computer Journal|Comput. J.]] | volume = 24 | issue = 2 | pages = 167–172 | year = 1981 | pmid = | pmc = }}
* [http://paulbourke.net/papers/triangulate/ Efficient Triangulation Algorithm Suitable for Terrain Modelling] generic explanations with source code examples in several languages.

{{DEFAULTSORT:Bowyer-Watson algorithm}}
[[Category:Geometric algorithms]]

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

2016-11-12T22:25:30Z

D.Polykovskiy:

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

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

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

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

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

<gallery>
File:Bowyer-Watson 0.png|Помещение первой вершины в охватывающий super-triangle
File:Bowyer-Watson 1.png|Вторая вершина
File:Bowyer-Watson 2.png|Третья вершина
File:Bowyer-Watson 3.png|Четвертая вершина
File:Bowyer-Watson 4.png|Пятая вергина
File:Bowyer-Watson 6.png|Убираем вершины super-triangle.
</gallery>

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

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

Учитывая итерации по объектам, в худшем случае вне зависимости от использования структурирования пространства получается сложность ''O(|S|2)''. Однако средняя оценка при структурировании снижается до ''O(|S| log|S|)''.

==Макроструктура алгоритма==
===Проверка на вхождение в описанную окружность===
Для работы алгоритма требуется уметь проверять точку D на принадлежность описанной окружности треугольника ABC. Для двумерного случая это может быть сделано при помощи перехода в 3D пространство по схеме ''(x, y) -> (x, y, x2+y2)''<ref>{{cite journal
| last1 = Guibas
| first1 = Leonidas
| authorlink1 = Leonidas J. Guibas
| last2 = Stolfi
| first2 = Jorge
| authorlink2 = Jorge Stolfi
| title = Primitives for the manipulation of general subdivisions and the computation of Voronoi
| journal = [[ACM Transactions on Graphics]]
| volume = 4
| pages = 74–123
| year = 1985
| doi = 10.1145/282918.282923
| issue = 2
| url = http://portal.acm.org/citation.cfm?id=282923 }}
</ref>. В новом пространстве точке расположены на параболоиде. Утверждается, что четыре точки коцикличны в ''(x, y)'' тогда и только тогда, когда они компланарны в пространстве ''(x, y, x2+y2)''. Пользуясь выпуклостью парабалоида, можно сформулировать критерий принадлежности точки описанной окружности: достаточно проверить неотрицательность определителя матрицы (предполагается, что точки расположены против часовой стрелки)

: <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} > 0
</math>

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

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

<syntaxhighlight lang="javascript">
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
</syntaxhighlight>

After every insertion, any triangles whose circumcircles contain the new point are deleted, leaving a [[star-shaped polygon]]al hole which is then re-triangulated using the new point. By using the connectivity of the triangulation to efficiently locate triangles to remove, the algorithm can take ''O(N log N)'' operations to triangulate N points, although special degenerate cases exist where this goes up to ''O(N2)''.<ref>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.</ref>

The algorithm is sometimes known just as the '''Bowyer Algorithm''' or the '''Watson Algorithm'''. [[Adrian Bowyer]] and David Watson devised it independently of each other at the same time, and each published a paper on it in the same issue of ''[[The Computer Journal]]'' (see below).

<gallery>
File:Bowyer-Watson 0.png|First step: insert a node in an enclosing "super"-triangle
File:Bowyer-Watson 1.png|Insert second node
File:Bowyer-Watson 2.png|Insert third node
File:Bowyer-Watson 3.png|Insert fourth node
File:Bowyer-Watson 4.png|Insert fifth (and last) node
File:Bowyer-Watson 6.png|Remove super-triangle edges
</gallery>

==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.<ref>Liu, Yuanxin, and Jack Snoeyink. "A comparison of five implementations of 3D Delaunay tessellation." Combinatorial and Computational Geometry 52 (2005): 439-458.</ref>

<syntaxhighlight lang="javascript">
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
</syntaxhighlight>

== See also ==
* [[Fortune's algorithm]]
* [[Delaunay triangulation]]
* [[Computational geometry]]

==References==
{{reflist}}
*{{Cite journal | last1 = Bowyer | first1 = Adrian |author1-link=Adrian Bowyer| title = Computing Dirichlet tessellations | doi = 10.1093/comjnl/24.2.162 | journal = [[The Computer Journal|Comput. J.]] | volume = 24 | issue = 2 | pages = 162–166 | year = 1981 | pmid = | pmc = }}
*{{Cite journal | last1 = Watson | first1 = David F. | authorlink1 = | title = Computing the ''n''-dimensional Delaunay tessellation with application to Voronoi polytopes | doi = 10.1093/comjnl/24.2.167 | journal = [[The Computer Journal|Comput. J.]] | volume = 24 | issue = 2 | pages = 167–172 | year = 1981 | pmid = | pmc = }}
* [http://paulbourke.net/papers/triangulate/ Efficient Triangulation Algorithm Suitable for Terrain Modelling] generic explanations with source code examples in several languages.

{{DEFAULTSORT:Bowyer-Watson algorithm}}
[[Category:Geometric algorithms]]

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

2016-11-12T22:03:59Z

D.Polykovskiy:

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

2016-11-12T21:00:57Z

D.Polykovskiy: Новая страница: « Алгоритм '''Бойера–Ватсона''' --- метод, позволяющий построить триангуляцию Делоне конечн…»

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

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

After every insertion, any triangles whose circumcircles contain the new point are deleted, leaving a [[star-shaped polygon]]al hole which is then re-triangulated using the new point. By using the connectivity of the triangulation to efficiently locate triangles to remove, the algorithm can take ''O(N log N)'' operations to triangulate N points, although special degenerate cases exist where this goes up to ''O(N2)''.<ref>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.</ref>

The algorithm is sometimes known just as the '''Bowyer Algorithm''' or the '''Watson Algorithm'''. [[Adrian Bowyer]] and David Watson devised it independently of each other at the same time, and each published a paper on it in the same issue of ''[[The Computer Journal]]'' (see below).

<gallery>
File:Bowyer-Watson 0.png|First step: insert a node in an enclosing "super"-triangle
File:Bowyer-Watson 1.png|Insert second node
File:Bowyer-Watson 2.png|Insert third node
File:Bowyer-Watson 3.png|Insert fourth node
File:Bowyer-Watson 4.png|Insert fifth (and last) node
File:Bowyer-Watson 6.png|Remove super-triangle edges
</gallery>

==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.<ref>Liu, Yuanxin, and Jack Snoeyink. "A comparison of five implementations of 3D Delaunay tessellation." Combinatorial and Computational Geometry 52 (2005): 439-458.</ref>

<syntaxhighlight lang="javascript">
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
</syntaxhighlight>

== See also ==
* [[Fortune's algorithm]]
* [[Delaunay triangulation]]
* [[Computational geometry]]

==References==
{{reflist}}
*{{Cite journal | last1 = Bowyer | first1 = Adrian |author1-link=Adrian Bowyer| title = Computing Dirichlet tessellations | doi = 10.1093/comjnl/24.2.162 | journal = [[The Computer Journal|Comput. J.]] | volume = 24 | issue = 2 | pages = 162–166 | year = 1981 | pmid = | pmc = }}
*{{Cite journal | last1 = Watson | first1 = David F. | authorlink1 = | title = Computing the ''n''-dimensional Delaunay tessellation with application to Voronoi polytopes | doi = 10.1093/comjnl/24.2.167 | journal = [[The Computer Journal|Comput. J.]] | volume = 24 | issue = 2 | pages = 167–172 | year = 1981 | pmid = | pmc = }}
* [http://paulbourke.net/papers/triangulate/ Efficient Triangulation Algorithm Suitable for Terrain Modelling] generic explanations with source code examples in several languages.

{{DEFAULTSORT:Bowyer-Watson algorithm}}
[[Category:Geometric algorithms]]

Участник:D.Polykovskiy/Триангуляция Делоне

2016-11-12T19:59:12Z

D.Polykovskiy: Init

{{Значения|Триангуляция}}
[[Файл:Delaunay_circumcircles_vectorial.svg|right|thumb|280px|Пример триангуляции Делоне. Из каждой точки порождается окружность, проходящая через две ближайшие в [[Евклидова метрика|метрике Евклида]] точки.]]

'''Триангуля́ция Делоне́''' — [[триангуляция (геометрия)|триангуляция]] для заданного множества точек {{mvar|S}} на плоскости, при которой для любого треугольника все точки из {{mvar|S}} за исключением точек, являющихся его вершинами, лежат вне окружности, описанной вокруг треугольника. Обозначается {{math|DT(''S'')}}. Впервые описана в [[1934 год в науке|1934 году]] советским математиком [[Делоне, Борис Николаевич|Борисом Делоне]].

== Свойства ==

* Триангуляция Делоне взаимно однозначно соответствует [[диаграмма Вороного|диаграмме Вороного]] для того же множества точек.
* Как следствие: если никакие четыре точки не лежат на одной окружности, триангуляция Делоне единственна.
* Триангуляция Делоне максимизирует минимальный угол среди всех углов всех построенных треугольников, тем самым избегаются «тонкие» треугольники.
* Триангуляция Делоне максимизирует сумму радиусов вписанных шаров.
* Триангуляция Делоне минимизирует [[дискретный функционал Дирихле]].
* Триангуляция Делоне минимизирует максимальный радиус минимального объемлющего шара.
* Триангуляция Делоне на плоскости обладает минимальной суммой радиусов окружностей, описанных около треугольников, среди всех возможных триангуляций{{sfn|Скворцов|2002|loc=теорема 3|с=11}}.

== Алгоритм «разделяй и властвуй» ==
{{main|Алгоритм Киркпатрика}}
Данный алгоритм основан на стандартной для многих алгоритмов методике сведения сложной задачи к более простым, в которых решение очевидно. Сам алгоритм для ''N'' > 1 состоит из 2 шагов:
# Разбиение исходного множества на более мелкие множества. Для этого мы проводим вертикальные или горизонтальные прямые в середине множества и уже относительно этих прямых разделяем точки на две части примерно по ''N''/2. После для каждой группы точек рекурсивно запускаем процесс деления.
# Объединение оптимальных триангуляций. Сначала находятся две пары точек, отрезки которых образуют в совокупности с построенными триангуляциями выпуклую фигуру. Они соединяются отрезками, и один из полученных отрезков выбирается как начало для последующего обхода. Обход заключается в следующем: на этом отрезке мы как будто «надуваем пузырь» внутрь до первой точки, которую достигнет раздувающаяся окружность «пузыря». С найденной точкой соединяется та точка отрезка, которая не была с ней соединена. Полученный отрезок проверяется на пересечение с уже существующими отрезками триангуляции, и в случае пересечения они удаляются из триангуляции. После этого новый отрезок принимается за начало для нового «пузыря». Цикл повторяется до тех пор, пока начало не совпадёт со вторым отрезком выпуклой оболочки.

Сложность разбиения множества <math>O(\log N)</math>, объединения — <math>O(N)</math> для каждого объединения, итоговая сложность алгоритма — <math>O(N \log N)</math>{{sfn|Скворцов|2002|loc=глава 3, алгоритм 3.1}}.

== Вариации и обобщения ==

* В трёхмерном пространстве возможна аналогичная конструкция с заменой окружностей на сферы.
* Также используются и обобщения при введении [[Метрическое пространство|метрик]], отличных от [[евклидово расстояние|евклидовой]].
* Одно из свойств триангуляции Делоне — минимальная сумма радиусов описанных кругов — можно применить для так называемой '''ограниченной триангуляции Делоне'''. Есть ''n'' точек, часть рёбер триангуляции уже проведены; провести остальные, чтобы сумма радиусов описанных кругов была наименьшей.

== Применение ==

[[Минимальное евклидово остовное дерево]] гарантированно располагается на триангуляции Делоне, поэтому некоторые алгоритмы пользуются триангуляцией. Также через триангуляцию Делоне приближённо решается [[Задача коммивояжёра#Метрическая задача|евклидова задача о коммивояжёре]].

В двумерной [[интерполяция|интерполяции]] триангуляция Делоне разбивает плоскость на самые «толстые» треугольники, насколько это возможно, избегая слишком острых и слишком тупых углов. По этим треугольникам можно строить, например, [[билинейная интерполяция|билинейную интерполяцию]].

[[Метод конечных элементов]] — метод численного решения дифференциальных уравнений в частных производных — предельно универсален, и с ростом мощи компьютеров и с отработкой стандартных библиотек становится всё более популярным. Однако, построение конечноэлементной сетки до последнего времени оставалось ручной работой. В большинстве вариантов метода конечных элементов погрешность обратно пропорциональна синусу минимального или максимального угла сетки, поэтому многие из алгоритмов автоматического построения сетки используют триангуляцию Делоне.

== Литература ==
* {{книга
|автор = Скворцов А. В.
|заглавие = Триангуляция Делоне и её применение
|город = Томск
|издательство = Изд-во Томского университета
|год = 2002
|страниц = 128
|isbn = 5-7511-1501-5
|ref = Скворцов
}}

[[Категория:Вычислительная геометрия]]
[[Категория:Комбинаторная геометрия]]
[[Категория:Геометрические алгоритмы]]

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

2016-11-12T19:50:08Z

D.Polykovskiy: Страница создана. Далее ее содержимое будет постепенно наполняться.