Разбивая вогнутый многоугольник на выпуклые

Question

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

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

(мой язык - Flash / ActionScript 3, но это не должно иметь значения)

Answer 1

Бернар Шазель и Дэвид П. Добкин в 1985 году представили алгоритм для этого: Оптимальные выпуклые разложения .

Другие подходы можно найти в Википедии .

Answer 2

вам, вероятно, нужно триангуляция

Answer 3

На этой странице объясняется, как преобразовать многоугольники в не сложные фигуры с помощью ActionScript 3. Код большой, поэтому я не буду копировать сюда вставку.

http://www.emanueleferonato.com/2011/09/12/create-non-convex-complex-shapes-with-box2d/