Biarc approximation of polygons within asymmetric tolerance bands

We present an algorithm for approximating a simple planar polygon by a tangent-continuous approximation curve that consists of biarcs. Our algorithm guarantees that the approximation curve lies within a user-specified tolerance from the original polygon. If requested, the algorithm can also guarantee that the original polygon lies within a user-specified distance from the approximation curve. Both symmetric and asymmetric tolerances can be handled. In either case, the approximation curve is guaranteed to be simple. Simplicity of the approximation curve is achieved by restricting it to a 'tolerance band' which represents the user-specified tolerance and which takes into account bottlenecks of the input polygon. The tolerance band itself is computed by means of a regular grid and so-called k-dops. The basic algorithm is readily extended to compute biarc approximations of collections of polygonal curves simultaneously. Experimental results demonstrate that this algorithm computes biarc approximations of an n-vertex polygon with a close-to-minimum number of biarcs in roughly O(n log n) time. (C) 2004 Elsevier Ltd. All rights reserved.