A divide-and-conquer algorithm for curve fitting

Diego Buchinger

doi:10.1016/j.cad.2022.103362

2022-10-01

PRE

Diego Buchinger *

Roberto Rosso

DOI：10.1016/j.cad.2022.103362

原文链接

原文求助

摘要

En 中文

Curve fitting is still an open problem which draws attention from many applications, such as computer-aided design, computer-aided manufacturing and reverse engineering. Splines such as Bezier, B-Spline and NURBS curves are usually employed in engineering applications and are intensively used for fitting purposes. The optimization of their shapes and localization parameters, however, is a very complex task. The literature presents many methods which empirically set some important parameters, such as the number of control points. As guessing such a value is difficult, this paper presents a new method to choose it through a multi-curve fitting method, based on linear least square optimizations, using a divide-and-conquer algorithm and an error tolerance threshold. Four prime procedures compose the method: the conquer step fits curves over subset point clouds; the combine step glues curve segments together with some selective continuity; the divide step splits subsets which are not properly fitted yet; and the merge step blends curve segments together. Several curve setups were tested in well-known benchmarks, using four-division strategies: bisection, error balance, point with the greatest curvature and point with the smallest curvature. The developed method allows for fast computation even for larger point clouds, and it was able to properly reconstruct each tested shape, even with the addition of synthetic noise. We also demonstrate that it can be significantly faster than a single-curve fitting using the same number of control points.(c) 2022 Elsevier Ltd. All rights reserved.

Keyword:

Data fitting

Curve reconstruction

B?zier

B-splines

Divide-and-conquer algorithm