Алгоритм уменьшения триангуляции

Question

Я вычислил триангуляцию области, границы которой описываются многоугольником. Но триангуляция вычисляется для выпуклой оболочки, большей, чем область.

Некоторые из треугольников в результирующем наборе должны быть отброшены. Ты знаешь об алгоритме этой операции?

Answer 1

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

Answer 2

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

Answer 3

Вы можете попробовать альфа-формы. Его триангуляция Делоне без ребер, превышающих альфа.