I have an idea how to triangulate the shape above. When building a face I need to check wheter the third vertex is left (outside) or right (inside) of the line conencting the first two vertices.
If this is the case I have my first triangle and I can mark point 2 as "done". I'll need points 1 and 3 for further recursion.

I'll continue like this until point 3 is on the left side. This means I have some concave form and I can't build a proper triangle. So I skip this vertex and try with the next vertex. When I've cycled through the vertex cloud once, I have some polygon shape, with some of the original vertices already "cut off".
I continue now until only 3 vertices remain. That's the last polygon.

It works for simple concave shapes, but not for complex shapes like labyrinths... so it is not a solution.