谈谈"求线段交点"的几种算法(js实现,完整版) |
您所在的位置：网站首页 › 函数交点个数公式 › 谈谈"求线段交点"的几种算法(js实现,完整版) |
谈谈"求线段交点"的几种算法(js实现,完整版)
|
"求线段交点"是一种非常基础的几何计算, 在很多游戏中都会被使用到. 下面我就现学现卖的把最近才学会的一些"求线段交点"的算法说一说, 希望对大家有所帮助. 本文讲的内容都很初级, 主要是面向和我一样的初学者, 所以请各位算法帝们轻拍啊 嘎嘎 引用 已知线段1(a,b) 和线段2(c,d) ,其中a b c d为端点, 求线段交点p .(平行或共线视作不相交)
=============================== 算法一: 求两条线段所在直线的交点, 再判断交点是否在两条线段上. 求直线交点时 我们可通过直线的一般方程 ax+by+c=0 求得(方程中的abc为系数,不是前面提到的端点,另外也可用点斜式方程和斜截式方程,此处暂且不论). 然后根据交点的与线段端点的位置关系来判断交点是否在线段上. 公式如下图:
实现代码如下 : Javascript代码 function segmentsIntr(a, b, c, d){ /** 1 解线性方程组, 求线段交点. **/ // 如果分母为0 则平行或共线, 不相交 var denominator = (b.y - a.y)*(d.x - c.x) - (a.x - b.x)*(c.y - d.y); if (denominator==0) { return false; } // 线段所在直线的交点坐标 (x , y) var x = ( (b.x - a.x) * (d.x - c.x) * (c.y - a.y) + (b.y - a.y) * (d.x - c.x) * a.x - (d.y - c.y) * (b.x - a.x) * c.x ) / denominator ; var y = -( (b.y - a.y) * (d.y - c.y) * (c.x - a.x) + (b.x - a.x) * (d.y - c.y) * a.y - (d.x - c.x) * (b.y - a.y) * c.y ) / denominator; /** 2 判断交点是否在两条线段上 **/ if ( // 交点在线段1上 (x - a.x) * (x - b.x) = 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引擎下). 我的测试用例里也是进行变态的百万次级别的线段相交测试 才能拉开三种算法之间的差距. 不过本着精益求精 以及学习的态度而言, 追求一个更好的算法, 总是有其积极意义的. 好了 不啰嗦了, 就到这里吧. 现学现卖的东西, 难免有错误, 还请大家不吝斧正. 先谢谢啦 文章来源:http://fins.iteye.com/blog/1522259 |
【本文地址】