Convex Decomposition of a Complex Polygon?

Question

With both my 2D physics system (box2D) and OpenGL, conplex polygons need to be decomposed into convex polygons. Ensuring models conform to this is easy. However, I would also like to edit the polygons as the simulation progresses, so I need a dynamic way of fracturing existing polygons into more polygons that are still convex.

I hope this drawing helps describe what I'm after:

My Question is, Is there an existing library that can accomplish this? And if not, what would be the least error prone way of doing it myself?

(I was looking through Boost, which has both a Geometry and a Polygon module, but the documentation is proving a little too esoteric for me to know if either can do what I want.)

Answer 1

I think this is what you're looking for.

As for finding the intersection, that's just a little algebra; for any two line segments it's easy to derive the corresponding lines ('rise over run', etc.),

y = a1*x + b1

y = a2*x + b2

then the point of intersection (x', y') is

x' = (b2 - b1) / (a1 - a2)

y' = a1*x' + b1

Now of course that's the point of intersection of the lines, to determine that the line segments actually intersect you'll need to do simple range checking with the x, y coordinates.