Вычисление бесконечных точек / ребер триангуляции Делоне

Question

Я пытаюсь вычислить бесконечные ребра триангуляции Делоне. У меня есть основные моменты, которые могут помочь мне собрать вершины для диаграммы Вороного. Проблема в том, что я не уверен, как или где начать вычислять линии, которые go к бесконечности

Те, которые отмечены синим цветом, и их соединительная линия - это то, что Я пытаюсь вычислить Те, которые отмечены желтым цветом, - это те, на которые я уже знаю, на основании процесса триангуляции

Я не уверен, какие расчеты мне нужно сделать, чтобы их получить. Кто-нибудь может предложить формулу или метод для их расчета? Кажется, я нигде не могу найти информацию об этом.

Answer 1

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

Чтобы сделать этот бетон, предположим, что ваш домен - это квадрат от -1 до 1 в направлениях x и y. Если одна из точек, генерирующих диаграмму Вороного, имеет вид (0,4, -0,3), то вы можете добавить точки (1,6, -0,3), (-2,4, -0,3), (0,4, 2,3), (0,4, -1,7), отражающие точка на линиях x = 1, x = -1, y = 1 и y = -1 соответственно.

Это хорошо, если дорого: ваша диаграмма Вороного включает в 5 раз больше входных точек, и четыре пятых из них выбрасываются. Чтобы быть более осторожным, вы можете создать начальную диаграмму Вороного с исходными точками (но не заботясь о разрешении бесконечных ячеек), а затем отразить только точки с бесконечными ячейками или ячейками, которые go вне ограничивающей области, и построить второй Вороной. диаграмма с этим дополненным набором.

Здесь - это дополненная версия диаграммы Вороного, на которой показаны дополнительные ключевые точки фиолетового цвета.

Answer 2

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

У меня есть проект с открытым исходным кодом для триангуляций Делоне, который может быть полезен для вас. В нем реализован класс для создания «ограниченных» диаграмм Вороного из Delaunay… Но на самом деле это скорее демонстрационная часть, а не одна из основных функций библиотеки. Поскольку вас действительно интересует Вороной, а не Делоне, я думаю, что вам лучше использовать один из классических алгоритмов c, которые производят Вороного напрямую, а не создают его из его двойной формы (двойственный Вороного Делоне). Тем не менее, вы можете просмотреть проект в https://github.com/gwlucastrig/Tinfour

В любом случае, как вы указали, граничные края ячейки Вороного проходят через центры окружностей треугольников, которые образуют Делоне. Лучи, которые go к бесконечности, связаны с треугольниками, которые включают один из внешних краев. Если центр окружности находится внутри треугольника, луч проходит от центра окружности треугольника и через середину внешнего края. Если центр окружности находится за пределами треугольника (например, когда у вас есть «тощий» треугольник на внешнем крае), он также будет l ie за пределами границ Делоне. Луч начинается от центра окружности и распространяется наружу, но он лежит на линии, которая проходит через центр окружности и среднюю точку внешнего края (средняя точка будет позади начала луча). Таким образом, в обоих случаях у вас есть две значимые точки, центр окружности и средняя точка соответствующего внешнего ребра.

Я полагаю, что у вас есть расчет для положения и радиуса окружности. Если нет, вы можете найти его по адресу https://github.com/gwlucastrig/Tinfour/blob/master/core/src/main/java/org/tinfour/common/Circumcircle.java

Надеюсь, что это вам поможет.

Гари