Subtract Rectangle from Polygon - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T05:45:22Z http://mathoverflow.net/feeds/question/111296 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/111296/subtract-rectangle-from-polygon Subtract Rectangle from Polygon Josh C. 2012-11-02T19:46:58Z 2012-11-03T13:33:40Z <p>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.</p> <p>I've been digging around the internet, but I've not found a good lead.</p> <p>Can someone point me in the right direction?</p> <p><strong>Edit</strong> 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.</p> <p>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.</p> <p>Do I sound like I am getting closer?</p> http://mathoverflow.net/questions/111296/subtract-rectangle-from-polygon/111323#111323 Answer by Joseph O'Rourke for Subtract Rectangle from Polygon Joseph O'Rourke 2012-11-03T00:20:27Z 2012-11-03T01:49:25Z <p>I suggest you investigate the <a href="http://www.cgal.org/" rel="nofollow">CGAL</a> manual, Chapter 19: "<a href="http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Boolean_set_operations_2/Chapter_main.html" rel="nofollow">2D Regularized Boolean Set-Operations</a>". Here is an example of <em>polygon difference</em>: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/TriangleSubtraction.jpg" alt="PolygonSubtraction"><br /> This is well-understood &amp; explored algorithmically, but nevertheless a very delicate computation, as the term <em>regularized</em> indicates. You are subtracting a rectangle, but there is nothing special about a rectangle&mdash;"degenerate" situations may occur. You really need to consider the general situation. So I recommend you look at general resources, such as</p> <blockquote> <p>"Boolean operations on general planar polygons." M. Riveroa, F.R. Feitob. <em>Computers &amp; Graphics</em>. Volume 24, Issue 6, December 2000, Pages 881â€“896 (<a href="http://www.sciencedirect.com/science/article/pii/S009784930000090X" rel="nofollow">Elsevier link</a>)</p> </blockquote> <p>or </p> <blockquote> <p>"A General Polygon Clipping Library." Version 2.32. Alan Murta. (<a href="http://www.cs.man.ac.uk/~toby/alan/software/gpc.html" rel="nofollow">link</a>)</p> </blockquote> <p>The upperleft corner of Murta's Fig.2 illustrates a complicated polygon difference (and the remaining images illustrate other Boolean operations). <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/BooleanOps.jpg" alt="Boolean Ops"></p>