判断平面上两条直线是否相交

 

判断平面上两条直线是否相交

分类： 数据结构与算法设计2013-09-17 09:07 117人阅读 评论(0) 收藏 举报 直线相交

首先引出计算几何学中一个最基本的问题：如何判断向量在的顺时针方向还是逆时针方向？

把p0定为原点，p1的坐标是(x1,y1)，p2的坐标是(x2,y2)。向量的叉积(cross product)实际上就是矩阵的行列式：

当叉积为正时，说明在的顺时针方向上；叉积为0说明两向量共线（同向或反向）。

当同时满足：

（1）和在的两侧（即一个顺时针方向上，一个在逆时针方向上）

（2）和在的两侧

时可肯定和相交。

　　　　　　　　　　　　图1

图1是线段相交的一般情形。

图2只满足第（1）条，不满足第（2）条所以不能证明和相交。

　　　　　　　　　　　　图2

图3和图4是一种特殊情况，它不满足第（2）条，因为和重合,即和的叉积为0。

可见当叉积为0时要分情况讨论，当p3在线段p₁p₂上时两线段相交；当p3在线段p₁p₂的延长线上时两线段不相交。

[cpp] view plaincopy

1. double direction(pair<double,double> p1,pair<double,double> p2,pair<double,double> p3){  
2.     pair<double,double> d1=make_pair(p3.first-p1.first,p3.second-p1.second);  
3.     pair<double,double> d2=make_pair(p2.first-p1.first,p2.second-p1.second);  
4.     return d1.first*d2.second-d1.second*d2.first;  
5. }  

direction函数用于计算和的叉积。

[cpp] view plaincopy

1. bool OnSegment(pair<double,double> p1,pair<double,double> p2,pair<double,double> p3){  
2.     double x_min,x_max,y_min,y_max;  
3.     if(p1.first<p2.first){  
4.         x_min=p1.first;  
5.         x_max=p2.first;  
6.     }else{  
7.         x_min=p2.first;  
8.         x_max=p1.first;  
9.     }  
10.     if(p1.second<p2.second){  
11.         y_min=p1.second;  
12.         y_max=p2.second;  
13.     }else{  
14.         y_min=p2.second;  
15.         y_max=p1.second;  
16.     }  
17.     if(p3.first<x_min || p3.first>x_max || p3.second<y_min || p3.second>y_max)  
18.         return false;  
19.     else  
20.         return true;  
21. }  

当p3在直线p₁p₂上时，OnSegment函数用于确认p3在上，还是在的延长线上。

下面是用于判断两线段是否相交的主函数。

[cpp] view plaincopy

1. bool SegmentIntersect(pair<double,double> p1,pair<double,double> p2,pair<double,double> p3,pair<double,double> p4){  
2.     double d1=direction(p3,p4,p1);  
3.     double d2=direction(p3,p4,p2);  
4.     double d3=direction(p1,p2,p3);  
5.     double d4=direction(p1,p2,p4);  
6.   
7.     if(d1*d2<0 && d3*d4<0)  
8.         return true;  
9.     else if(d1==0 && OnSegment(p3,p4,p1))  
10.         return true;  
11.     else if(d2==0 && OnSegment(p3,p4,p2))  
12.         return true;  
13.     else if(d3==0 && OnSegment(p1,p2,p3))  
14.         return true;  
15.     else if(d4==0 && OnSegment(p1,p2,p4))  
16.         return true;  
17.     else  
18.         return false;  
19. }  

测试函数：

[cpp] view plaincopy

1. int main(){  
2.     double x1,y1,x2,y2,x3,y3,x4,y4;  
3.     cout<<"Please input x1,y1,x2,y2,x3,y3,x4,y4 by order"<<endl;  
4.     cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;  
5.     pair<double,double> p1=make_pair(x1,y1);  
6.     pair<double,double> p2=make_pair(x2,y2);  
7.     pair<double,double> p3=make_pair(x3,y3);  
8.     pair<double,double> p4=make_pair(x4,y4);  
9.     if(SegmentIntersect(p1,p2,p3,p4))  
10.         cout<<"YES"<<endl;  
11.     else  
12.         cout<<"NO"<<endl;  
13.     return 0;  
14. }