Как вырезать треугольники из вогнутой триангуляции Делоне?

Question

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

Answer 1

Самоответ: в некоторых случаях это невозможно. Мне нужно было использовать алгоритм Делоне с ограничениями: http://www.cs.cmu.edu/~quake/triangle.delaunay.html

Answer 2

Вы не должны, вы должны найти процедуру Делоне, которая правильно обрабатывает границы.

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