Как триангулировать многоугольник без случайных внутренних точек?

Question

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

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

Как мне это установить?

Комментарий: это больше не зависит от языка, мне нравится знать, как реализовать это самостоятельно.

Answer 1

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

(Если вы решите формировать монотонные многоугольники, монотонные многоугольники будут выпуклыми и могут быть разбиты на треугольные вееры напрямую.)

Answer 2

Я нашел очень полезную библиотеку Poly2Tri .Ветка Java этой библиотеки делает именно то, что мне нужно.

Мне просто нужно правильно ее использовать.Он не добавляет никаких точек к многоугольнику.

Answer 3

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

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