Brechen eines konkaven Polygons in konvexe

Question

Ich benutze eine Spielphysik-Bibliothek (Box2D), die nur konvexe Polygonformen unterstützt. Ich möchte jedoch, dass der Ebenen-Builder konkave Polygone angeben kann, ohne sich darum kümmern zu müssen.

Also, wie kann ich ein konkaves Polygon automatisch in konvexe (oder sogar alle Dreiecke) zerlegen. Geschwindigkeit wäre cool, aber die Einfachheit der Implementierung ist wichtiger. Das Auseinanderbrechen wird nur bei der Initialisierung des Spiels durchgeführt.

(Meine Sprache ist Flash/Actionscript 3, aber das sollte egal)

Answer 1

Sie probabaly triangulation

Answer 2

Bernard Chazelle und David P. Dobkin brauchen präsentiert einen Algorithmus für das im Jahr 1985: Optimal Convex Decompositions.

Andere Ansätze finden Sie unter Wikipedia.

Answer 3

Auf dieser Seite wird erläutert, wie Polygone mit ActionScript 3 in nicht komplexe Formen konvertiert werden. Der Code ist groß, daher kopiere ich hier nicht.

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