混合曲线曲面的CG-LSPIA拟合算法

Conjugate-gradient progressive-iterative approximation for least square fitting of curves and surfaces

混合曲线曲面的拟合常应用于计算机辅助设计与制造中,但传统的数据拟合方法缺乏明显的几何意义.最小二乘渐进迭代逼近算法(progressive-iterative approximation for least square fitting, LSPIA)能通过迭代地调整控制点得到原始数据点的最小二乘拟合结果,具有明显的几何意义,但收敛速度较慢.为解决这个问题,本文提出一种基于共轭梯度法的最小二乘渐进迭代逼近算法(conjugate-gradient progressive-iterative approximation for least square fitting, CG-LSPIA).该算法首先计算共轭曲线曲面,再更新混合曲线曲面,在没有数值误差的情况下,迭代至多n步即可生成给定数据点的最小二乘拟合曲线曲面.此外,本文给出了CG-LSPIA算法收敛性证明.最后,以B样条曲线曲面为例,与LSPIA算法进行了比较,实验表明该算法有效,并且减少了达到相同拟合误差限所需的迭代次数与时间.

The fitting of curves and surfaces has been widely used in computer-aided design and computeraided manufacturing(CAD/CAM). However, traditional data fitting methods lack clear geometric meaning.By iteratively adjusting control points, the progressive-iterative approximation for least square fitting(LSPIA)algorithm can obtain the least square fitting results for given data points with intuitive geometric meaning, but the convergence rate is prolonged. Here, we design a novel LSPIA algorithm based on the conjugate-gradient method, named CG-LSPIA. First, the conjugate-gradient vector is constructed, and then the control points are precisely updated. The algorithm converges in at most n iterations. We also demonstrate the convergence of CG-LSPIA. In the absence of numerical error, the numerical examples show that our method is effective and greatly reduces the iteration time for reaching the fitting error limit compared with the LSPIA.