Briser un polygone concave en polygones convexes

Question

J'utilise une bibliothèque de physique de jeu (Box2D) qui ne supporte que les formes polygonales convexes. Cependant, j'aimerais que le constructeur de niveau puisse simplement spécifier des polygones concaves sans avoir à se soucier de cela. Donc, comment puis-je séparer automatiquement un polygone concave en polygones convexes (ou même tous les triangles)? La vitesse serait cool, mais la facilité de mise en œuvre est plus importante. La rupture ne sera faite que lors de l'initialisation du jeu.

(Ma langue est Flash/ActionScript 3, mais cela ne devrait pas d'importance)

Answer 1

vous avez besoin probabaly triangulation

Answer 2

Bernard Chazelle et David P. Dobkin a présenté un algorithme pour cela en 1985: Optimal Convex Decompositions.

D'autres approches peuvent être trouvées sur Wikipedia.

Answer 3

Cette page explique comment convertir des polygones en formes non complexes à l'aide d'ActionScript 3. Le code est grand, donc je ne copierai pas de pâte ici.

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