dividing concave polygon into convex ones

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.