A Representation and Algorithm for Exact Computation of Cascaded Polygon Intersections with Fixed Storage Requirements

Abstract

Given a collection of polygons (or a collection of sets of polygons) with vertex points specified to some fixed-point precision, a technique is presented for accurately representing the intersection points formed by elements in the collection. In particular, we recognize that in 2D, the result of a series of intersections between polygons must be composed of line segments that are part of the line segments making up the original polygons. While our techniques greatly improve the accuracy of floating point representations for intersection points, we also provide algorithms based on rational arithmetic that compute these intersection points exactly. The storage required to represent an intersection vertex is slightly greater than four times the number of bits in the input resolution. Furthermore, no intermediate quantity requires resolution slightly greater than four times the resolution resolution of input vertex values, so implementation on existing computers at practical resolution can easily be done. Cascaded intersection operations do not require ever greater amounts of storage for vertex points, as would normally be required by a rational arithmetic approach. We also prove that a similar approach is not possible for any reasonable set of rotations.