Breaking a concave polygon into convex ones.

Question

I'm using a game physics library (Box2D) which only supports convex polygon shapes. However, I'd like the level builder to be able to just specify concave polygons without having to worry about that.

So, how can I automatically break apart a concave polygon into convex ones (or even all triangles). Speed would be cool, but ease of implementation is more important. The breaking apart will only be done on game initialization.

(My language is Flash/ActionScript 3, but that shouldn't matter)

Answer 1

you probabaly need triangulation

Answer 2

Bernard Chazelle and David P. Dobkin presented an algorithm for that in 1985: Optimal Convex Decompositions.

Other approaches can be found on Wikipedia.