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). thumbnail|right|Different boolean operations
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
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
Vidi još Bulova algebra Computational geometry Constructive solid geometry
Software Michael Leonov has compiled a comparison of polygon clippers. Angus Johnson has also compared three clipping libraries . SINED GmbH has compared performance and memory utilization of three polygon clippers . 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 , 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 , General Polygon Clipper library. PolygonLib , C++ and COM libraries for 2D polygons (optimized for large polygon sets, built-in spatial indices).
Категорија:Вики гимназијалац/Математичка гимназија Категорија:Геометријски алгоритми