谈谈"求线段交点"的几种算法(js实现,完整版)

"求线段交点"是一种非常基础的几何计算, 在很多游戏中都会被使用到.下面我就现学现卖的把最近才学会的一些"求线段交点"的算法总结一下, 希望对大家有所帮助.本文讲的内容都很初级, 主要是面向和我一样的初学者, 所以请各位算法帝们轻拍啊 嘎嘎

===============================算法一: 求两条线段所在直线的交点, 再判断交点是否在两条线段上.求直线交点时 我们可通过直线的一般方程 ax+by+c=0 求得(方程中的abc为系数,不是前面提到的端点,另外也可用点斜式方程和斜截式方程,此处暂且不论).然后根据交点的与线段端点的位置关系来判断交点是否在线段上. 公式如下图:实现代码如下 :

1. functionsegmentsIntr(a,b,c,d){
3. /**1解线性方程组,求线段交点.**/
4. //如果分母为0则平行或共线,不相交
5. vardenominator=(b.y-a.y)*(d.x-c.x)-(a.x-b.x)*(c.y-d.y);
6. if(denominator==0){
7. returnfalse;
8. }
10. //线段所在直线的交点坐标(x,y)
11. varx=((b.x-a.x)*(d.x-c.x)*(c.y-a.y)
12. +(b.y-a.y)*(d.x-c.x)*a.x
13. -(d.y-c.y)*(b.x-a.x)*c.x)/denominator;
14. vary=-((b.y-a.y)*(d.y-c.y)*(c.x-a.x)
15. +(b.x-a.x)*(d.y-c.y)*a.y
16. -(d.x-c.x)*(b.y-a.y)*c.y)/denominator;
18. /**2判断交点是否在两条线段上**/
19. if(
20. //交点在线段1上
21. (x-a.x)*(x-b.x)<=0&&(y-a.y)*(y-b.y)<=0
22. //且交点也在线段2上
23. &&(x-c.x)*(x-d.x)<=0&&(y-c.y)*(y-d.y)<=0
24. ){
26. //返回交点p
27. return{
28. x:x,
29. y:y
30. }
31. }
32. //否则不相交
33. returnfalse
35. }

算法一思路比较清晰易懂, 但是性能并不高. 因为它在不确定交点是否有效(在线段上)之前, 就先去计算了交点, 耗费了较多的时间.如果最后发现交点无效, 那么之前的计算就白折腾了. 而且整个计算的过程也很复杂.那么有没有一种思路,可以让我们先判断是否存在有效交点,然后再去计算它呢?显然答案是肯定的. 于是就有了后面的一些算法.===============================算法二: 判断每一条线段的两个端点是否都在另一条线段的两侧, 是则求出两条线段所在直线的交点, 否则不相交.第一步判断两个点是否在某条线段的两侧, 通常可采用投影法:求出线段的法线向量, 然后把点投影到法线上, 最后根据投影的位置来判断点和线段的关系. 见下图点a和点b在线段cd法线上的投影如图所示, 这时候我们还要做一次线段cd在自己法线上的投影(选择点c或点d中的一个即可).主要用来做参考.图中点a投影和点b投影在点c投影的两侧, 说明线段ab的端点在线段cd的两侧.同理, 再判断一次cd是否在线段ab两侧即可.求法线 , 求投影 什么的听起来很复杂的样子, 实际上对于我来说也确实挺复杂,在几个月前我也不会(念书那会儿的几何知识都忘光了 :'( )'不过好在学习和实现起来还不算复杂, 皆有公式可循:求线段ab的法线:

1. varnx=b.y-a.y,
2. ny=a.x-b.x;
3. varnormalLine={x:nx,y:ny};

注意: 其中 normalLine.x和normalLine.y的几何意义表示法线的方向, 而不是坐标.求点c在法线上的投影位置:

1. vardist=normalLine.x*c.x+normalLine.y*c.y;

注意: 这里的"投影位置"是一个标量, 表示的是到法线原点的距离, 而不是投影点的坐标.通常知道这个距离就足够了.当我们把图中 点a投影(distA),点b投影(distB),点c投影(distC) 都求出来之后, 就可以很容易的根据各自的大小判断出相对位置.distA==distB==distC 时, 两条线段共线distA==distB!=distC 时, 两条线段平行distA 和 distB 在distC 同侧时, 两条线段不相交.distA 和 distB 在distC 异侧时, 两条线段是否相交需要再判断点c点d与线段ab的关系.前面的那些步骤, 只是实现了"判断线段是否相交", 当结果为true时, 我们还需要进一步求交点.求交点的过程后面再说, 先看一下该算法的完整实现 :

1. functionsegmentsIntr(a,b,c,d){
3. //线段ab的法线N1
4. varnx1=(b.y-a.y),ny1=(a.x-b.x);
6. //线段cd的法线N2
7. varnx2=(d.y-c.y),ny2=(c.x-d.x);
9. //两条法线做叉乘,如果结果为0,说明线段ab和线段cd平行或共线,不相交
10. vardenominator=nx1*ny2-ny1*nx2;
11. if(denominator==0){
12. returnfalse;
13. }
15. //在法线N2上的投影
16. vardistC_N2=nx2*c.x+ny2*c.y;
17. vardistA_N2=nx2*a.x+ny2*a.y-distC_N2;
18. vardistB_N2=nx2*b.x+ny2*b.y-distC_N2;
20. //点a投影和点b投影在点c投影同侧(对点在线段上的情况,本例当作不相交处理);
21. if(distA_N2*distB_N2>=0){
22. returnfalse;
23. }
25. //
26. //判断点c点d和线段ab的关系,原理同上
27. //
28. //在法线N1上的投影
29. vardistA_N1=nx1*a.x+ny1*a.y;
30. vardistC_N1=nx1*c.x+ny1*c.y-distA_N1;
31. vardistD_N1=nx1*d.x+ny1*d.y-distA_N1;
32. if(distC_N1*distD_N1>=0){
33. returnfalse;
34. }
36. //计算交点坐标
37. varfraction=distA_N2/denominator;
38. vardx=fraction*ny1,
39. dy=-fraction*nx1;
40. return{x:a.x+dx,y:a.y+dy};
41. }

最后 求交点坐标的部分 所用的方法看起来有点奇怪, 有种摸不着头脑的感觉.其实它和算法一 里面的算法是类似的,只是里面的很多计算项已经被提前计算好了.换句话说, 算法二里求交点坐标的部分 其实也是用的直线的线性方程组来做的.现在来简单粗略 很不科学的对比一下算法一和算法二:1 最好情况下, 两种算法的复杂度相同2 最坏情况, 算法一和算法二的计算量差不多3 但是算法二提供了 更多的"提前结束条件",所以平均情况下,应该算法二更优.实际测试下来, 实际情况也确实如此.前面的两种算法基本上是比较常见的可以应付绝大多数情况. 但是事实上还有一种更好的算法.这也是我最近才新学会的(我现学现卖了,大家不要介意啊...)===============================算法三: 判断每一条线段的两个端点是否都在另一条线段的两侧, 是则求出两条线段所在直线的交点, 否则不相交.(咦? 怎么感觉和算法二一样啊? 不要怀疑 确实一样 ... 囧)所谓算法三, 其实只是对算法二的一个改良, 改良的地方主要就是 :不通过法线投影来判断点和线段的位置关系, 而是通过点和线段构成的三角形面积来判断.先来复习下三角形面积公式: 已知三角形三点a(x,y) b(x,y) c(x,y), 三角形面积为:

1. vartriArea=((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x))/2;

因为 两向量叉乘==两向量构成的平行四边形(以两向量为邻边)的面积 , 所以上面的公式也不难理解.而且由于向量是有方向的, 所以面积也是有方向的, 通常我们以逆时针为正, 顺时针为负数.改良算法关键点就是:如果"线段ab和点c构成的三角形面积"与"线段ab和点d构成的三角形面积" 构成的三角形面积的正负符号相异,那么点c和点d位于线段ab两侧. 如下图所示:图中虚线所示的三角形, 缠绕方向(三边的定义顺序)不同, 所以面积的正负符号不同.下面还是先看代码:由于我们只要判断符号即可, 所以前面的三角形面积公式我们就不需要后面的 除以2 了.

1. functionsegmentsIntr(a,b,c,d){
3. //三角形abc面积的2倍
4. vararea_abc=(a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
6. //三角形abd面积的2倍
7. vararea_abd=(a.x-d.x)*(b.y-d.y)-(a.y-d.y)*(b.x-d.x);
9. //面积符号相同则两点在线段同侧,不相交(对点在线段上的情况,本例当作不相交处理);
10. if(area_abc*area_abd>=0){
11. returnfalse;
12. }
14. //三角形cda面积的2倍
15. vararea_cda=(c.x-a.x)*(d.y-a.y)-(c.y-a.y)*(d.x-a.x);
16. //三角形cdb面积的2倍
17. //注意:这里有一个小优化.不需要再用公式计算面积,而是通过已知的三个面积加减得出.
18. vararea_cdb=area_cda+area_abc-area_abd;
19. if(area_cda*area_cdb>=0){
20. returnfalse;
21. }
23. //计算交点坐标
24. vart=area_cda/(area_abd-area_abc);
25. vardx=t*(b.x-a.x),
26. dy=t*(b.y-a.y);
27. return{x:a.x+dx,y:a.y+dy};
29. }

最后 计算交点坐标的部分 和算法二同理.算法三在算法二的基础上, 大大简化了计算步骤, 代码也更精简. 可以说,是三种算法里, 最好的.实际测试结果也是如此.当然必须坦诚的来说, 在Javascript里, 对于普通的计算, 三种算法的时间复杂度其实是差不多的(尤其是V8引擎下).我的测试用例里也是进行变态的百万次级别的线段相交测试 才能拉开三种算法之间的差距.不过本着精益求精 以及学习的态度而言, 追求一个更好的算法, 总是有其积极意义的.好了 不啰嗦了, 就到这里吧.现学现卖的东西, 难免有错误, 还请大家不吝斧正. 先谢谢啦补充:后来微博上@miloyip (这个是真正的大牛, 是会自己写3D引擎的人哦 )还推荐了另外一种更好的算法, 不过我还没有理解透彻.等我学会了 再来和大家分享