I'm looking for an algorithm that will subtract a rectangle from a simple, concave polygon and return a remainder of polygons. If the rectangle encloses the polygon, the remainder is null. In most cases, it looks like at least one edge will be shared between the rectangle and the polygon.
I've been digging around the internet, but I've not found a good lead.
Can someone point me in the right direction?
Edit I did some more digging and found a few polygon clipping algorithms. However, all of the ones I found finds what is inside the clipping region. I want all of the stuff outside as separate rectangles.
If I understand correctly, the Weiler–Atherton algorithm detects all of the intersections between the clipping region and the polygon. I was thinking of using that approach. I've got some tricky cases where the edge of the clipping region and the edge of the polygon are collinear.
Do I sound like I am getting closer?