判断两线段是否相交

判断两线段是否相交

下面的方法是标准算法
：
　　我们分两步确定两条线段是否相交：
　　(1)快速排斥试验
　　　　设以线段 P1P2 为对角线的矩形为R, 设以线段 Q1Q2 为对角线的矩形为T,如果R和T不相交,显然两线段不会相交.
　　(2)跨立试验 　　　　如果两线段相交,则两线段必然相互跨立对方.若P1P2跨立Q1Q2 ,则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧,即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0.上式可改写成( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) 0.当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时,说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线,但是因为已经通过快速排斥试验,所以 P1 一定在线段 Q1Q2上；同理,( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上.所以判断P1P2跨立Q1Q2的依据是：( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) = 0.同理判断Q1Q2跨立P1P2的依据是：( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) = 0.
在相同的原理下,对此算法的具体的实现细节可能会与此有所不同,除了这种过程外,大家也可以参考《算法导论》上的实现.
class POINT{public:double x,y;};
class LINESEG{public:POINT s,e;}l[2000];
double max(double a,double b){return ab?a:b;}double min(double a,double b){return a<b?a:b;}double multiply(POINT sp,POINT ep,POINT op){return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y));}bool online(LINESEG l,POINT p){return( (multiply(l.e,p,l.s)==0) &&( ( (p.x-l.s.x)*(p.x-l.e.x)<=0 )&&( (p.y-l.s.y)*(p.y-l.e.y)<=0 ) ) );}/*如果线段u和v相交(包括相交在端点处)时,返回true */bool intersect(LINESEG u,LINESEG v){return( (max(u.s.x,u.e.x)=min(v.s.x,v.e.x))&& //排斥实验
(max(v.s.x,v.e.x)=min(u.s.x,u.e.x))&&
(max(u.s.y,u.e.y)=min(v.s.y,v.e.y))&&
(max(v.s.y,v.e.y)=min(u.s.y,u.e.y))&&
(multiply(v.s,u.e,u.s)*multiply(u.e,v.e,u.s)=0)&& //跨立实验
(multiply(u.s,v.e,v.s)*multiply(v.e,u.e,v.s)=0));}上面的算法在两线段共线时会有问题,这时第二步时两个叉积都为0
,这时就可以用这四个点的不相等的坐标分量来判断两线段是否有重合部分就行了.如果X、Y坐标分量都相等,那就是一个点了
此外在用叉积作判断时认为一个线段的端点点在另一个线段上或两线线段有公共端点时两线段有交点.