Boolean operations on polygons

<h2 id="algorithms">Algorithms</h2>
<ul><li><a href="/facts/Greiner%25E2%2580%2593Hormann_clipping_algorithm/gWlvFqTr">Greiner–Hormann clipping algorithm</a></li>
<li><a href="/facts/Vatti_clipping_algorithm/TVqPvjA2">Vatti clipping algorithm</a></li>
<li><a href="/facts/Sutherland%25E2%2580%2593Hodgman_algorithm/WDrYbGUl">Sutherland–Hodgman algorithm</a> (special case algorithm)</li>
<li><a href="/facts/Weiler%25E2%2580%2593Atherton_clipping_algorithm/zHnWENLa">Weiler–Atherton clipping algorithm</a> (special case algorithm)</li></ul>
<h2 id="uses-in-software">Uses in software</h2>
<p>Early algorithms for Boolean operations on polygons were based on the use of <a href="/facts/Bitmaps/Fr80ySnT">bitmaps</a>. Using bitmaps in modeling polygon shapes has many drawbacks. One of the drawbacks is that the memory usage can be very large, since the resolution of polygons is proportional to the number of bits used to represent polygons. The higher the resolution is desired, the more the number of bits is required.
</p><p>Modern implementations for Boolean operations on polygons tend to use plane sweep algorithms (or <a href="/facts/Sweep_line_algorithm/phUJCw6U">Sweep line algorithms</a>). A list of papers using plane sweep algorithms for Boolean operations on polygons can be found in References below.
</p><p>Boolean operations on <a href="/facts/Convex_polygon/7x35w610">convex polygons</a> and <a href="/facts/Monotone_polygon/16N42zJL">monotone polygons</a> of the same direction may be performed in <a href="/facts/Linear_time/77T62gmf">linear time</a>.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Boolean_algebra/VkCToAmg">Boolean algebra</a></li>
<li><a href="/facts/Computational_geometry/eeaotQtl">Computational geometry</a></li>
<li><a href="/facts/Constructive_solid_geometry/Dcs2fzyU">Constructive solid geometry</a>, a method of defining three-dimensional shapes using a similar set of operations</li>
<li><a href="/facts/Geometry_processing/Hq3So4MP">Geometry processing</a></li>
<li><a href="/facts/General_Polygon_Clipper/TmwSKsbh">General Polygon Clipper</a>, a C library which computes the results of clipping operations</li></ul>
<h2 id="notes">Notes</h2>

<h2 id="bibliography">Bibliography</h2>

<ul><li>Mark de Berg, Marc van Kreveld, <a href="/facts/Mark_Overmars/4MzGpDBq">Mark Overmars</a>, and Otfried Schwarzkopf, Computational Geometry - Algorithms and Applications, Second Edition, 2000</li>
<li>Jon Louis Bentley and Thomas A. Ottmann, <a href="https://ieeexplore.ieee.org/document/1675432/;jsessionid=C7C5DA2FF6075A109E90E53B7071A60E?arnumber=1675432">Algorithms for Reporting and Counting Geometric Intersections</a>, IEEE Transactions on Computers, Vol. C-28, No. 9, September 1979, pp. 643–647</li>
<li><a href="/facts/Jon_Louis_Bentley/WEK7bgSs">Jon Louis Bentley</a> and <a href="/facts/Derick_Wood/dGFHnzJG">Derick Wood</a>, <a href="https://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1675628">An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles</a>, IEEE Transactions on Computers, Vol. C-29. No. 7, July 1980, pp. 571–577</li>
<li>Ulrich Lauther, <a href="http://portal.acm.org/citation.cfm?id=802358&jmp=abstract">An O(N log N) Algorithm for Boolean Mask Operations</a>, 18th Design Automation Conference, 1981, pp. 555–562</li>
<li>James A. Wilmore, <a href="http://portal.acm.org/citation.cfm?id=802360">Efficient Boolean Operations on IC Masks</a>, 18th Design Automation Conference, 1981, pp. 571–579</li>
<li>Nievergelt, J.; Preparata, F. P. (October 1982). "Plane-Sweep Algorithms for Intersecting Geometric Figures". <i>Communications of the ACM</i>. 25 (10): 739–747. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.83.3275">10.1.1.83.3275</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F358656.358681">10.1145/358656.358681</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:16606107">16606107</a>.</li>
<li>Thomas Ottmann, Peter Widmayer, and Derick Wood, "<a href="https://www.sciencedirect.com/science/article/pii/0734189X85901598">A Fast Algorithm for the Boolean Masking Problem</a>," Computer Vision, Graphics, and Image Processing, 30, 1985, pp. 249–268</li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://web.archive.org/web/20111106212300/http://compgeom.cs.uiuc.edu/~jeffe/compgeom/">UIUC Computational Geometry Pages</a></li>
<li><a href="https://web.archive.org/web/20081219103233/http://compgeom.cs.uiuc.edu/~jeffe/compgeom/code.html">Constructive planar geometry</a>, by Dave Eberly.</li></ul>
Software
<ul><li>Michael Leonov has compiled a <a href="https://web.archive.org/web/20110720075903/http://www.complex-a5.ru/polyboolean/comp.html">comparison of polygon clippers</a>.</li>
<li>Angus Johnson has also <a href="http://angusj.com/delphi/clipper.php#features">compared three clipping libraries</a>.</li>
<li>SINED GmbH has <a href="http://www.ulybin.de/products/polygonlib.php?lang=en#comparison">compared performance and memory utilization of three polygon clippers</a> <a href="https://web.archive.org/web/20121116204221/http://www.ulybin.de/products/polygonlib.php?lang=en#comparison">Archived</a> 2012-11-16 at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a>.</li>
<li>A comparison of 5 clipping libraries at <a href="http://rogue-modron.blogspot.com/2011/04/polygon-clipping-wrapper-benchmark.html">rogue-modron.blogspot.com</a></li>
<li>A commercial library for 3D Boolean operations: <a href="http://www.geometros.com">sgCore C++/C# library</a>.</li>
<li>The <a href="http://www.faqs.org/faqs/graphics/algorithms-faq/">comp.graphics.algorithms FAQ</a>, solutions to mathematical problems with 2D and 3D Polygons.</li>
<li>Matthias Kramm's <a href="http://gfxpoly.quiss.org/">gfxpoly</a>, a free C library for 2D polygons (BSD license).</li>
<li>Klaas Holwerda's <a href="http://boolean.klaasholwerda.nl/bool.html">Boolean</a>, a C++ library for 2D polygons.</li>
<li>David Kennison's <a href="https://web.archive.org/web/20081103090937/http://www.dkrz.de/ngdoc/ng/supplements/polypack/">Polypack</a>, a FORTRAN library based on the Vatti algorithm.</li>
<li>Klamer Schutte's <a href="http://clippoly.sourceforge.net/">Clippoly</a>, a polygon clipper written in C++.</li>
<li>Michael Leonov's <a href="https://web.archive.org/web/20110720075903/http://www.complex-a5.ru/polyboolean/comp.html">poly_Boolean</a>, a C++ library, which extends the Schutte algorithm.</li>
<li>Angus Johnson's <a href="http://sourceforge.net/projects/polyclipping/">Clipper</a>, an open-source freeware library (written in Delphi, C++ and C#) that's based on the <a href="/facts/Vatti_clipping_algorithm/TVqPvjA2">Vatti algorithm</a>.</li>
<li><a href="https://crates.io/crates/clipper2">clipper2 crate</a>, a safe Rust wrapper for Angus Johnson's Clipper2 library.</li>
<li>Nail Sharipov’s <a href="https://ishape-rust.github.io/iShape-js/overlay/overlay.html">iOverlay</a> Rust Polygon Boolean Operations library: Supports intersection, union, difference, xor, and self-intersections for all polygon varieties.</li>
<li><a href="http://www.geolib.co.uk/index.htm">GeoLib</a>, a commercial library available in C++ and C#.</li>
<li>Alan Murta's <a href="http://www.cs.man.ac.uk/~toby/alan/software/">GPC</a> <a href="https://web.archive.org/web/20110227070056/http://www.cs.man.ac.uk/~toby/alan/software/">Archived</a> 2011-02-27 at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a>, General Polygon Clipper library.</li>
<li><a href="http://www.ulybin.de/products/polygonlib.php?lang=en">PolygonLib</a> <a href="https://web.archive.org/web/20121116204221/http://www.ulybin.de/products/polygonlib.php?lang=en">Archived</a> 2012-11-16 at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a>, C++ and COM libraries for 2D polygons (optimized for large polygon sets, built-in spatial indices).</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Katz, Matthew J.; Overmars, Mark H.; Sharir, Micha (1992), "Efficient hidden surface removal for objects with small union size", Computational Geometry: Theory and Applications, 2 (4): 223–234, doi:10.1016/0925-7721(92)90024-M. <a href="/wiki/Computational_Geometry_(journal)" target="_blank">/wiki/Computational_Geometry_(journal)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Boolean operations on polygons open-in-new

Boolean operations on polygons