How to form a Concave shape out of Convex shapes?

i'm trying to get around the rule of only being able to form convex shapes in the SFML c++ library.

To do this I'm planning on testing given vertices, and if concave, splitting the vertices into groups, testing each groups' concaveness, and repeating until a full set of concave shapes results that look just like the original shape when put together

What I would like to know is...

What the equation for testing a shapes concaveness is: What is it and how does it work?
How would i split up the vertices of the concave shape so in the end the shape is formed out of as few convex shapes as possible?
Whats the best practice for achieving my goal?

Thanks!

Solution

You can test for a shape being a convex hull by going round all the edges and checking the next edge is always moving in the same direction (left/right handed). This is a quick and cheap algorithm. There is an implementation of this here: en.wikipedia.org/wiki/Graham_scan

If you don't have a convex hull, perform a package wrapping algorithm to get a convex hull that encompasses all your points (again quite fast). en.wikipedia.org/wiki/Gift_wrapping_algorithm

Now, look for points that are on your shape, but aren't on the convex hull. For each run of these points, create a new shape from these points (plus the 2 either side on the convex hull).

Recursion is now your friend: do the exact same process on each of the sub-shapes you have just made.

I have used this techniques to test for a point being contained inside an arbitrary shape: i.e. the point must be inside the convex hull (easy to test), but not any of the sub-shapes, or their sub-shapes, or their sub-shapes....