• Source: Boolean operations on polygons

Boolean operations on polygons are a set of Boolean operations (AND, OR, NOT, XOR, ...) operating on one or more sets of polygons in computer graphics. These sets of operations are widely used in computer graphics, CAD, and in EDA (in integrated circuit physical design and verification software).




Algorithms


Greiner–Hormann clipping algorithm
Vatti clipping algorithm
Sutherland–Hodgman algorithm (special case algorithm)
Weiler–Atherton clipping algorithm (special case algorithm)




Uses in software


Early algorithms for Boolean operations on polygons were based on the use of bitmaps. 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.
Modern implementations for Boolean operations on polygons tend to use plane sweep algorithms (or Sweep line algorithms). A list of papers using plane sweep algorithms for Boolean operations on polygons can be found in References below.
Boolean operations on convex polygons and monotone polygons of the same direction may be performed in linear time.




See also


Boolean algebra
Computational geometry
Constructive solid geometry, a method of defining three-dimensional shapes using a similar set of operations
Geometry processing
General Polygon Clipper, a C library which computes the results of clipping operations




Notes






Bibliography






External links


UIUC Computational Geometry Pages
Constructive planar geometry, by Dave Eberly.
Software
Michael Leonov has compiled a comparison of polygon clippers.
Angus Johnson has also compared three clipping libraries.
SINED GmbH has compared performance and memory utilization of three polygon clippers Archived 2012-11-16 at the Wayback Machine.
A comparison of 5 clipping libraries at rogue-modron.blogspot.com
A commercial library for 3D Boolean operations: sgCore C++/C# library.
The comp.graphics.algorithms FAQ, solutions to mathematical problems with 2D and 3D Polygons.
Matthias Kramm's gfxpoly, a free C library for 2D polygons (BSD license).
Klaas Holwerda's Boolean, a C++ library for 2D polygons.
David Kennison's Polypack, a FORTRAN library based on the Vatti algorithm.
Klamer Schutte's Clippoly, a polygon clipper written in C++.
Michael Leonov's poly_Boolean, a C++ library, which extends the Schutte algorithm.
Angus Johnson's Clipper, an open-source freeware library (written in Delphi, C++ and C#) that's based on the Vatti algorithm.
clipper2 crate, a safe Rust wrapper for Angus Johnson's Clipper2 library.
GeoLib, a commercial library available in C++ and C#.
Alan Murta's GPC Archived 2011-02-27 at the Wayback Machine, General Polygon Clipper library.
PolygonLib Archived 2012-11-16 at the Wayback Machine, C++ and COM libraries for 2D polygons (optimized for large polygon sets, built-in spatial indices).

Kata Kunci Pencarian:

• Boolean operations on polygons
• Boolean operation
• Greiner–Hormann clipping algorithm
• Vatti clipping algorithm
• Polygon
• Sweep line algorithm
• 2D geometric model
• Rectilinear polygon
• Constructive solid geometry
• Clipping (computer graphics)