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?
Best Answer
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
or
The upperleft corner of Murta's Fig.2 illustrates a complicated polygon difference (and the remaining images illustrate other Boolean operations).
