Выпуклая декомпозиция сложного многоугольника?

Как с моей 2D-физической системой (box2D), так и с OpenGL, сложные полигоны должны быть разложены на выпуклые многоугольники. Обеспечение соответствия моделей этому легко. Тем не менее, я также хотел бы отредактировать полигоны по мере продвижения моделирования, поэтому мне нужен динамический способ разлома существующих полигонов на большее количество полигонов, которые все еще выпуклые.

Я надеюсь, что этот рисунок поможет описать, что я хочу:

Мой вопрос: существует ли существующая библиотека, которая может это сделать? И если нет, то какова была бы наименее подверженная ошибкам способ сделать это сама?

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

Ответы

Ответ 1

Я думаю, этот - это то, что вы ищете.

Что касается нахождения пересечения, то это всего лишь небольшая алгебра; для любых двух сегментов линии легко выводить соответствующие строки ( "рост над пробегом" и т.д.),

y = a1 * x + b1

y = a2 * x + b2

то точка пересечения (x ', y') равна

x '= (b2 - b1)/(a1 - a2)

y '= a1 * x' + b1

Теперь, конечно, что точка пересечения линий, чтобы определить, что сегменты линии действительно пересекаются, вам нужно будет провести простую проверку диапазона с координатами x, y.