Boolean operations on rectangular polygons

Question

Avast there, other programmers!

I have the following problem:

I have two rectangles overlapping as shown in the image below.

I want to figure out a polygon consisting of an ABCDEF point.

Alternative Christmas Description: A red cutter cutter cuts off some black cookies. I want to calculate a black cookie.

Each rectangle represents a data structure with 4 2d vertices.

What is the best algorithm to achieve this?

Answer 1

This is a special case of cropping a common two-dimensional polygon. A good place to start is the Wyler-Atherton algorithm. Wikipedia has a summary and links to the source document . It seems that the algorithm matches the data structure that you described pretty well.

Please note that it is quite possible that in the end you will get a rectangle with a hole in it (if red is completely inside black) or even two rectangles (for example, if red is higher and thinner than black), if you are sure that there is only one corner of the red rectangle inside the black, then the solution should be much simpler.

Answer 2

solid structural geometry

Answer 3

How accurate are the coordinates? If the rectangles are quite small, the simplest approach would be to simply draw them on the canvas, first a black rectangle, then red. The remaining black pixels on the canvas are the remaining polygon.

Another approach is to split the grid into a bunch of rectangles based on all sides of the rectangles (not counting unlimited rectangles, you have up to 9 rectangles generated if you have two original rectangles). Then simply check the representative point from each of these rectangles for belonging to specific polygons to determine which rectangles are and which are missing.

Answer 4

I found a few things that I could use:

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

I really downloaded the CGAL source before I even posted this question, but I think I will take a closer look at it.