Opérations booléennes sur les polygones

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

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

Algorithme de Greiner-Hormann
Algorithme de Vatti
Algorithme de Sutherland-Hodgman (dans des cas particuliers)
Algorithme de Weiler-Atherton (dans des cas particuliers)

Utilisations dans les logiciels

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 d'articles faisant usage de tels algorithmes pour effectuer des opérations booléennes sur les polygones se trouve en bibliographie ci-dessous.

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].

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Boolean operations on polygons » (voir la liste des auteurs).

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

Voir aussi

Articles connexes

Algèbre de Boole (logique)
Géométrie algorithmique
Géométrie de construction de solides
General Polygon Clipper (en), une bibliothèque C effectuant des opérations booléennes sur des polygones

Bibliographie

Mark de Berg, Marc van Kreveld, Mark Overmars et Otfried Schwarzkopf, Computational Geometry - Algorithms and Applications, Second Edition, 2000
Jon Louis Bentley et Thomas A. Ottmann, « Algorithms for Reporting and Counting Geometric Intersections », IEEE Transactions on Computers, vol. C-28, No. 9, September 1979, p. 643–647
Jon Louis Bentley et Derick Wood, « An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles », IEEE Transactions on Computers, vol. C-29. No. 7, July 1980, p. 571–577
Ulrich Lauther, An O(N log N) Algorithm for Boolean Mask Operations, 18th Design Automation Conference, 1981, p. 555–562
James A. Wilmore, Efficient Boolean Operations on IC Masks, 18th Design Automation Conference, 1981, p. 571–579

Liens externes

UIUC Computational Geometry Pages
Constructive planar geometry, de Dave Eberly.

Logiciels

Michael Leonov a compilé une comparaison d’algorithmes.
Angus Johnson a également comparé trois bibliothèques d'opérations.
SINED GmbH a comparé les performances utilisation de mémoire de trois algorithmes.
Une comparaison de cinq bibliothèques : rogue-modron.blogspot.com
Une bibliothèque commerciale : sgCore C++/C# library.
La FAQ comp.graphics.algorithms, solutions aux problèmes mathématiques mettant en jeu des polygones 2D ou 3D.
Matthias Kramm's gfxpoly, une bibliothèque gratuite écrite en C pour des polygones 2D (sous licence BSD).
Klaas Holwerda's Boolean, une bibliothèque C++ pour les polygones 2D.
David Kennison's Polypack, une bibliothèque FORTRAN basée sur l'algorithme de Vatti.
Klamer Schutte's Clippoly, un algorithme d'opérations booléennes écrit en C++.
Michael Leonov's poly_Boolean, une bibliothèque C++ qui étend l'algorithme de Schutte.
Angus Johnson's Clipper, une bibliothèque gratuite et open-source (écrite en Delphi, C++ et C#) basée sur l'algorithme de Vatti.
GeoLib, une bibliothèque commerciale disponible en C++ et C#.
Alan Murta's GPC, General Polygon Clipper library.
PolygonLib, bibliothèques C++ et COM pour des polygones 2D.

Portail de l'informatique théorique
Portail de la géométrie

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

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