Opérations booléennes sur les polygones

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Les opérations booléennes sur les polygones sont un ensemble d’opérations booléennes (AND, OR, NOT, XOR...) effectuées sur un ou plusieurs ensembles de polygones en infographie. Ces ensembles d’opérations sont largement utilisés en infographie, en CAO, et en conception électronique (dans les logiciels de conception et de vérification de circuits intégrés).

Différentes opérations booléennes

Algorithmes[modifier | modifier le code]

Les algorithmes suivants permettent de faire des opérations booléennes sur les polygones :

Utilisations dans les logiciels[modifier | modifier le code]

Les premiers algorithmes effectuant des opérations booléennes sur les polygones reposaient sur l’utilisation de bitmaps. Mais l’utilisation de bitmaps pour modéliser la forme des polygones possède de nombreux inconvénients. L’un d’entre eux est que l’utilisation de la mémoire peut être très importante, du fait que la résolution des polygones est proportionnelle au nombre de bits utilisés pour les représenter. Plus la résolution désirée est grande, plus le nombre de bits nécessaire est important.

Les implémentations modernes des opérations booléennes sur les polygones tendent à utiliser des algorithmes de plan de balayage (ou de ligne de balayage). Une liste de documents faisant usage de tels algorithmes pour effectuer des opérations booléennes sur les polygones se trouve dans les références.

Les opérations booléennes sur des polygones convexes et sur des polygones monotones de même direction peuvent être effectuées en temps linéaire[1].

Notes[modifier | modifier le code]

  1. Katz, Matthew J.; Overmars, Mark H.; Sharir, Micha (1992), "Efficient hidden surface removal for objects with small union size", Computational Geometry: Theory and Applications 2 (4): 223–234, doi:10.1016/0925-7721(92)90024-M.

Bibliographie[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Logiciels