From Surf Wiki (app.surf) — the open knowledge base

Boolean operations on polygons

Type of geometry processing

Summary

Type of geometry processing

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). These are also used for activities like rapid prototyping in product design, medical device development, or even the creation of elaborate artworks.

Different boolean operations

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.{{citation

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, 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

Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

geometric-algorithms geometry-processing

Want to explore this topic further?

Ask Mako anything about Boolean operations on polygons — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report