Ответ 1
Похоже, вы хотите ограниченную триангуляцию Delaunay. "Отверстия" могут быть реализованы путем ограничения входных краев, чтобы они не прерывались в триангуляции.
Делоне триангулирует 2-й многоугольник с отверстиями
Я хочу триангулировать сложный (но не самопересекающийся) многоугольник с отверстиями, так что возникающие треугольники лежат внутри многоугольника, полностью покрывают этот многоугольник и подчиняются правилам треугольника Делоне.
Очевидно, я мог бы построить триангуляцию Деланея для всех точек, но я боюсь, что некоторые ребра многоугольника не будут включены в возникающую триангуляцию.
Итак, возможна ли такая триангуляция? И если да, как я могу это сделать?
На всякий случай - мне нужно построить аппроксимацию полигональной медиальной оси (надеюсь, это можно сделать, подключив все точки окружности результирующих треугольников).
Ответы
Ответ 2
Вот один из методов, которые я придумал, когда делаю navmesh для игры RTS. Обратите внимание, что это доморощенный, сторонних инструментов не было, мне потребовалось около 3 недель для реализации и исправления:
- Подайте все точки в триангуляцию Делоне (чтобы получить наиболее однородные треугольники)
- Проверьте контуры отверстий и переверните многоугольные пары, созданные Delaunay, чтобы соответствовать контурам
- Отверстия для отверстий
Результат (plz игнорировать фиолетовые контуры):
