В вычислительной геометрии , то алгоритм Бойер-Уотсон представляет собой метод для вычисления триангуляции Делона конечного множества точек в любом количестве измерений . Алгоритм также может быть использован для получения диаграммы Вороного точек, которая является двойственным графом триангуляции Делоне.
Описание
Алгоритм Бойера – Ватсона - это инкрементальный алгоритм . Он работает, добавляя точки по одной к действительной триангуляции Делоне подмножества требуемых точек. После каждой вставки все треугольники, окружности которых содержат новую точку, удаляются, оставляя многоугольное отверстие в форме звезды, которое затем повторно триангулируется с использованием новой точки. Используя связность триангуляции для эффективного определения местоположения треугольников для удаления, алгоритм может выполнять O (N log N) операций для триангуляции N точек, хотя существуют особые вырожденные случаи, когда это достигает O (N 2 ) . [1]
Первый шаг: вставьте узел в охватывающий "супер" -треугольник
Вставить второй узел
Вставить третий узел
Вставить четвертый узел
Вставить пятый (и последний) узел
Убрать ребра с крайностями в супер-треугольнике
История
Этот алгоритм иногда называют просто алгоритмом Бойера или алгоритмом Ватсона . Адриан Бойер и Дэвид Уотсон разработали его независимо друг от друга в одно и то же время, и каждый из них опубликовал статью об этом в том же выпуске The Computer Journal (см. Ниже).
Псевдокод
Следующий псевдокод описывает базовую реализацию алгоритма Бойера-Ватсона. Его временная сложность. Эффективность можно повысить несколькими способами. Например, соединение треугольников можно использовать для определения местоположения треугольников, которые содержат новую точку в их описанной окружности, без необходимости проверять все треугольники - таким образом мы можем уменьшить временную сложность до. Предварительное вычисление описанных окружностей может сэкономить время за счет использования дополнительной памяти. А если точки распределены равномерно, их сортировка по кривой Гильберта, заполняющей пространство, перед вставкой также может ускорить определение местоположения точки. [2]
Функция BowyerWatson ( PointList ) // PointList представляет собой набор координат , определяющих точки , чтобы быть триангулирован триангуляции : = пустой треугольник сетки данных структуры добавить супер - треугольник в триангуляции // должно быть достаточно большим , чтобы полностью содержать все точки в PointList для каждой точки в PointList же // добавить все точки по одному на триангуляции badTriangles : = пустое множество для каждого треугольника в триангуляции сделать // первый найти все треугольники, которые больше не действительны из - за вставки , если точка находится внутри окружность из треугольника добавить треугольник к badTriangles многоугольника : = пустое множество для каждого треугольника в badTriangles же // найти границу многоугольной отверстия для каждого ребра в треугольнике делать , если край будет не разделяют с помощью любых других треугольников в badTriangles добавить края к полигону для каждого треугольника в badTriangles действительно // удалить их из структуры данных удалить треугольника из триангуляции для каждого края в многоугольнике сделать // повторно триангуляции многоугольной отверстие newTri : = образуют собой треугольник из EDG е к точке добавить newTri в триангуляцию для каждого треугольника в триангуляции // проделанных точек вставляя, теперь моется , если треугольник содержит в вершину из оригинальных супер - треугольника удалить треугольник из триангуляции возврата триангуляции
Рекомендации
- ^ Rebay, S. Эффективное создание неструктурированной сетки с помощью триангуляции Делоне и алгоритма Бойера-Ватсона . Журнал вычислительной физики, том 106, выпуск 1, май 1993 г., стр. 127.
- ^ Лю, Yuanxin, и Джек Snoeyink. «Сравнение пяти реализаций тесселяции 3D Делоне». Комбинаторная и вычислительная геометрия 52 (2005): 439-458.
дальнейшее чтение
- Бойер, Адриан (1981). «Вычисление мозаики Дирихле» . Comput. J. 24 (2): 162–166. DOI : 10.1093 / comjnl / 24.2.162 .
- Уотсон, Дэвид Ф. (1981). «Вычисление n- мерной мозаики Делоне с применением к многогранникам Вороного» . Comput. J. 24 (2): 167–172. DOI : 10.1093 / comjnl / 24.2.167 .
- Эффективный алгоритм триангуляции Подходит для общих объяснений моделирования местности с примерами исходного кода на нескольких языках.
Внешние ссылки
- pyDelaunay2D : дидактическая реализация алгоритма Бойера – Ватсона на Python .
- Bl4ckb0ne / delaunay-triangulation : реализация алгоритма Бойера – Ватсона на C ++ .