8
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
17
$\begingroup$

I suggest you investigate the CGAL manual, Chapter 19: "2D Regularized Boolean Set-Operations". Here is an example of polygon difference:
            PolygonSubtraction
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)

or

"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).
      Boolean Ops

Improve this answer
$\endgroup$
2
  • $\begingroup$ Once again, you give a killer answer. I've added a bit more to my op. I think this answer and my question are still inline, but I honestly can't tell. Can you explain a bit more on the complications of implementing this algorithm or the Weiler–Atherton? $\endgroup$
    – Josh C.
    Commented Nov 3, 2012 at 13:36
  • 3
    $\begingroup$ @Josh: You need to find all the intersection points between the four sides of your rectangle, and your polygon. Then walk around the boundary of the polygon, stopping at each intersection point, and labeling the subsegments of the polygon as in or out. Etc., where there is considerable work in "etc." This is well-explained in the literature. $\endgroup$
    – Joseph O'Rourke
    Commented Nov 3, 2012 at 16:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .