资源描述：
《几何常用算法与判断线段相交》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、下面这个函数在我写的计算几何库函数里面有，那个库可以在http://algorithm.126.com/的资源中心 - 代码角 找到。 算法简单说明： 首先判断以两条线段为对角线的矩形是否相交，如果不相交两条线段肯定也不相交。（所谓以a1b2为对角钱的矩形就是以两边长为
2、a1.x–b2.x
3、和
4、a1.y–b2.y
5、以及a1b2为对角线的矩形）。如果相交的话，利用矢量叉乘判断两条线段是否相互跨越，如果相互跨越显然就相交，反之则不相交。算法不难，但是一些特殊情况需要考虑到，比如两条相段共线且在断点处相交。下面的代码经过测试了，应该没有bug，如果你真的发现了bug请告诉我：）
6、/******************************************************** ** *返回(P1-P0)*(P2-P0)的叉积。* *若结果为正，则在的顺时针方向；* *若为0则共线；* *若为负则在的在逆时针方向;* *可以根据这个函数确定两条线段在交点处的转向,* *比如确定p0p1和p1p2在p1处是左转还是右转，只要 * * 求(p2-p0)*(p1-p0)，若<0则左转，>0则右转，=0则 * * 共
7、线 * ** ********************************************************/ float multiply(TPoint p1,TPoint p2,TPoint p0) { return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y)); } //确定两条线段是否相交 int intersect(TLineSeg u,TLineSeg v) { return( (max
8、(u.a.x,u.b.x)>=min(v.a.x,v.b.x))&& (max(v.a.x,v.b.x)>=min(u.a.x,u.b.x))&& (max(u.a.y,u.b.y)>=min(v.a.y,v.b.y))&& (max(v.a.y,v.b.y)>=min(u.a.y,u.b.y))&& （以两线段为对角线的矩形是否相交） (multiply(v.a,u.b,u.a)*multiply(u.b,v.b,u.a)>=0)&& (multiply(u.a,v.b,v.a)*multiply(
9、v.b,u.b,v.a)>=0));（是否相互跨立） } 忘记了说明TPoint和TLineSeg的定义了：） struct TPoint { float x,y; }; struct TLineSeg { TPoint a,b; }; 上面的算法避免了除法运算，所以不会出现计算误差NOwcan兄的方法虽然简单，但是求两条直线的交点需要用到除法，当两条线段相交但是很接近平行的时候，会有精度上的误差，所以我的方法不用除法更好一点。这是计算几何中的经典算法计算几何常用算法(一共23个) 1. 矢量减法 设二维矢量 P = （x1,y1） ，Q = (x2,y2)
10、 则矢量减法定义为： P - Q = ( x1 - x2 , y1 - y2 ) 显然有性质 P - Q = - ( Q - P ) 如不加说明，下面所有的点都看作矢量，两点的减法就是矢量相减； 2.矢量叉积 设矢量P = （x1,y1） ，Q = (x2,y2) 则矢量叉积定义为： P × Q = x1*y2 - x2*y1 得到的是一个标量 显然有性质 P × Q = - ( Q × P ) P × ( - Q ) = - ( P × Q ) 如不加说明，下面所有的点都看作矢量，点的乘法看作矢量叉积； 叉乘的重要性质： > 若 P × Q
11、> 0 , 则P 在Q的顺时针方向 > 若 P × Q < 0 , 则P 在Q的逆时针方向 > 若 P × Q = 0 , 则P 与Q共线，但可能同向也可能反向 3.判断点在线段上 设点为Q，线段为P1P2 ，判断点Q在该线段上的依据是： ( Q - P1 ) × ( P2 - P1 ) = 0 =>共线 且 Q 在以 P1，P2为对角顶点的矩形内 4.判断两线段是否相交 我们分两步确定两
