Алгоритм Бойера-Ватсона: как заполнить оставшиеся «дыры», удалив треугольники с вершинами супер треугольников
Я реализую алгоритм Бойера-Ватсона, представленный наВикипедия, В моей реализации все работает так, как я ожидал до последней части псевдокода:
for each triangle in triangulation // done inserting points, now clean up
if triangle contains a vertex from original super-triangle
remove triangle from triangulation
Если я буду следовать псевдокоду здесь буквально, я могу получить недостающие треугольники в моей триангуляции Делоне.
В качестве примера рассмотрим изображения ниже. Сайты, которые я триангулирую, отображаются в виде синих кружков. Треугольники отображаются с черными линиями (исключая границы изображения) и соединяют узлы или ограничивающие / супер треугольные вершины. Окружности отображаются серым цветом, а их центры - красными кружками. Ячейки Вороного окрашены в разные цвета (надеюсь), чтобы сделать проблему более очевидной.
Это изображение показывает состояние триангуляции непосредственно перед выполнением шагов, перечисленных в псевдокоде выше. Обратите внимание, что две вершины супер-треугольника находятся за правым и нижним краем изображения.
Это изображение показывает шаг после удаления любых треугольников, которые содержат вершины супер треугольника без каких-либо дополнительных соображений:
Три верхние вершины должны иметь новый треугольник с центром в точке, где встречаются зеленоватые / коричневатые клетки. Проблема в том, что угловая вершина, которая была показана на изображении «до», находилась внутри этой окружности, поэтому регулярная обработка алгоритма никогда не генерировала этот треугольник.
Как я могу выразить этот крайний случай в псевдокоде, чтобы я мог проверить и решить его? Я хотел бы избежать какой-либо ужасающей петли «попробуйте каждую комбинацию сайтов, которые имеют общий треугольник с вершиной супер треугольника для правильного круга».
Я прочитал статьи Бойера и Ватсона пару лет назад и, при необходимости, прочту их еще раз, чтобы ответить. Я надеялся, что (1) кто-то другой мог бы иметь доступный ответ и (2) я мог бы использовать переполнение стека, чтобы найти ответ, если я когда-нибудь столкнусь с этим вопросом снова.
редактировать
Так что я нашел относительно дешевый, но несовершенный обходной путь. Мой супер-треугольник программно определен так, чтобы окружать ограничивающий прямоугольник сайтов, не пересекая его стороны. Эта идея была вызвана всевозможными неприятными проблемами с Java, считающими некоторые из моих вычисленных координат окружности или расстояния между координатами бесконечными. Это предостережение заставило меня сделать мой супер треугольник настолько маленьким, что его вершины иногда попадали в окружности действительных треугольников. Увеличение размера супер треугольника заставило проблему исчезнуть. Однако возможно, что треугольник на выпуклой оболочке может быть настолько тупым, что одна из вершин все еще может попадать в допустимое окружность.
Я думаю, это означает, что мой первоначальный вопрос все еще актуален перед лицом ограничений числа с плавающей точкой. Есть ли дешевый способ гарантировать, что алгоритм Бойера-Ватсона генерирует правильную триангуляцию?