Boolean operations on polygons
Boolean operations on polygons are a set of operations (which include AND, OR, NOT, XOR, etc.) operating on one or more sets of polygons. These sets of operations are widely used in VLSI 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 those Boolean operations 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.
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, "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, "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
- J. Nievergelt and F. P. Preparata, "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