Делоне триангулирует 2-й многоугольник с отверстиями

Question

Я хочу триангулировать сложный (но не самопересекающийся) многоугольник с отверстиями, чтобы все получающиеся треугольники лежали внутри многоугольника, полностью покрывали этот многоугольник и подчинялись правилам треугольника Делоне.

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

Итак, возможна ли такая триангуляция? И если да, то как я могу это сделать?

На всякий случай - мне нужно построить аппроксимацию средней оси многоугольника (надеюсь, это можно сделать, соединив все точки окружности получающихся треугольников).

Answer 1

Звучит так, как вы хотите ограниченная триангуляция Делоне . «Отверстия» могут быть реализованы путем ограничения входных ребер, чтобы они не прерывались в триангуляции.

См. Проекты Triangle и poly2tri для реализации.

Answer 2

Вот один из методов, которые я придумал, когда делал navmesh для игры RTS. Обратите внимание, что это доморощенный, сторонние инструменты не использовались, мне потребовалось около 3 недель для внедрения и исправления:

1. Введите все точки в триангуляцию Делоне (чтобы получить наиболее однородные треугольники)
2. Проверьте контуры отверстий и переверните пары полигонов, произведенные Делоне, для соответствия контурам
3. Защелкивающиеся отверстия внутри

Результат (пожалуйста, игнорируйте фиолетовые контуры):