I'm working on a library for collision detection/response and perhaps slightly realistic physics. It's going well, but I want my library to have some pretty advanced features. I honestly think if I took enough time, I could find a solution to my problem, but I was wondering if there were any good resources to figure out how to get convex polygons out of concave ones. I thought about using triangulation, which would technically work, but it would be best if I could just use convex polygons with multiple sides (if that's what the shape calls for) rather than using multiple triangles to form a single convex shape.

I haven't written a triangulation algorithm yet, but I think I have a good idea of how to write one (thanks to reading up on it online). Could I use triangulation at first, then get each convex shape, or is it easier to get each convex shape individually?

Triangulation is actually far trickier than you might think. Among other things you need to keep an eye out for (this, in particular, applies to ear clipping):

* repeating vertices along a line (need to be handled before triangulation)
* winding (which will easily mess up your reflex vertex detection - took me an heureka moment to figure this one out)
* degenerate input
* optimization cases for N=3, N=4 and input = convex

Ear clipping can be fairly fast in and of itself, but making it robust is a real pain and will slow it down considerably.

The only solution I know of to get convex output from concave input is still through triangulation and then using the Hertel-Mehlhorn algorithm to merge the triangles.

PS - ear clipping is only the comparatively simplest algorithm for this job. Other more complex solutions exist.