两条直线的位置判断

给你两条直线，判断这两条直线是否共线，相交，不相交（即平行），相交的话输出交点。

 

判断平行，然后通过叉积判断是否共线。

 

平行判断可以判断两条直线的斜率是否相等。

 

交点的话，相当于联立方程组求解了。

 

这些方程看模板理解的，刚才搜了下，有人讲得比较清楚，借鉴下http://blog.csdn.net/dreamvyps/archive/2011/01/25/6162690.aspx

 

 

如何判断是否同线？由叉积的原理知道如果p1，p2，p3共线的话那么(p2-p1)X(p3-p1)=0。因此如果p1，p2，p3共线，p1，p2，p4共线，那么两条直线共线。direction（）求叉积，叉积为0说明共线。

 

如何判断是否平行？由向量可以判断出两直线是否平行。如果两直线平行，那么向量p1p2、p3p4也是平等的。即((p1.x-p2.x)*(p3.y-p4.y)-(p1.y-p2.y)*(p3.x-p4.x))==0说明向量平等。

 

如何求出交点？这里也用到叉积的原理。假设交点为p0(x0,y0)。则有：

 

(p1-p0)X(p2-p0)=0

 

(p3-p0)X(p4-p0)=0

 

展开后即是

 

(y1-y2)x0+(x2-x1)y0+x1y2-x2y1=0

 

(y3-y4)x0+(x4-x3)y0+x3y4-x4y3=0

 

将x0,y0作为变量求解二元一次方程组。

 

假设有二元一次方程组

 

a1x+b1y+c1=0;

 

a2x+b2y+c2=0

 

那么

 

x=(c1*b2-c2*b1)/(a2*b1-a1*b2);

 

y=(a2*c1-a1*c2)/(a1*b2-a2*b1);

 

因为此处两直线不会平行，所以分母不会为0。

 

[cpp] view plain copy print ?

1. #include <queue>  
2. #include <stack>  
3. #include <math.h>  
4. #include <stdio.h>  
5. #include <stdlib.h>  
6. #include <iostream>  
7. #include <limits.h>  
8. #include <string.h>  
9. #include <algorithm>  
10. using namespace std;  
11. const double eps = 1e-6;  
12. struct point{   double x,y; };  
13. struct line{    point a,b;      };   
14. bool dy(double x,double y)  {   return x > y + eps;} // x > y   
15. bool xy(double x,double y)  {   return x < y - eps;} // x < y   
16. bool dyd(double x,double y) {   return x > y - eps;} // x >= y   
17. bool xyd(double x,double y) {   return x < y + eps;}     // x <= y   
18. bool dd(double x,double y)  {   return fabs( x - y ) < eps;}  // x == y  
19. double crossProduct(point a,point b,point c)//向量 ac 在 ab 的方向   
20. {  
21.     return (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y);  
22. }  
23. bool parallel(line u,line v)  
24. {  
25.     return dd( (u.a.x - u.b.x)*(v.a.y - v.b.y) - (v.a.x - v.b.x)*(u.a.y - u.b.y), 0.0 );  
26. }  
27. point intersection(line u,line v)  
28. {  
29.     point ans = u.a;  
30.     double t = ((u.a.x - v.a.x)*(v.a.y - v.b.y) - (u.a.y - v.a.y)*(v.a.x - v.b.x))/  
31.                 ((u.a.x - u.b.x)*(v.a.y - v.b.y) - (u.a.y - u.b.y)*(v.a.x - v.b.x));  
32.     ans.x += (u.b.x - u.a.x)*t;  
33.     ans.y += (u.b.y - u.a.y)*t;  
34.     return ans;  
35. }  
36. int main()  
37. {  
38.     int n;  
39.     line u,v;  
40.     int flag = 0;  
41.     while( ~scanf("%d",&n) )  
42.     {  
43.         printf("INTERSECTING LINES OUTPUT/n");  
44.         while( n-- )  
45.         {  
46.             scanf("%lf %lf %lf %lf",&u.a.x,&u.a.y,&u.b.x,&u.b.y);  
47.             scanf("%lf %lf %lf %lf",&v.a.x,&v.a.y,&v.b.x,&v.b.y);  
48.             if( parallel(u,v) )  
49.                 if( dd(crossProduct(u.a,u.b,v.a),0.0) )  
50.                     printf("LINE/n");  
51.                 else  
52.                     printf("NONE/n");  
53.             else  
54.             {  
55.                 point ans = intersection(u,v);  
56.                 printf("POINT %.2lf %.2lf/n",ans.x,ans.y);  
57.             }  
58.         }  
59.         printf("END OF OUTPUT/n");  
60.     }  
61. return 0;  
62. }