http://en.wikipedia.org/wiki/Polygon_triangulation
have you looked into the algorithms mentioned here?

yes, with special cases like holes it probably isn't that easy. what do you need this for? i think there also are some ready to use c/c++ libraries for triangulation.