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