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

Question

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

Answer 1

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

Answer 2

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

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