Boolean operations on rectangle polygons.

Answer 1

constructive solid geometry

Answer 2

This is a special case of general 2D polygon clipping. A good place to start is the Weiler-Atherton algorithm. Wikipedia has a summary and links to the original paper. The algorithm seems to match the data structure you've described pretty well.

Note that it's quite possible you'll end up with a rectangle with a hole in it (if the red one is entirely inside the black one) or even two rectangles (eg if the red is taller and skinnier than the black). If you're certain there is only one corner of the red rectangle inside the black one then the solution should be much simpler.

Answer 3

I found some stuff here I might use:

http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Boolean_set_operations_2/Chapter_main.html

I actually downloaded the CGAL source before I even posted this question, but I think I'll look closer into it.

Answer 4

How precise are the coordinates? If the rectangles are fairly small, the easiest approach might be to just paint them on a canvas, black rectangle first, followed by red. The remaining black pixels on the canvas are the polygon that's left.

Another approach is to split the coordinate grid into a bunch of rectangles based on all of the sides of the rectangles (not counting unbounded rectangles, you have up to 9 rectangles generated if you have two original rectangles). Then just test a representative point from each of these rectangles for membership in the particular polygons to determine which rectangles are in and which are out.