Boolean operations on polygons by using trapezoidal decomposition

A new algorithm for Boolean operations is presented, which incorporates trapezoidal decomposition. The involved polygons are decomposed into two sets of trapezoids by the sweep-line, therefore Boolean operations on polygons are transformed into the Boolean operations on the decomposed trapezoids. Since these trapezoids are organized and stored by row, thus the Boolean operations between them are confined within one row; in consequence, the computation efficiency could be improved. Once the resulting set of trapezoids is obtained by implementing Boolean operations on the two original sets of trapezoids, the resulting polygons need to be constructed by means of boundary tracing. The proposed method avoids the complex computation of spatial relationship between polygons' edges in most vector algorithms for Boolean operation, thus making the whole procedures more efficient and understandable. In addition, by adopting multi-attribute condition extraction, this method could realize various Boolean operations in a unified way, without the necessity of designing respective methods targeting at each operation.