A New Method of Applying Polygon Boolean Operations Based on Trapezoidal Decomposition

摘要

Boolean operations between planar polygons are fundamental operations in the GISciences. In this paper, a new algorithm based on trapezoidal decomposi tion is used to perform Boolean operations. Using this method, Boolean operations between polygons are transformed into Boolean operations between decomposed trapezoids. It is comparatively easier to process the simple trapezoids than arbitrary polygons. This new method avoids the complex computation of the spatial relation ship between the polygons' edges in the traditional algorithms, thus making the pro cedure more efficient and easier to understand. In addition, the proposed algorithm can work with concave polygons and those with holes.