Operații booleene pe poligoane
Operațiile booleene pe poligoane sunt un set de conectivități logice (ȘI, SAU, NU, XOR, ...) care operează pe unul sau mai multe seturi de poligoane .
Operațiile booleene au aplicații frecvente în grafică pe computer , CAD și automatizarea proiectării electronice (proiectarea stratului fizic pentru un circuit integrat și testarea software-ului ).
Aplicații în software
Primii algoritmi care efectuează operații booleene pe poligoane au fost implementați pe grafică bitmap . pentru a „desena” laturile poligonului folosind bitmap-uri, erau necesare cantități mari de memorie , deoarece cu un număr necesar de biți proporțional cu rezoluția imaginii dorite.
Prin urmare, poligoanele tind să fie reprezentate prin algoritmi de măturare liniară sau plană (dintre care algoritmii de linie de scanare sunt un exemplu).
Operațiile booleene pe poligoane convexe și pe poligoane monotone având aceeași direcție au o complexitate de calcul liniară [1] .
Geometria solidă constructivă este o metodă de construire a obiectelor tridimensionale, utilizând operații booleene pe poligoane.
Notă
- ^ Matthew J. Katz, Mark H. Overmars, Micha Sharir, Eliminarea eficientă a suprafeței ascunse pentru obiecte cu dimensiuni mici ale uniunii , în Computational Geometry: Theory and Applications , vol. 2, nr. 4, 1992, p. 223-234, DOI : 10.1016 / 0925-7721 (92) 90024-M .
Elemente conexe
linkuri externe
- Calculul geometriei pe site-ul UIUC
- Geometrie plană constructivă , de Dave Eberly.