генерация ребер ограничений случайным образом для генерации ограниченной триангуляции Делоне

Question

Я реализовал подход строчной линии, используемый Домитером и Заликом для генерации ограниченной триангуляции Делоне для набора точек в 2D-пространстве в Java.Я хочу убедиться, что код, который я разработал, действительно работает для n случайно сгенерированных точек и k ребер ограничения между ними.

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

Таким образом, мне было интересно, знает ли кто-нибудь об эффективной стратегии случайного генерирования ограничений.

Заранее спасибо.

Answer 1

Вы можете попробовать двухэтапный процесс:

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

• Добавить дополнительный набор случайных точек к набору данных и построить ограниченную триангуляцию Делоне для полного набораналожение границ ограничения, найденных ранее.

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

Пакет Triangle включает в себя несколько эталонных геометрий, которые могут быть полезны в этом отношении.

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