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

This page explains how to convert polygons into non-complex shapes using ActionScript 3. The code is large so I wont copy paste here.

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

Answer 2

you probabaly need triangulation

Answer 3

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

Other approaches can be found on Wikipedia.