Subtract Rectangle from Polygon - MathOverflow

Subtract Rectangle from Polygon

2012-11-02T19:46:58Z

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?

Answer by Joseph O'Rourke for Subtract Rectangle from Polygon

2012-11-03T00:20:27Z

I suggest you investigate the CGAL manual, Chapter 19: "2D Regularized Boolean Set-Operations". Here is an example of polygon difference:

This is well-understood & explored algorithmically, but nevertheless a very delicate computation, as the term regularized indicates. You are subtracting a rectangle, but there is nothing special about a rectangle—"degenerate" situations may occur. You really need to consider the general situation. So I recommend you look at general resources, such as

"Boolean operations on general planar polygons." M. Riveroa, F.R. Feitob. Computers & Graphics. Volume 24, Issue 6, December 2000, Pages 881–896 (Elsevier link)

"A General Polygon Clipping Library." Version 2.32. Alan Murta. (link)

The upperleft corner of Murta's Fig.2 illustrates a complicated polygon difference (and the remaining images illustrate other Boolean operations).