R. L. Scot Drysdale, Günter Rote, and Astrid Sturm:
1. Approximation of an open polygonal curve with a minimum number
of circular
arcs
In: Abstracts of the 22nd European Workshop on Computational
Geometry,
Delphi, March 2006, pp. 25–28. (preliminary version with partial
results)
2. Approximation of an open polygonal curve with a minimum number
of circular
arcs and biarcs
Computational Geometry,
Theory and Applications 41 (2008), 31–47. doi:10.1016/j.comgeo.2007.10.009
Abstract
We present an algorithm for approximating a given open polygonal curve
with a
minimum number of circular arcs. In computer-aided manufacturing
environments,
the paths of cutting tools are usually described with circular arcs and
straight line segments. Greedy algorithms for approximating a polygonal
curve
with curves of higher order can be found in the literature. Without
theoretical bounds it is difficult to say anything about the quality of
these
algorithms. We present an algorithm which finds a series of circular
arcs
that approximate the polygonal curve while remaining within a given
tolerance
region. This series contains the minimum number of arcs of any such
series.
Our algorithm takes O(n2 log n) time
for
an original
polygonal chain
with n vertices.
Using a similar approach, we design an algorithm with a runtime of O(n2
log n), for computing a tangent-continuous
approximation with the
minimum number of biarcs, for a sequence of points with given tangent
directions.
Last update: May 29, 2008.