Алгоритм Бойера – Ватсона

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

Описание

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

Первый шаг: вставьте узел во вмещающий «супер»-треугольник.
Вставить второй узел
Вставить третий узел
Вставьте четвертый узел
Вставьте пятый (и последний) узел
Удалите края с экстремумами в супертреугольнике.

История

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

Псевдокод

Следующий псевдокод описывает базовую реализацию алгоритма Бойера-Ватсона. Его временная сложность равна $O(n^{2})$ . Эффективность можно повысить несколькими способами. Например, связность треугольников можно использовать для поиска треугольников, содержащих новую точку в описанной окружности, без необходимости проверять все треугольники — таким образом мы можем уменьшить временную сложность до $O(n\log n)$ . Предварительное вычисление описанных окружностей может сэкономить время за счет дополнительного использования памяти. А если точки распределены равномерно, сортировка их вдоль кривой Гильберта, заполняющей пространство перед вставкой, также может ускорить определение местоположения точки. ^{[ 2 ]}

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

Ссылки

^ Ребай, С. Эффективное создание неструктурированной сетки с помощью триангуляции Делоне и алгоритма Бойера-Ватсона . Журнал вычислительной физики, том 106, выпуск 1, май 1993 г., с. 127.
^ Лю, Юаньсинь и Джек Снойинк. «Сравнение пяти реализаций 3D-мозаики Делоне». Комбинаторная и вычислительная геометрия 52 (2005): 439–458.

Дальнейшее чтение

Бойер, Адриан (1981). «Вычисление мозаики Дирихле» . Вычислить. Дж. 24 (2): 162–166. дои : 10.1093/comjnl/24.2.162 .
Уотсон, Дэвид Ф. (1981). «Вычисление n- мерной мозаики Делоне с применением к многогранникам Вороного». Вычислить. Дж. 24 (2): 167–172. дои : 10.1093/comjnl/24.2.167 .
Эффективный алгоритм триангуляции, подходящий для моделирования местности. Общие объяснения с примерами исходного кода на нескольких языках.

Внешние ссылки

pyDelaunay2D : дидактическая на языке Python . реализация алгоритма Бойера-Ватсона
Bl4ckb0ne/delaunay-triangulation : на C++ . реализация алгоритма Бойера – Ватсона

[1] Ребай, С. Эффективное создание неструктурированной сетки с помощью триангуляции Делоне и алгоритма Бойера-Ватсона . Журнал вычислительной физики, том 106, выпуск 1, май 1993 г., с. 127.

[2] Лю, Юаньсинь и Джек Снойинк. «Сравнение пяти реализаций 3D-мозаики Делоне». Комбинаторная и вычислительная геометрия 52 (2005): 439–458.

[ 1 ]

[ 2 ]