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

Question

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

Надеюсь, этот чертеж поможет описать то, что мне нужно:

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

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

Answer 1

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

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

y = a1 * x + b1

y = a2 * x+ b2

, тогда точка пересечения (x ', y') будет

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

y '= a1 * x' + b1

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