二维Bezier曲线求交算法及其比较.doc

二维Bezier曲线求交算法及其比较
朱根荣作者简介：朱根荣（1963—），男，浙江嘉兴人，高级讲师，主要研究方向：计算机辅助教学，E_mail:　jxzgr@

(秀洲党校，浙江 嘉兴 314000)

摘 要：用扫描法、两分查找法、牛顿法、离散法、解非线性方程组法求Bezier曲线交点的算法思想、在Adobe ActionScript3.0中的实现、存在问题、改进办法。并通过实验比较，发现解非线性方程组法是诸方法中效率最高，稳定性最好的方法。
关键词：Bezier曲线; 交点; 算法
中图分类号：TP391
Algorithms and comparison about finding intersection point between 2-dimensional Bezier curves
Zhu Gen-rong
（Xiuzhou Party School,　Jiaxing 314000,　Zhejiang China）
Abstract: Algorithms, realizing in ActionScript 3.0, problems, ways to improve about finding intersection point between two-dimensional Bezier curves using scanning method, binary-searching method, Newton method, discreting method and solving nonlinear equations method. By experiment, found that solving nonlinear equations method is a highest efficiency and most stable way.
Key words: Bezier curves; intersection point; algorithm

在用Flash制作经济学图形的演示动画时，经常遇到求两条曲线交点的问题。如最基本的需求曲线与供给曲线的交点。当然在设计时，两曲线的交点是显而易见的。困难的是在动画运行期间，正在移动的曲线，它们的交点该如何确定。这不仅需要所求交点位置准确，而且需要有较快的求交速度。一旦速度太慢，必然使动画产生时滞、显得不够流畅。鉴于设计时所画曲线均为Bezier曲线，因此问题便成了Bezier曲线求交问题。曹锋提到了用解高次方程组的方法求Bezier曲线的交点（曹锋，1998），并不简单。对于求两条三次Bezier曲线交点的问题，最终要转化为解关于参数的9次方程，不得不借助代数方程的数值解法。没有尝试，但受其启发，最终用“牛顿法解非线性方程组”（《数学手册》编写组，1979）实现了这一算法。王国瑾介绍了化曲为直的离散未交算法（王国瑾，2001），在AS3.0中实现后，效果不错。此外，还尝试了扫描法、两分查找法、牛顿法。在此对各种算法及其在AS3.0中的实现、存在问题、改进办法作一归纳总结，并通过实验比较证明：用牛顿法解非线性方程组的方法求两Bezier曲线交点，效率最高，也最稳定。
0．二维Bezier曲线的参数表示
在曲线运动过程中求交点，无疑需要借助有关算法在动作脚本中以代码实现。而要用代码求两Bezier曲线的交点，首先需要将曲线表示成函数。但对Bezier曲线而言，要用普通函数来表示是困难的，幸可用参数方程。当给定平面上n+1个点dii=0,1……n)，则n次Bezier曲线可表示为。其中Cni是组合数，即，而P(t)是参数为t时曲线的位置，是一个二维矢量。容易看出方程右边实际上是一个n次多项式，可整理成，这里系数ai是一个二维矢量。
鉴于AS3.0中无法重载运算符，因而无法定义矢量运算类，需将矢量方程化成标量方程，形如：，其中ai、bi为标量系数，可从给定控制点di求得 求解方法见参考文献[3]“2.1.2 Bezier曲线的矩阵表示”一节
。对于三次Bezier曲线，两参数方程的系数，，其中(xi,yi)为控制点di的横、纵坐标。MB为三次Bezier曲线的4×4矩阵(李原，2007)。下面给出根据控制点求参数方程系数的AS3.0代码如下：
代码1：根据Bezier曲线的控制点求参数方程的系数
//参数：ds为Bezier曲线控制点数组
//返回：参数方程系数数组：a0,a1,……an;b0,b1……bn
function getCoefs(ds:Array):Array {
var n:int;
var M:Array;
var coefs:Array=new Array(2);
coefs[0]=new Array(n+1);
coefs[1]=new Array(n+1);
n=ds.length;
M=new Array(n);
switch(n){
case 2:
M[0]=[1,0];
M[1]=[-1,1];
break;
case 3:
M[0]=[1,0,0];
M[1]=[-2,2,0];
M[2]=[1,-2,1];
break;
case 4:
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(var i:int=0;i端扫描，扫描线每到一个位置x，便计算两曲线纵坐标之差的绝对值dy=|y1-y2| (见图1) ，当dy小于给定的精度ε(一个小正数)，便将点(x,(y1+y2)/2)近似为两曲线的一个交点。代码如下：
代码2：扫描法求交点的基本代码
//参数：ca、cb表示两曲线，系自定义Bezier曲线类实例
//返回：交点数组
function scan(ca:McCurve,cb:McCurve):Array{
var left,right:Number; //两曲线相交区域的左、右端
var y1,y2:Number; //两曲线在x时的纵坐标
var ,dy:Number; //两曲线在x时纵坐标差的绝对值
图 1 扫描法求交点的算法描述
var step:Number=1; //步长
var eps:Number=1; //精度
var pts:Array; //存放交点的数组
for(x=left;x<=right;x+=step){
y1=ca.getYByX(x);
y2=cb.getYByX(x);
dy=Math.abs(y1-y2);
if(dy了突出算法重点，代码中没有给出两曲线相交区域左、右端的计算过程。这在ActionScript3.0中不难解决，可用MovieClip类的getBounds()、getRect()函数获得两曲线的包围盒，再用Rectangle类的intersection()方法求出两包围盒的相交区域(不妨记为rect)。于是相交区域的左、右端即为：
left=rect.x;
right=rect.x+rect.width;
1.1.2 存在问题
该算法虽然简单明了，但实现时问题不少。
⑴根据x值求y值的getYByX(x)函数的实现问题
由Bezier曲线的参数方程可知，要根据x值求y值，需分两步：
①先从⑴式中由给定的x值求出参数t值；
②再从⑵式中根据t值求出y值。
对于三次Bezier曲线，第①步要解关于t的一元三次方程，并不简单，所幸的是ActionScript3.0的BezierSegment类提供了根据方程系数求三次方根的函数getCubicRoota(a,b,c,d)。对于更高阶的Bezier曲线，就没有现存方法可用，只有用代数方程的数值解法求得近似解。
⑵无值、多值问题
上面第①步从方程⑴中求t值时，理论上有n个根。剔除[0,1]以外的值后，t值的个数在0与n之间，事先无法确定。相应地第②步得到的y值的个数与t值个数相同，也在0与n之间。因此，在计算dy=|y1y2|时，要根据y值的个数作出相应的处理。如果y1或y2的个数有一个为0，则回到循环开始进行下一循环；否则，需对每个y1值与每个y2值两两求差取绝对值，再行判断，需用到双循环。
var ys1,ys2:Array; //两曲线在横坐标为x时的纵坐标值数组
var i,j:int;
for(i=0;i}
}
⑶步长、精确度与交点个数
当步长step较大时，运行速度较快，但会发生交点漏失，即明明相交的地方，因步长较大被跨过，而未被检测到，使求得的交点个数小于实际交点数。
当步长step很小时，虽可能避免交点漏失的情况，但会带来两个问题，一是运行速度减慢，二会使交点个数虚增。即在一个交点附近，多次被判断为相交，使求得的交点个数大于实际交点数。而若减小精确度，又可能导致交点漏失。
1.1.3 改进思路
对于问题⑴，曾经想到将“对x值扫描”改为“对参数t扫描”，这样根据t值求相应的y值时，无须解n次方程，只需将t值代入方程⑵即可求得，且也避免了多值问题。但这仅仅得到了一条曲线的纵坐标值由于t值相同时，两条曲线的横坐标值未必相同，因此另一条曲线的纵坐标值不能简单地用相同的参数t值来求，而要根据一条曲线的x值求出另一条曲线的参数值(为了区别第一条曲线的参数，用s表示)，再由s求出另一条曲线的y值。
这里，根据一条曲线的x值求另一条曲线的参数值s还得解n次方程，还会有多个y值。改进效果不明显，放弃。
对于问题⑵，既然对参数t扫描仍然无法彻底解决多值问题，我们又尝试了对纵坐标y扫描。一般来说，给定x求y值时有多个值时，反过来给定y值求x值，多值问题会有所改善，但仍然无法避免。比如，当曲线为类似圆时，无论前者还是后者，都会有两个值。因此，考虑到兼容性，针对多值问题的这个双循环是免不了的了。
对于问题⑶，想到的是在扫描过程中，改变步长。即在不太可能相交时，步长大一点，在可能相交时，步长小一点。前者可以提高速度，后者可以避免交点漏失。想法虽好，但问题是，如何判断某一时刻是不太可能相交，还是将要相交，不太可能相交时，步长取多大，快要相交时步长又该取多大。一个简单的办法时，根据dy(在横向扫描时)的大小来决定步长。在代码2中计算出dy后，添加以下代码：
if(dyy; //dy较小时，将要相交，步长减小
else step=2; //否则取较大的步长
这一办法，虽然对求交速度和准确性有所改善，但改善不大。为此笔者又尝试了用两曲线的斜率、二阶导数、曲率作为决定下一步步长的依据，但都无功而返。最后采取的办法是，求扫描线处两曲线切线的交点，比较切线交点与扫描线的有向距离来判断两曲线的相交趋势，进而决定步长的大小。如图2中曲线A的切线LA与曲线B的切线LB相交于点P，点P与扫描线X的距离d即是判断相交趋势并决定步长大小的依据。图中是即将相交的情形，可取步长为d乘以一个小于1的正数。如果P在扫描线的左边，则说明暂时不会相交，步长可适当图 2 扫描法可变步长的确定
取大一些。当然在具体实现中，还有很多特殊情况需要考虑，在此，就不一一细说了。
这样一来，虽然增加了求曲线切线及其切线交点的运算，但可大大减少扫描的次数，实验证明，对提高求交速度和交点数量的准确性还是有一定效果的。
1.2两分(折半)查找法
1.2.1 算法与代码
两分查找法是一种十分常用的算法，通常用于在一个排序数组中寻找某个元素。笔者将其用于曲线求交，得归功于《数学手册》中用两分查找法解代数方程的启示。若设两曲线相交区域的左、右端为L、R(见1.1.1)，则两曲线交点的求解过程是：
①在区间[L,R]中插入中点M，将原区间分成左、右两个子区间[L,M]和[M,R]（图3
②分别计算x=L、M、R时两曲线y值之差(不是绝对值)，记为ldy、mdy、rdy，则左子区间两端两曲线y值之差为ldy，mdy；右子区间两端两曲线y值之差为mdy，rdy。
图 3 两分查找法求交点算法描述
③若某子区间两端y值之差同号，则直接无视，舍去这一子区间(图3中[M,R])。若某子区间两端y值之差异号(图3中[L,M])，在这一子区间中再插入中点M，将此子区间分成两段，重复②，③，直到子区间的长度小于给定精度ε，或者|ldy|、|mdy|、|rdy|中有一个小于ε为止。若是|ldy|<ε，则将L作为交点的横坐标，x=L时两y值的平均值作为交点的纵坐标；若是|mdy|或|rdy|<ε，则将M或R作为交点的横坐标，相应两y值的平均值作为交点的纵坐标。
代码3：两分查找求交的循环算法
function binary(ca:McCurve,cb:McCurve):Point{
var xs,dy:Array;
var pt:Point;
var eps:Number=0.1;
var y1,y2:Number;
var ints:Boolean=false; //相交标志
xs=[L,0,R]; //左、中、右的位置
dy=new Array(3); //x在左、中、右位置时两曲线的y值之差

while(xs[0] ints=true;
break;
}
}
if(ints) break;
if(dy[0]*dy[1]<0){dy[2]=dy[1];continue} //左段中包含交点
if(dy[1]*dy[2]<0){dy[0]=dy[1];continue} //右段中包含交点
}
return pt;
}
1.2.2 存在问题
与前面的扫描法相比，效率明显提高，但缺陷仍然不可避免：
(a)
(b)
(c)
⑴局限于只有一个交点的情形。若有多个交点，仅依靠上述代码无法求全。如图4(a)左、右两子区间，两端y值之差均异号，代码3中最后两个判断句均为真，但实际执行时，当执行了第一个判断，取了左子区间后，遇到continue语句，就开始对左子区间继续进行两分查找，而第二个判断则执行不到，从而把右子区间给舍去了。因而，只能求出左段包含的交点。而如果将continue语句去掉，则进入下一循环时，L=R=M，不满足循环条件，结束循环，于是一个交点也求不到。
图 4 两分查找法求交点存在的问题
⑵在根据x值求y值时仍然面临着无值、多值问题。如图4(b)，当x=L时，求曲线A的Y值时有两个，求曲线B的Y值时，无值，从而无法求得ldy；当x=R时也有类似情况而无法求得rdy。
⑶上下相切时(如图4(c))，ldy，mdy，rdy始终同号，切点将无法求得。
1.2.3 改进
对于问题⑴，改进办法是将两分查找法与分治法相结合。先将两曲线相交区域的x值域[L,R]分成若干区间，对每一区间运用两分查找法。但随之而来的问题是对区间[L,R]如何划分。这里采用的方法是，将相交区域的左、右端及两曲线所有位于相交区域内的控制点的横坐标值放入一个数组，将数组升序排列。这样数组中每相邻两元素便构成一个区间，再对每一区间运用两分查找法求出每一段中包含的交点。
对于问题②，类似于1.1.3中对相似问题的改进，在横向分割存在无值、多值问题时，改用纵向分割。即对相交区域的y值域进行分割，这样就变根据x值求y值为根据y值求x值，原来的问题在大部分情况下，可以得到解决，但仍有例外，参见1.1.3。
问题⑶在两分查找法中无法解决。
1.3牛顿法
1.3.1 算法与代码
这也是受《数学手册》中牛顿法解代数方程的启示。本来的思路是：从曲线的一个端点出发画切线，与x轴交于x1，再画曲线在x1处的切线交x轴交于x2，……直到切点与x轴的距离小于给定的精度ε为止。
该算法应用于曲线求交时，步骤如下：
①过两曲线的起点分别画切线LA、LB(在Bezier曲线中就是前两个控制点的连线)；(见图5)
②求出两切线的交点(记为P(x,y))；
③过P画垂线交曲线A、B于PA、PB；
图 5 牛顿法求交点算法描述
④计算PA、PB的距离dy，如果dy<ε，则将点(x,(PA.y+PB.y)/2)作为交点的近似。否则，过PA作曲线A的切线，过PB作曲线B的切线，重复②、③、④。
这里事实上隐含了数学中常用的化曲为直思想，将求曲线交点转化为求直线交点。AS3.0代码如下：
代码4 Newton法求两曲线交点
//参数ca、cb表示两曲线
//参数la、lb为两曲线过起点的切线
//返回两曲线的交点
function newton(ca,cb,la,lb):Point {
var xv,ya,yb,dy:Number;
var p,papb,pt:Point;
var eps:Number=0.1;
while (true) {
p=la.intersection(lb);
xv=p.x;
ya=ca.getYByX(xv)[0];
yb=cb.getYByX(xv)[0];
dy=Math.abs(ya-yb);
if (dy
la=ca.getTan(pa); //求曲线A过点pa的切线
lb=cb.getTan(pb); //求曲线B过点pb的切线
}
return pt;
}
上述代码中根据曲线上一点求过该点切线的函数getTan(P)，需先求出曲线在该点的斜率，再根据给定点、给定的切线长度及斜率求出切线段另一端点的坐标，即可得到切线。代码略。
1.3.2 存在问题
对于正常情况，循环二、三步即可得到一个交点，效率比两分查找法又有提高，但1.2.2中的前两个问题还是存在。
1.3.3 改进
要解决求多个交点的问题，总体思路还是分而治之的分治法，但分的方法与两分查找法不同。这里用的方法是，选阶数较低曲线两端点的连线作为LA，另一曲线的控制点两两相连所成直线为LB1，LB2……，再分别对LA与LB1，LA与LB2，……使用牛顿法求交(即重复本算法描述中第②、③、④步。假定曲线ca、cb的次数为na、nb，控制点数组为pa、pb，且naf(pt!=null) pts.push(pt);
}
代码中函数byPP(p1,p2)为根据两端点重新定义直线段。
无值、多值问题的解决。鉴于y值的个数取决于t值的个数，因此我们把由x值求y值转变为由x值求t值，得到t值组成的数组：tsx=crv.getTByX(P.x)。为了避免过P点的垂线与曲线不相交，从而tsx数组为空，再根据该点的纵坐标求一下t值，得到另一个t值组成的数组tsy=crv.getTByY(P.y)，两个数组元素的个数在0-n之间，即可能无值，也可能多值。而我们只需要一个值，到底取哪一个呢？我们约定一个原则：所取t值对应的曲线上点与给定点P的距离是所有t值中最小的为此，要做以下三步：
①在数组tsx中找出与给定点P距离最近的t值tx及最小距离dx。
若数组tsx非空，对tsx中的每一个t值，求出相应的y值，及与给定点P的纵坐标的距离，取距离最小时的t值为tx,最小距离记为dx；
若数组tsx为空，用给定点P与曲线两端点的距离大小进行取舍，若P与起点较近，取t=0,dx为P与起点的距离；否则若P与终点较近，则取t=1,dx为P与终点的距离。
②在数组tsy中找出与给定点P距离最近的t值ty及最小距离dy。
若数组tsy非空，对tsy中的每一个t值，求出相应的x值，及与给定点P的横坐标的距离，取距离最小时的t值为ty,最小距离记为dy；
若数组tsy为空，用与tsx为空同样的方法取t=0或t=1。
③比较dx与dy，若dx≤dy，取tx，否则取ty。
据此，可得到代码：
代码6，根据给定点(不一定在曲线上)求曲线的唯一参数值
//参数crv为曲线，p为给定点
//返回曲线的唯一参数值
function getTByP(crv:McCurve,p:Point):Number{
var x,y,tx,ty,dx,dy,d0,d1:Number;
var tsx,tsy:Array;
var i:int;
tsx=crv.getTByX(p.x);
tsy=crv.getTByY(p.y);
if(tsx.length<1){
d0=Point.distance(p,crv.ps[0]);
d1=Point.distance(p,crv.ps[crv.n]);
if(d0 if(tsy.length<1){
d0=Point.distance(p,crv.ps[0]);
d1=Point.distance(p,crv.ps[crv.n]);
if(d0dx var xa,ya,xb,yb:Number; //与参数值对应的两曲线上点的坐标
var ka,kb:Number; //曲线的斜率
var count:int=0;
while(count<5){
p=la.intersection(lb);
if(p==null) break;
ta=ca.getTByP(p);
xa=ca.getX(ta);
ya=ca.getY(ta);
ka=ca.getK(ta,"t");
pa=new Point(xa,ya);
tb=cb.getTByP(p);
xb=cb.getX(tb);
yb=cb.getY(tb);
kb=cb.getK(tb,"t");
pb=new Point(xb,yb);
d=Point.distance(pa,pb);
if(d<1){
return new Point((xa+xb)/2,(ya+yb)/2);
}
la.byPK(pa,ka);
lb.byPK(pb,kb);
count++;
}
return ret;
}
1.4离散法
1.4.1 算法描述
这是王国瑾等给出的Bezier曲线求交方法(王国墐，2001)，其基本思想还是化曲为直，将曲线求交转化成直线求交。但转化的方法与牛顿法不同，这里采用的是分割化直的办法，即将曲线分割成若干等次的Bezier曲线，当分割得很小时，用子曲线段两端点的连线代替子曲线段，然后求一曲线的所有子曲线替代直线段与另一曲线的所有子曲线替代直线段的交点，求得的交点即为原曲线交点的近似解。其堆栈算法描述如下：
⑴初始化
计算两曲线的先验分割次数(决定分割到何时为止)ar0，br0；
计算两曲线的包围盒
如果两包围盒不相交，则返回一个空数组，否则
将两曲线的控制点数组、当前分割次数(=0)压入堆栈。
⑵循环(直到堆栈为空止){
从堆栈中弹出两子曲线的控制点数组(记为aps,bps)，两曲线的当前分割次数(ar,br)
比较ar与ar0，br与br0的大小，根据比较结果分别处理{
情况1：ar≥ar0,br≥br0(两曲线的分割都已经够小了)
连结子曲线A的两个端点，得到直线段LA
连结子曲线B的两个端点，得到直线段LB
求LA与LB的交点
如果交点存在，将交点存入结果数组
情况2：ar相交，将A1、B的控制点数组、各自的当前分割次数压入堆栈
对A2重复上述操作
情况3：ar≥ar0,br当前分割次数压入堆栈
}
}
上述算法已在王国瑾给出的算法上作了些许改进，改进之处为包围盒相交性检查的位置。原算法在曲线分割后，不管子曲线与另一曲线(或其子曲线)的包围盒是否相交，不作判断，直接压入堆栈，在循环开始从堆栈弹出后再行检查。这样，无疑增加了大量的堆栈压入、弹出操作，浪费了机时；同时也会使堆栈的空间占用大量增加。据此，我们将包围盒相交性检查放在曲线分割后，压入堆栈之前，对于包围盒不相交的子曲线段直接无视，不再压入堆栈，仅把包围盒相交的子曲线段压入堆栈。虽然在代码上增加了不少，但实际检查次数并未增加，且在减少堆栈空间占用的同时，减少了大量无效的堆栈压入、弹出操作。实验证明，速度明显加快。
1.4.2 算法实现
上述算法，在实现时还有一些具体工作要做：
⑴先验分割次数的计算
王国瑾给出了先验分割次数(先验离散层数)的计算公式：
其中：n为Bezier曲线的次数；
ε为给定的精度(一个小正数)，使分割后子曲线上任一点到子曲线段两端点连线的距离小于此值；

实际上，为了简便，可视曲线的弯曲程度直接给定一个先验分割次数。
⑵曲线包围盒相交性判断
如果运用自定义的继承于MovieClip类的McCurve类，可用MovieClip类的getBounds()，getRect()方法获得曲线的包围盒。但鉴于本算法用到的仅是曲线的控制点，而McCurve类包含了大量与本算法无关的属性，建立众多该类的实例，难免会增加空间占用。因此在该算法实现上，我们没有用McCurve类。于是便不能直接应用上述获取包围盒的方法，需另行定义获取方法，当然这并不困难，无非是求出所有控制点的纵、横坐标的最小值、最大值，据此构造一个Rectangle类实例。进而可用Rectangle类的intersects方法判断两矩形是否相交。
⑶Bezier曲线的分割
这在不少资料上有介绍，可在t1=0.5处执行de Casteljan递推算法
，其中
Pi(i=0……n)是n阶Bezier曲线的n+1控制点,t∈[0,1]。所得的两条子Bezier曲线的控制点分别为
P0i(i=0……n) ,t∈[0,t1]和Pjn-j(j=0,……n) ,t∈[t1,1]。
代码8 Bezier曲线分割的de Casteljan递推算法
//参数pts为曲线的控制点数组，t为分割点的参数值
//返回两子曲线段的控制点数组
function seg(pts:Array,t:Number=0.5):Array {
var n:int=pts.length-1;
var P:Array=new Array(n);
var sub1,sub2:Array;
var i,j,k:int;
sub1=new Array(n);
sub2=new Array(n);
k=0;
P[k]=new Array(n);
for (i=0; i<=n; i++) {
P[k][i]=pts[i];
}
for (k=1; k<=n; k++) { //de Casteljan递推
P[k]=new Array(n-k);
for (i=0; i<=n-k; i++) {
P[k][i]=new Point();
P[k][i].x=(1-t)*P[k-1][i].x+t*P[k-1][i+1].x;
P[k][i].y=1-t)*P[k-1][i].y+t*P[k-1][i+1].y;
}
}
for (k=0; k<=n; k++) { //左边子曲线段的控制点数组
sub1[k]=P[k][0];
}
for (k=n; k>=0; k--) { //右边子曲线段的控制点数组
sub2[n-k]=P[k][n-k];
}
var bs:Array=new Array(2);
bs[0]=sub1;
bs[1]=sub2;
return bs;
}
1.4.3 存在问题与改进办法
该算法求交速度快，适用性好，而且避免了getYByX()或getXByY()可能出现的无值、多值问题。但在两曲线相切或接近相切时，也会出现交点个数虚增的情况。对此我们的改进办法是，在算法情况1中，求得一个非空交点后，将堆栈中所有分割次数大于曲线次数-1的元素全部弹出，不作处理，这样既节约了时间，又避免了交点个数的虚增。
另外一个需要注意的问题是，在求连线交点时，所得交点可能在线段之外，这可能导致所求交点不在两曲线之上。改进办法是判断所求交点是否位于两连线段的包围盒相交区域内，若是则返回该交点，否则返回null。在AS3.0中可以借助Rectangle类的intersection方法求得两连线段包围盒的相交区域，再用其containPoint(point)判断点是否在相交区域内。
1.5代数法(牛顿法解非线性方程组的方法)
若曲线由显函数表示，如曲线A：y=f(x)，曲线B：y=g(x)，则求曲线A、B的交点只需解方程组即可。但Bezier曲线通常只能用参数方程表示，现记曲线A的参数方程为：，曲线B的参数方程为，s，t∈[0,1]分别为曲线A、B的参数，na，nb分别为曲线A、B的次数,ai、bi、ai’、bi’为参数方程的系数。于是要求曲线A、B的交点，则需解以下两元Max(na,nb)次方程组：
。为方便将方程组记为
当曲线的阶数≥2时，传统的消元法，矩阵法便无能为力，因而常到此却步不前。偶而在《数学手册》中发现“牛顿法解非线性方程组”一节，顿时感觉眼睛一亮，真是踏破铁鞋无觅处，得来全不费功夫。拿来一试，一个字，爽!
1.5.1 算法描述
从一组近似解P0(s0，t0)开始用迭代公式
，，其中
直到据此求得的两曲线上的点PAn+1与PBn+1之间的距离小于给定的精度ε为止。
1.5.1 算法实现
作为迭代出发点的近似解的确定，可以用牛顿法中的方法，取次数较低曲线两端点的连线作为LA，取另一曲线的控制点两两相连所成直线为LB1、LB2……再求LA与LB1、LB2……的交点，根据每一个交点用1.3.3中的getTByP(crv,p)求出两