One algorithm that should work in this situation to break the shape into convex hulls that can be drawn more easily:
1. Pick a point, add it a list A which shall be our first convex sape
2. Cycle through points going clockwise
3. Check each such point to make sure that it is further clockwise than the previously checked one
4. If it's not clockwise not, then ignore add it to a list of points left over
5. If it is clockwise, add it to the convex hull
5a. If it is clockwise and the previous one was not, run this algorithm recursively, making a new convex shape by iterating over the list of left-over points (clear left-over point list when done)
6. Continue until all points have been checked
I hope that's clear. Basically, anything that isn't still going clockwise is a new convex (recusively, since this might also need to be broken up), but anything that is, is. This isn't guaranteed to have the best possible break-up of convex shapes and I'm sure you could come up with weird shapes that it would break up inefficiently. But I suspect it will work for the vast majority of things. It is guaranteed that for any non-self-intersecting shape it will fill exactly its interior and none of its exterior. Don't expect it to work sanely with self-intersections. Also, your choice of initial point will affect how it makes the convex shapes.
Note that a convex shape can be drawn by picking any point and drawing a 'triangle fan' out from that point, like the (out-dated?) OpenGL function for that.
I tried out what you mentioned one paper and It makes a lot of sense and is far quicker than the ideas I was coming up with.
It also will help with box2D when I come to allow for concave shapes.
I will code it in tomorrow or tonight and see if it all works but I believe it should do. The only time I can see it breaking is when a lines intersect which should not happen any way.