Boolean operations on polygons are a set of Boolean operation

Boolean operation

Boolean operation or Boolean operator may refer to one of the following related meanings.*Boolean function*an operation in a Boolean algebra; in particular:**operations over the algebra of sets: union , intersection , etc....

s (AND, OR, NOT, XOR, ...) operating on one or more sets of polygon

Polygon

In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...

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

Computer graphics

Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....

, CAD, and in EDA

Electronic design automation

Electronic design automation is a category of software tools for designing electronic systems such as printed circuit boards and integrated circuits...

 (in integrated circuit

Integrated circuit

An integrated circuit or monolithic integrated circuit is an electronic circuit manufactured by the patterned diffusion of trace elements into the surface of a thin substrate of semiconductor material...

 physical design and verification software).

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 algorithm

Sweep line algorithm

In computational geometry, a sweep line algorithm or plane sweep algorithm is a type of algorithm that uses a conceptual sweep line or sweep surface to solve various problems in Euclidean space...

s). A list of papers using plane sweep algorithms for Boolean operations on polygons can be found in References below.

Boolean operations on convex polygon

Convex polygon

In geometry, a polygon can be either convex or concave .- Convex polygons :A convex polygon is a simple polygon whose interior is a convex set...

s and monotone polygon

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 P at most twice....

s of the same direction may be performed in linear time.

See also

• Boolean algebra (logic)
• Computational geometry
  Computational geometry
  Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
  
  
• Constructive solid geometry
  Constructive solid geometry
  Constructive solid geometry is a technique used in solid modeling. Constructive solid geometry allows a modeler to create a complex surface or object by using Boolean operators to combine objects...
  
  
• General Polygon Clipper, a C library which computes the results of clipping operations

External links

• UIUC Computational Geometry Pages
• Constructive planar geometry, by Dave Eberly.

Software

• 3D Boolean operations in sgCore C++/C# library
• Michael Leonov has compiled a comparison of polygon clippers.
• Angus Johnson has also compared three clipping libraries.
• A comparison of 5 clipping libraries at rogue-modron.blogspot.com
• The comp.graphics.algorithms FAQ, solutions to mathematical problems with 2D and 3D Polygons.
• 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
  Vatti clipping algorithm
  The Vatti clipping algorithm is used in computer graphics. It allows clipping of any number of arbitrarily shaped subject polygons by any number of arbitrarily shaped clip polygons. Unlike the Sutherland–Hodgman and Weiler–Atherton polygon clipping algorithms, the Vatti algorithm does not restrict...
  
  .
• GeoLib, a commercial library available in C++ and C#.
• Alan Murta's GPC, General Polygon Clipper library.