Boolean operations on polygons

Boolean operations on polygons

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

Early algorithms for Boolean operations on polygons are based on the use of bit maps. Using bit maps in modelling 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.

References

* Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf, Computer Geometry - Algorithms and Applications, Second Edition, 2000
* Jon Louis Bentley and Thomas A. Ottmann, [http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1675432 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, [http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1675628 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, [http://portal.acm.org/citation.cfm?id=802358&jmp=abstract An O(N log N) Algorithm for Boolean Mask Operations] , 18th Design Automation Conference, 1981, pp. 555-562
* James A. Wilmore, [http://portal.acm.org/citation.cfm?id=802360 Efficient Boolean Operations on IC Masks] , 18th Design Automation Conference, 1981, pp. 571-579
* J. Nievergelt and F. P. Preparata, doi-inline|10.1145/358656.358681|Plane-Sweep Algorithms for Intersecting Geometric Figures, Communications of the ACM, October 1982, Vol. 25, No. 10, pp. 739-747
* 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

ee also

* Boolean algebra (logic)
* Computational geometry


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Boolean operation — 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 (set theory), intersection (set theory), etc. **Boolean operations on polygons… …   Wikipedia

  • Polygon — For other uses, see Polygon (disambiguation). Some polygons of different kinds In geometry a polygon (   …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • 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. It is one of the key techniques in computational… …   Wikipedia

  • List of combinatorial computational geometry topics — enumerates the topics of computational geometry that states problems in terms of geometric objects as discrete entities and hence the methods of their solution are mostly theories and algorithms of combinatorial character.See List of numerical… …   Wikipedia

  • Nef polygon — Nef polygons and Nef polyhedra are the sets of polygons (resp. polyhedra) which can be obtained from a finite set of halfplanes (halfspaces) by Boolean operations of set intersection and set complement. The objects are named after the Swiss… …   Wikipedia

  • logic, history of — Introduction       the history of the discipline from its origins among the ancient Greeks to the present time. Origins of logic in the West Precursors of ancient logic       There was a medieval tradition according to which the Greek philosopher …   Universalium

  • GPC General Polygon Clipper Library — The University of Manchester GPC library is a software library providing an API for computing the results of clipping operations on sets of polygons. It generalises the computer graphics clipping problem of intersecting polygons with polygons.The …   Wikipedia

  • Rectilinear polygon — Some examples of rectilinear polygons A rectilinear polygon is a polygon all of whose edges meet at right angles. Thus the interior angle at each vertex is either 90° or 270°. Rectilinear polygons are a special case of isothetic polygons. In many …   Wikipedia

  • Inkscape — infobox software name = Inkscape caption = Inkscape 0.46 developer = The Inkscape Team latest release version = 0.46 latest release date = release date|2008|3|24 programming language = C++ and GTK+ operating system = Linux, FreeBSD, Mac OS X,… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”