Computing Geometric Boolean Operations by Input Directed Decomposition.

Abstract

This paper presents an algorithm to perform regularized Boolean operations on collections of simple polygons. The algorithm accepts two arbitrarily complex collections of disjoint polygons and returns two collections of polygons corresponding to the union and intersection respectively. The algorithm is efficient and generalizes to higher dimensions. Given two collections of polygons, the algorithm recursively decomposes them into fragments using splitting lines determined from the collections' edges. This approach, which is called input directed decomposition, maintains exact representations of objects, and easily classifies an edge into either the union or the intersection set. By the use of edge orientation information, ambiguities caused by objects that touch along an edge are avoided. After edge classification, edge connectivity of polygons is used to allow creation of the polygons belonging to the union and the intersection collections.