Boolean operations on polygons are a set of Boolean operations (AND, OR, NOT, XOR, ...) operating on one or more sets of

polygon In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed '' polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two ...

s in computer graphics. These sets of operations are widely used in

computer graphics Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...

CAD Computer-aided design (CAD) is the use of computers (or ) to aid in the creation, modification, analysis, or optimization of a design. This software is used to increase the productivity of the designer, improve the quality of design, improve c ...

, and in

EDA EDA or Eda may refer to: Computing * Electronic design automation * Enterprise Desktop Alliance, a computer technology consortium * Enterprise digital assistant * Estimation of distribution algorithm * Event-driven architecture * Exploratory da ...

(in

integrated circuit An integrated circuit or monolithic integrated circuit (also referred to as an IC, a chip, or a microchip) is a set of electronic circuits on one small flat piece (or "chip") of semiconductor material, usually silicon. Large numbers of tiny ...

physical design and verification software). Boolean operations on shapes-en

Algorithms

* Greiner–Hormann clipping algorithm *

Vatti clipping algorithm The Vatti clipping algorithmBala R. Vatti"A generic solution to polygon clipping" Communications of the ACM, Vol 35, Issue 7 (July 1992) pp. 56–63. is used in computer graphics. It allows clipping of any number of arbitrarily shaped ''subject po ...

* 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 polygon In geometry, a polygon ''P'' in the plane is called monotone with respect to a straight line ''L'', if every line orthogonal to ''L'' intersects the boundary of ''P'' at most twice. Similarly, a polygonal chain ''C'' is called monotone with res ...

s of the same direction may be performed in

linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

Notes

Bibliography

* Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf, Computational Geometry - Algorithms and Applications, Second Edition, 2000 * Jon Louis Bentley and Thomas A. Ottmann
Algorithms for Reporting and Counting Geometric Intersections
IEEE Transactions on Computers, Vol. C-28, No. 9, September 1979, pp. 643–647 * Jon Louis Bentley and

Derick Wood Derick Wood (1940–2010) was an English computer scientist who worked for many years as a professor of computer science in Canada and Hong Kong. He was known for his research in automata theory and formal languages, much of which he published ...

An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles
IEEE Transactions on Computers, Vol. C-29. No. 7, July 1980, pp. 571–577 * Ulrich Lauther
An O(N log N) Algorithm for Boolean Mask Operations
18th Design Automation Conference, 1981, pp. 555–562 * James A. Wilmore
Efficient Boolean Operations on IC Masks
18th Design Automation Conference, 1981, pp. 571–579 * * Thomas Ottmann, Peter Widmayer, and Derick Wood,
A Fast Algorithm for the Boolean Masking Problem
" Computer Vision, Graphics, and Image Processing, 30, 1985, pp. 249–268 {{refend

External links

UIUC Computational Geometry Pages

by Dave Eberly. ;Software * Michael Leonov has compiled

* Angus Johnson has als
compared three clipping libraries
* SINED GmbH ha
compared performance and memory utilization of three polygon clippers
* A comparison of 5 clipping libraries a

* A commercial library for 3D Boolean operations
sgCore C++/C# library
* Th
comp.graphics.algorithms FAQ
solutions to mathematical problems with 2D and 3D Polygons. * Matthias Kramm'
gfxpoly
a free C library for 2D polygons (BSD license). * Klaas Holwerda'

a C++ library for 2D polygons. * David Kennison'
Polypack
a FORTRAN library based on the Vatti algorithm. * Klamer Schutte'
Clippoly
a polygon clipper written in C++. * Michael Leonov'

a C++ library, which extends the Schutte algorithm. * Angus Johnson'
Clipper
an open-source freeware library (written in Delphi, C++ and C#) that's based on the Vatti algorithm.
GeoLib
a commercial library available in C++ and C#. * Alan Murta'
GPC
General Polygon Clipper library.
PolygonLib
C++ and COM libraries for 2D polygons (optimized for large polygon sets, built-in spatial indices). Geometric algorithms Geometry processing

Algorithms

Uses in software

See also

Notes

Bibliography

External links