前面的两种算法基本上是比较常见的可以应付绝大多数情况. 但是事实上还有一种更好的算法.
这也是我最近才新学会的(我现学现卖了,大家不要介意啊…)
算法三: 判断每一条线段的两个端点是否都在另一条线段的两侧, 是则求出两条线段所在直线的交点, 否则不相交.
(咦? 怎么感觉和算法二一样啊? 不要怀疑 确实一样 … 囧)
所谓算法三, 其实只是对算法二的一个改良, 改良的地方主要就是 :
不通过法线投影来判断点和线段的位置关系, 而是通过点和线段构成的三角形面积来判断.
先来复习下三角形面积公式: 已知三角形三点a(x,y) b(x,y) c(x,y), 三角形面积为:
<code>var triArea=( (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x) ) /2 ; </code>
因为 两向量叉乘==两向量构成的平行四边形(以两向量为邻边)的面积 , 所以上面的公式也不难理解.
而且由于向量是有方向的, 所以面积也是有方向的, 通常我们以逆时针为正, 顺时针为负数.
改良算法关键点就是:
如果”线段ab和点c构成的三角形面积”与”线段ab和点d构成的三角形面积” 构成的三角形面积的正负符号相异,
那么点c和点d位于线段ab两侧.
如下图所示:
图中虚线所示的三角形, 缠绕方向(三边的定义顺序)不同, 所以面积的正负符号不同.
下面还是先看代码:
由于我们只要判断符号即可, 所以前面的三角形面积公式我们就不需要后面的 除以2 了.
function segmentsIntr(a, b, c, d){ // 三角形abc 面积的2倍 var area_abc = (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x); // 三角形abd 面积的2倍 var area_abd = (a.x - d.x) * (b.y - d.y) - (a.y - d.y) * (b.x - d.x); // 面积符号相同则两点在线段同侧,不相交 (对点在线段上的情况,本例当作不相交处理); if ( area_abc*area_abd>=0 ) { return false; } // 三角形cda 面积的2倍 var area_cda = (c.x - a.x) * (d.y - a.y) - (c.y - a.y) * (d.x - a.x); // 三角形cdb 面积的2倍 // 注意: 这里有一个小优化.不需要再用公式计算面积,而是通过已知的三个面积加减得出. var area_cdb = area_cda + area_abc - area_abd ; if ( area_cda * area_cdb >= 0 ) { return false; } //计算交点坐标 var t = area_cda / ( area_abd- area_abc ); var dx= t*(b.x - a.x), dy= t*(b.y - a.y); return { x: a.x + dx , y: a.y + dy }; }
最后 计算交点坐标的部分 和算法二同理.
算法三在算法二的基础上, 大大简化了计算步骤, 代码也更精简. 可以说,是三种算法里, 最好的.实际测试结果也是如此.
当然必须坦诚的来说, 在Javascript里, 对于普通的计算, 三种算法的时间复杂度其实是差不多的(尤其是V8引擎下).
我的测试用例里也是进行变态的百万次级别的线段相交测试 才能拉开三种算法之间的差距.
总结
不过本着精益求精 以及学习的态度而言, 追求一个更好的算法, 总是有其积极意义的。以上就是利用js实现线段交点的几种算法，内容不是很深奥，希望对大家学习js有所帮助。
您可能感兴趣的文章: