Having axis-aligned rectangles will make some of the details easier but doesn't effect the general algorithm, so I will make no further assumptions regarding axis alignment.
The method for subtracting simple polygons works the same as described for finding the intersection of polygons described here with one small change. Also, that answer assumed that the polygons were convex (in fact rectangles) so there was at most one polygon resulting from the intersection. In the current case multiple polygons may result. However, finding multiple polygons isn't much harder, see the comments below.
In the intersection problem, the polygons were both oriented counterclockwise, which is a way of specifying (by convention) which side of the lines are inside the polygon. If we reverse the orientation of the rectangle to be subtracted, then by convention, all of the plane is "inside" the polygon, except for a small area to the right of the edges. Thus subtraction of polygons is actually intersection of polygons, where the polygon to be subtracted is turned inside out!
Comments:
- Subtracting a convex polygon from a non-convex polygon could result in multiple polygons. Which polygon is found depends on the starting intersection point. If one keeps track of the intersection points that are consumed while tracing out one resultant polygon, then the process can be repeated for unconsumed intersections, each time finding more pieces of the result.
- In cases where intersections happen at a corner, things can get confusing. One way is to logically break the intersection into multiple logical intersections, each logical intersection representing one legal traversal.
- Segments of the two polygons may be concurrent, especially in the OP's case. These segments may be culled as part of a preprocess. If they are in opposite directions they represent an infinitely thin interior piece surrounded by the exterior, if they are in the same direction they represent infinitely thin exterior surrounded by interior. Either way they may be discarded.
- The previous comment may seem strange since after discarding the overlapping segments the Boolean is no longer between polygons, but the algorithm only requires the entities to be oriented correctly. Therefore, this general approach can be used to slice polygons with curves, keeping the pieces to one side or the other.
- Subtraction of polygons can lead to objects which are not simple polygons. If the polygon being subtracted is entirely inside the other polygon, the result may be a region with a hole in it. If this is of concern, you might consider using a slightly more sophisticated structure to represent regions that uses multiple loops to define the boundaries. The outer loop of a region should be oriented counterclockwise, the inner loops should be oriented clockwise.
