Bézier曲线间最近距离的计算方法

针对Bzier曲线间最近距离计算问题,提出一种简捷、可靠的计算方法.该方法以Bernstein多项式算术运算为工具,建立Bzier曲线间最近距离的计算模型;然后充分利用Bzier曲面的凸包性质和de Casteljau分割算法进行求解.该方法几何意义明确,能有效地避免迭代初始值的选择和非线性方程组的求解,并可进一步推广应用于计算Bzier曲线/曲面间的最近距离.实验结果表明,该方法简捷、可靠且容易实现,与Newton-Raphson方法的融合可进一步提高该方法的运行速度.

An effective and straightforward algorithm is developed for computation of minimum distance between two Bézier curves. This problem is firstly formulated in terms of solutions of a polynomial equation expressed in Bernstein basis by means of the arithmetic for multivariate Bernstein-form polynomials,and a novel solution method is proposed by using the convex hull property of Bézier surface and the de Casteljau algorithm. The proposed method is geometrically intuitive,can avoid the choice of initial values and the solution of non-linear equation system,and can also be further generalized to compute the minimum distance between a Bézier curve and a Bézier surface. Experimental results demonstrate that the algorithm is steady and effective,and can further improve its efficiency when integrated with Newton-Raphson method.

辽宁省科学技术计划(07L2160201);;中国科学院沈阳自动化所知识创新工程青年人才领域前沿基金(07A2080201)