I'm looking for an algoritm that could be used to sub-divide a 2d concave polygon into a set of convex ones. As it stands the polygon to be divided is defined with its points in an ordered list. I thought about looking up an algorithm used to divide a concave polygon into triangles, and then build a set of convex polygons from the triangles, but it seems a bit messy. The reason for this is to be used in my physics engine which only works with convex polygons - however it can weld them together for concave ones. The reason i want to have it divided into convex ones and not just triangles is that the physics runs alot faster with having a small set of convex polygons than many triangles.

Okay im almost there.

all points are already in order, create a list of all inflexive points. Drawing lines between these points in order around polygon gives a set of convex polygons, and a possibly concave polygon made by all of these points in the middle. Iterate on this possibly concave polygon - if only two inflexive points, you can simply split.

It doesn't however deal with only having one inflexive point, in which case for an optimum solution, check each split made with the point to other points in polygon, if any gives 2 convex use it. if not, test each over split to find one that gives least number of polygons in the end - this will well be the slowest part of algorithm depending on number of points.

Anyone got any suggestions how to best deal with one inflexive point to find solution that gives least number of polygons?

damn, all seemed to be going well, but i found a set of shapes for which the algorithm fails :/

Search on "convex partitioning". Joseph O'Rourke has a decent discussion of "polygon partitioning" in "Computational Geometry in C, 2nd edition". Convex partitioning into the minimum number of pieces is a hard problem. The Hertel-Mehlhorn algorithm is easy to implement (what you are trying to rediscover) and guarantees at most 4 times the minimum number. Search Google using "Keil and Snoeyink" to find papers on minimum decomposition using dynamic programming.

the algorithm for minimal number of polygons seems to be very heavy compared to an approximation like the one you suggested - that and any description of the algorithm i've found has been extremely vague :/ Ill look into one of the approximations.