Opérations booléennes sur les polygones

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

• 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

• 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

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

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