Logički operatori na poligonima

Logički operatori na poligonima obuhvataju operatore Bulove algebre (AND, OR, NOT, XOR, ...) koji se primenjuju na jednom ili vise mnogouglova u racunarskoj grafici. Ovi operatori se koriste u računarskoj grafici, CAD (computer-aided design) i u EDA (u integrisanom kolu fizičkog dizajna i vertifikaciji softvera).

Algoritmi

Vatti clipping algorithm
Sutherland–Hodgman algorithm (algoritam za specijalni slučaj)
Weiler–Atherton clipping algorithm (algoritam za specijalni slučaj)

Upotreba kod softvera

Prvi algoritmi za logičke operatore na mnogouglovima baziraju se na upotrebi bitmaps. Upotreba bitmaps u modeliranju poligonskih oblika ima mnogo nedostataka. Jedan od nedostataka je to što se troši puno memorije, pošto je rezolucija mnogougla proporcionalna broju bitova upotrebljenom za prikaz poligona. Što veću rezoluciju želimo, više bitova je potrebno.

Moderne implementatcije teže da koriste plane sweep algorithms (ili Sweep line algorithms). Spisak radova koji koriste plane sweep algorithms mogu se naći u referencama.

Bulove operacije na konveksnim mnogouglovima i monotonim mnogouglovima u istom pravcu mogu se izvršiti u linearnom vremenu.

Literatura

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
Nievergelt, J.; Preparata, F. P. (1982). „Plane-Sweep Algorithms for Intersecting Geometric Figures”. Communications of the ACM. 25 (10): 739—747. CiteSeerX: 10.1.1.83.3275.
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
Francisco Martínez, Antonio Jesús Rueda, Francisco Ramón Feito, A new algorithm for computing Boolean operations on polygons, Computers & Geosciences, Volume 35, Issue 6, June 2009, Pages 1177-1185, ISSN 0098-3004

Vidi još

Software

Michael Leonov has compiled a comparison of polygon clippers.
Angus Johnson has also compared three clipping libraries Архивирано на сајту Wayback Machine (13. јун 2010).
SINED GmbH has compared performance and memory utilization of three polygon clippers Архивирано на сајту Wayback Machine (16. новембар 2012).
A comparison of 5 clipping libraries at rogue-modron.blogspot.com
A commercial library for 3D Boolean operations: sgCore C++/C# library.
The comp.graphics.algorithms FAQ, solutions to mathematical problems with 2D and 3D Polygons.
Matthias Kramm's gfxpoly Архивирано на сајту Wayback Machine (1. новембар 2012), a free C library for 2D polygons (BSD license).
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.
GeoLib, a commercial library available in C++ and C#.
Alan Murta's GPC Архивирано на сајту Wayback Machine (27. фебруар 2011), General Polygon Clipper library.
PolygonLib Архивирано на сајту Wayback Machine (16. новембар 2012), C++ and COM libraries for 2D polygons (optimized for large polygon sets, built-in spatial indices).