Approximation of an open polygonal curve with a minimum number of circular arcs and biarcs
Approximation of an open polygonal curve with a minimum number of circular arcs and biarcs
复制标题
具有最少数量的圆弧和双弧的开放多边形曲线的近似
DOI：
10.1016/j.comgeo.2007.10.009
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
A. Sturm
中科院分区：
文献类型：
--
作者：
R. Drysdale;G. Rote;A. Sturm
我们提出了一种用最少数量的圆弧来近似给定的开放多边形曲线的算法。在计算机辅助制造环境中，切削刀具的路径通常用圆弧和直线段来描述。用于用高阶曲线逼近多边形曲线的贪婪算法可以在文献中找到。如果没有理论界限，就很难评价这些算法的质量。我们提出了一种算法，可以找到一系列近似多边形曲线的圆弧，同时保持在给定的公差范围内。该系列包含任何此类系列中最少数量的弧。对于具有 n 个顶点的原始多边形链，我们的算法需要 O(n2logn) 时间。使用类似的方法，我们设计了一种运行时间为 O(n2logn) 的算法，用于针对给定切线方向的点序列计算具有最小数量双弧的切线连续近似。
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(n2logn) time for an original polygonal chain with n vertices. Using a similar approach, we design an algorithm with a runtime of O(n2logn), for computing a tangent-continuous approximation with the minimum number of biarcs, for a sequence of points with given tangent directions.