Разделение полигонов и триангуляция

Question

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

Используемая мной библиотека (SFML \ Box2D) принимает только выпуклые формы.

Это то, что я хочу знать:

1. Является ли разбиение полигонов или триангуляция полигонов быстрее?

2. Как работает разбиение полигонов / Как вы это делаете?

---

Не забывайте, что триангуляция также не требует выпуклых форм ...

Answer 1

Не полный ответ на ваш вопрос, но если у вас есть общий многоугольник (вогнутый, выпуклый и т. Д.), И вы хотите его триангулировать (возможно, для последующего рендеринга в стиле openGL), вы можете изучить пакеты «триангуляции с ограниченным Делоне» , Одним из таких примеров является пакет Triangle , который считается быстрым и надежным.

Насколько я понимаю, алгоритмы, используемые в Треугольнике, демонстрируют O(nlogn) сложность времени выполнения.

Answer 2

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

Вот мой код: https://github.com/meshko/triangulator/tree/master/som

Я не трогал 10 лет, поэтому остерегайтесь.