Operazioni booleane sui poligoni
{{S|Matematica}}
[[File:Boolean operations on shapes-en.svg|thumbnail|Operazioni booleane sui poligoni]]
Le '''operazioni booleane sui poligoni''' sono un insieme di [[Connettivo logico|connettivi logici]] (AND, OR, NOT, XOR, ...) che [[operatore (matematica)|operano]] su uno o più insiemi di [[poligono|poligoni]].

Le operazioni booleane hanno frequenti applicazioni nella [[computer grafica]], nel [[Computer-aided design|CAD]] e nella ''[[Electronic design automation]]'' (progettazione di livello fisico per un [[circuito integrato]], e [[collaudo del software]]).

== Applicazioni nel ''software'' ==
I primi algoritmi per eseguire operazioni booleane sui poligoni erano [[implementazione|implementati]] su [[grafica bitmap]].
per "disegnare" i lati del poligono tramite bitmap, erano necessarie grandi quantità di [[Memoria (informatica)|memoria]], perché con un numero di bit necessario proporzionale alla risoluzione dell'immagine desiderata.

Perciò, si tende a rappresentare i poligoni tramite ''algoritmi sweep'' lineari o per il piano (di cui sono un esempio gli ''[[algoritmo scan line|algoritmi scan line]]'').

Le operazioni booleane su [[poligono#Convessità|poligoni convessi]] e su poligoni monotoni aventi la stessa direzione, hanno una [[complessità temporale#Tempo lineare|complessità lineare di calcolo]]<ref>{{cita pubblicazione| autore = Matthew J. Katz, Mark H. Overmars, Micha Sharir|doi=10.1016/0925-7721(92)90024-M|numero= 4| rivista = Computational Geometry: Theory and Applications| p = 223–234| titolo = Efficient hidden surface removal for objects with small union size| volume = 2| data = 1992}}</ref>.

La [[geometria solida costruttiva]] è un metodo per costruire oggetti tridimensionali, usando operazioni booleane su poligoni.

== Note ==
<references/>

== Voci correlate ==
* [[Algebra booleana]]
* [[Geometria computazionale]]
* [[Geometria solida costruttiva]]

== Collegamenti esterni ==
* [https://web.archive.org/web/20111106212300/http://compgeom.cs.uiuc.edu/~jeffe/compgeom/ Geometria computazine nel sito della UIUC]
* [https://web.archive.org/web/20081219103233/http://compgeom.cs.uiuc.edu/~jeffe/compgeom/code.html Geometria planare costruttiva], a cura di Dave Eberly.

{{Portale|matematica|informatica|architettura|design|ingegneria}}

[[Categoria:Algoritmi geometrici]]