Area Partitioning Algorithm of Boolean Operations on Highly Complicated 2D Polygons[J]. Journal of Image and Graphics, 2007, 12(3): 552. DOI: 10.11834/jig.20070329.
Area Partitioning Algorithm of Boolean Operations on Highly Complicated 2D Polygons
Boolean operations on a kind of highly complicated 2D polygons having a large amount of data is concerned.Each polygon is composed of line segments and arc segments
which has a great number of vertices and is of a complicated geometric shape.This algorithm of Boolean operations is introduced specially for these 2D polygons.By area partitioning
the algorithm calculates the intersection points of two polygons.Then it determines the crossing condition at the position of each intersection point
and traces the edges of polygons to form a closed cycle according to the requirement of union
intersection or subtract operation.The results are also 2D polygons.The algorithm is designed from the aspect of practicality
avoiding the complex mathematic reasoning.It can be coded conveniently and improves the efficiency of Boolean operations greatly in practice.