二维Bezier曲线求交算法及其比较朱根荣1(秀洲党校，浙江嘉兴314000)摘要：用扫描法、两分查找法、牛顿法、离散法、解非线性方程组法求Bezier曲线交点的算法思想、在AdobeActionScript3.0中的实现、存在问题、改进办法。并通过实验比较，发现解非线性方程组法是诸方法中效率最高，稳定性最好的方法。关键词：Bezier曲线;交点;算法：TP391Algorithmsandcomparisonaboutfindingintersectionpointbetween2-dimensionalBeziercurvesZhuGen-rong（XiuzhouPartySchool,激axing314000,Zhe激angChina）Abstract:Algorithms,realizinginActionScript3.0,problems,waystoimproveaboutfindingintersectionpointbetweentwo-dimensionalBeziercurvesusingscanningmethod,binary-searchingmethod,Newtonmethod,discretingmethodandsolvingnonlinearequationsmethod.Byexperiment,foundthatsolvingnonlinearequationsmethodisahighestefficiencyandmoststableway.Keywords:Beziercurves;intersectionpoint;algorithm在用Flash制作经济学图形的演示动画时，经常遇到求两条曲线交点的问题。如最基本的需求曲线与供给曲线的交点。当然在设计时，两曲线的交点是显而易见的。困难的是在动画运行期间，正在移动的曲线，它们的交点该如何确定。这不仅需要所求交点位置准确，而且需要有较快的求交速度。一旦速度太慢，必然使动画产生时滞、显得不够流畅。鉴于设计时所画曲线均为Bezier曲线，因此问题便成了Bezier曲线求交问题。曹锋提到了用解高次方程组的方法求Bezier曲线的交点（曹锋，1998），并不简单。对于求两条三次Bezier曲线交点的问题，最终要转化为解关于参数的9次方程，不得不借助代数方程的数值解法。没有尝试，但受其启发，最终用“牛顿法解非线性方程组”（《数学手册》编写组，1979）实现了这一算法。王国瑾介绍了化曲为直的离散未交算法（王国瑾，2001），在AS3.0中实现后，效果不错。此外，还尝试了扫描法、两分查找法、牛顿法。在此对各种算法及其在AS3.0中的实现、存在问题、改进办法作一归纳总结，并通过实验比较证明：用牛顿法解非线性方程组的方法求两Bezier曲线交点，效率最高，也最稳定。1作者简介：朱根荣（1963—），男，浙江嘉兴人，高级讲师，主要研究方向：计算机辅助教学，E_mail:jxzgr@1630．二维Bezier曲线的参数表示在曲线运动过程中求交点，无疑需要借助有关算法在动作脚本中以代码实现。而要用代码求两Bezier曲线的交点，首先需要将曲线表示成函数。但对Bezier曲线而言，要用普通函数来表示是困难的，幸可用参数方程。当给定平面上n+1个点di(i=0,1……n)，则n次Bezier曲线可表示为。其中Cni是组合数，即，而P(t)是参数为t时曲线的位置，是一个二维矢量。容易看出方程右边实际上是一个n次多项式，可整理成，这里系数ai是一个二维矢量。鉴于AS3.0中无法重载运算符，因而无法定义矢量运算类，需将矢量方程化成标量方程，形如：，其中ai、bi为标量系数，可从给定控制点di求得1。对于三次Bezier曲线，两参数方程的系数，，其中(xi,yi)为控制点di的横、纵坐标。MB为三次Bezier曲线的4×4矩阵(李原，2007)。下面给出根据控制点求参数方程系数的AS3.0代码如下：代码1：根据Bezier曲线的控制点求参数方程的系数//参数：ds为Bezier曲线控制点数组//返回：参数方程系数数组：a0,a1,……an;b0,b1……bnfunctiongetCoefs(ds:Array):Array{varn:int;varM:Array;varcoefs:Array=newArray(2);coefs[0]=newArray(n+1);coefs[1]=newArray(n+1);n=ds.length;M=newArray(n);switch(n){case2:M[0]=[1,0];M[1]=[-1,1];break;case3:M[0]=[1,0,0];M[1]=[-2,2,0];M[2]=[1,-2,1];1求解方法见参考文献[3]“2.1.2Bezier曲线的矩阵表示”一节break;case4:M[0]=[1,0,0,0];M[1]=[-3,3,0,0];M[2]=[3,-6,3,0];M[3]=[-1,3,-3,1];break;}for(vari:int=0;i<n;i++){coefs[0][i]=0;coefs[1][i]=0;for(varj:int=0;j<n;j++){coefs[0][i]+=(M[i][j]*ds[j].x);coefs[1][i]+=(M[i][j]*ds[j].y)}}returncoefs;}1.二维Bezier曲线求交算法及其优化1.1扫描法(步进法)1.1.1算法与代码扫描法是最先想到的求交方法，基本思...