Boolean operations on rectangle polygons

Question

Avast there fellow programmers!

I have the following problem:

I have two rectangles overlapping like shown on the picture below.

I want to figure out the polygon consisting of point ABCDEF.

Alternate christmas description: The red cookie cutter is cutting away a bit of the black cookie. I want to calculate the black cookie.

Each rectangle is a data structure with 4 2d-vertices.

What is the best algorithm to achieve this?

Answer 1

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.

Answer 2

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 3

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 4

constructive solid geometry