Abstract
We present robust algorithms for set operations and affine transformations on curved shapes in the plane using approximate geometric primitives. We use a refinement algorithm to ensure consistency. Its computational complexity is O(n log n + k) for an input of size n with k = O(n2) consistency violations. The output is as accurate as the geometric primitives. We validate our algorithms using sequences of six set operations and affine transforms on shapes bounded by algebraic curve segments of degree 1 to 6. We test generic and degenerate inputs.
