Используйте триангуляцию Делоне с ограничением для триангуляции многоугольника

Question

У меня есть алгоритм триангуляции Делоне с ограничением (CDT), и у меня есть многоугольник (он может быть вогнутым или выпуклым) в качестве входных данных. Как я могу использовать этот алгоритм триангуляции Делоне с ограничением, чтобы разбить многоугольник на треугольники без введения новых точек?

Редактировать: объединение всех треугольников должно равняться многоугольнику. Поэтому нельзя просто взять CDT вместе с границей в качестве границы ограничения для генерации треугольников, потому что это приведет к выпуклому многоугольнику, независимо от того, является ли вход вогнутым или выпуклым.

Answer 1

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

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

Edit:

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