Report Number: CS-TR-96-1568
Institution: Stanford University, Department of Computer Science
Title: Algorithms for computing intersection and union of toleranced polygons with applications
Author: Cazals, Frederic
Author: Ramkumar, G. D. S.
Date: April 1996
Abstract: Since mechanical operations are performed only up to a certain precision, the geometry of parts involved in real life products is never known precisely. Nevertheless, operations on toleranced objects have not been studied extensively. In this paper, we initiate a study of the analysis of the union and intersection of toleranced simple polygons. We provide a practical and efficient algorithm that stores in an implicit data structure the information necessary to answer a request for specific values of the tolerances without performing a computation from scratch. If the polygons are of sizes m and n, and s is the number of intersections between edges occuring for all the combinations of tolerance values, the pre-processed data structure takes O(s) space and the algorithm that computes a union/intersection from it takes O((n+m) log(s) + k' + k log(k)) time where k is the number of vertices of the union/intersection and k <= k' <= s. Although the algorithm is not output sensitive, we show that the expectations of k and k' remain within a constant factor tau, a function of the input geometry. Finally, we list interesting applications of the algorithms related to feasibility of assembly and assembly sequencing of real assemblies.
http://i.stanford.edu/pub/cstr/reports/cs/tr/96/1568/CS-TR-96-1568.pdf