BIARC APPROXIMATION, SIMPLIFICATION AND SMOOTHING OF POLYGONAL CURVES BY MEANS OF VORONOI-BASED TOLERANCE BANDS
MARTIN HEIMLICH, Martin Held · International Journal of Computational Geometry & Applications · 2008
We present an algorithm for approximating multiple closed polygons in a tangent-continuous manner with circular biarcs. The approximation curves are guaranteed to lie within a user-specified tolerance of the original input. If requested, our algorithm can also ensure that the input is within a user-specified tolerance of the approximation curves. These tolerances can be either symmetric, asymmetric, one-sided, or even one-sided and completely disconnected from the inputs. Our algorithm makes use of Voronoi diagrams to build disjoint and continuous tolerance bands for every polygon of the input. In a second step the approximation curves are fitted into the tolerance bands. Our algorithm has a worst-case complexity of O(n log n) for an n-vertex input. Extensive experiments with synthetic and real-world data sets show that our algorithm generates approximation curves with significantly fewer approximation primitives than previously proposed algorithms. This difference becomes more prominent the larger the tolerance threshold is or the more severe the noise in the input is. In particular, no heuristic is needed for smoothing noisy input prior to the actual approximation. Rather, our approximation algorithm can be used to smooth out noise in a reliable manner.