Computing Geometric Boolean Operations by Input Directed Decomposition.

Loading...
Thumbnail Image
Files
TR_87-8.pdf(1000.9 KB)
No. of downloads: 454
Publication or External Link
Date
1987
Authors
Vanecek, G.
Nau, D.S.
Advisor
Citation
DRUM DOI
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.
Notes
Rights