Создайте 2d треугольники из 2d точек

Question

Мне нужно сделать 2d треугольники из списка 2d точек с условием: длина любого ребра не может быть больше, чем предопределенная константа.

Примерно так:

Знаете ли вы какой-нибудь алгоритм, который может это сделать?Или какой-нибудь совет?

Спасибо!

Answer 1

Попробуйте Триангуляция Делоне , затем удалите слишком длинные ребра.

Из вышеприведенной статьи вы увидите ссылку на страницу 2D-триангуляции CGAL .

Answer 2

Сначала сгенерируйте все возможные ребра (т.е. соедините пару вершин, которые ближе, чем константа).Затем, когда два из них пересекаются, удалите один из них.Повторяйте этот шаг до тех пор, пока не будет пересечений.

Это решение довольно примитивно, возможно, возможно сделать это быстрее.

Answer 3

Мне нравится ответ svick -

при реализации я бы сделал следующее

1. вычислить линии между каждой парой точек
2. Сортировка списка по длине
3. Удалить все строки длиннее вашего порога
4. Продолжить вниз по списку (от самого длинного до самого короткого), если он пересекает другую строку, затем удалить его.