کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414313 680885 2008 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
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
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 41, Issues 1–2, October 2008, Pages 31-47