基于粒子群算法求曲线/曲面间最小距离方法

摘要

最小距离问题在很多领域都有着重要的应用。当今社会的主流造型系统通常采用参数曲线、曲面模型。先前的算法大多存在诸如:计算较复杂、适用范围有限等缺点。人工智能算法灵活性较大,适用于复杂的曲线、曲面间的最小距离的求解,本文主要利用粒子群算法针对求解参数曲线、曲面间的最小距离问题进行研究,主要工作和成果归纳如下:
　　 1.根据粒子群优化算法的原理,传统的思路是将B样条曲线上的一个点设为一个粒子；然后根据粒子群算法的公式进行粒子几何位置的平移,但这样做可能出现曲线上的点平移后不会落在曲线上的情况。针对该特点,本文提出了一个基于参数域的求解两B样条曲线间最小距离的粒子群算法。该算法先在两B样条曲线的参数域内各随机地生成相同数量的粒子并随机进行一一配对；接着计算各对参数相应的曲线点对之间的距离和所有点对间的最小距离,并得到个体最优参数和群体最优参数；然后根据粒子群算法原理,反复迭代,不断更新各对粒子间的个体最优参数和群体最优参数,直至满足预先设定的算法结束条件,从而求得两B样条曲线间的最小距离。该算法计算简单,实验结果表明其效果较好。
　　 2.通过对上述求两B样条曲线间最小距离算法的性能和实验结果的分析,进一步提出了改进的算法。首先,优化粒子群的初始配对方法,采用最近点对配对取代随机配对,以提高算法的效率；其次,用粒子群算法给出的结果作为初值,进一步用牛顿迭代法进行迭代,以提高解的精度。实验结果表明,改进的算法在效率和解的精度上都得以提高。
　　 3.将求解曲线间的最小距离的方法推广到曲面的情况,提出了一个基于参数域的求解两B样条曲面间的最小距离的算法及其改进的算法。实验结果表明,所提出的算法收敛性好,具有较高的效率和精度。
　　 本文方法的应用范围广,其应用对象并不局限于B样条曲线曲面,可直接推广到其它形式的参数曲线曲面,其基本思路也适用于非参数形式的曲线曲面。该方法还可应用于点与曲线、点与曲面,曲线与曲面等不同形式的最小距离问题,具有进一步的研究空间。