判断两条线段是否相交（三种算法）

末蓝、 2022-08-23 12:56 436阅读 0赞

算法1：

**\[cpp\]**  [view plain][] [copy][view plain]

1.  ///----------alg 1------------  
2.  **struct** Point  
3.  \{   
4.      **double** x, y;  
5.  \};   
6.    
7.  **bool** between(**double** a, **double** X0, **double** X1)  
8.  \{  
9.      **double** temp1= a-X0;  
10.     **double** temp2= a-X1;  
11.     **if** ( ( temp1<1e-8 && temp2>-1e-8 ) || ( temp2<1e-6 && temp1>-1e-8 ) )  
12.     \{  
13.         **return** **true**;  
14.     \}  
15.     **else**  
16.     \{  
17.         **return** **false**;  
18.     \}  
19. \}  
20.   
21.   
22. // 判断两条直线段是否有交点，有则计算交点的坐标  
23. // p1,p2是直线一的端点坐标  
24. // p3,p4是直线二的端点坐标  
25. **bool** detectIntersect(Point p1, Point p2, Point p3, Point p4)  
26. \{  
27.     **double** line\_x,line\_y; //交点  
28.     **if** ( (fabs(p1.x-p2.x)<1e-6) && (fabs(p3.x-p4.x)<1e-6) )  
29.     \{  
30.         **return** **false**;  
31.     \}  
32.     **else** **if** ( (fabs(p1.x-p2.x)<1e-6) ) //如果直线段p1p2垂直与y轴  
33.     \{  
34.         **if** (between(p1.x,p3.x,p4.x))  
35.         \{  
36.             **double** k = (p4.y-p3.y)/(p4.x-p3.x);  
37.             line\_x = p1.x;  
38.             line\_y = k\*(line\_x-p3.x)+p3.y;  
39.   
40.             **if** (between(line\_y,p1.y,p2.y))  
41.             \{  
42.                 **return** **true**;  
43.             \}  
44.             **else**  
45.             \{  
46.                 **return** **false**;  
47.             \}  
48.         \}  
49.         **else**   
50.         \{  
51.             **return** **false**;  
52.         \}  
53.     \}  
54.     **else** **if** ( (fabs(p3.x-p4.x)<1e-6) ) //如果直线段p3p4垂直与y轴  
55.     \{  
56.         **if** (between(p3.x,p1.x,p2.x))  
57.         \{  
58.             **double** k = (p2.y-p1.y)/(p2.x-p1.x);  
59.             line\_x = p3.x;  
60.             line\_y = k\*(line\_x-p2.x)+p2.y;  
61.   
62.             **if** (between(line\_y,p3.y,p4.y))  
63.             \{  
64.                 **return** **true**;  
65.             \}  
66.             **else**  
67.             \{  
68.                 **return** **false**;  
69.             \}  
70.         \}  
71.         **else**   
72.         \{  
73.             **return** **false**;  
74.         \}  
75.     \}  
76.     **else**  
77.     \{  
78.         **double** k1 = (p2.y-p1.y)/(p2.x-p1.x);   
79.         **double** k2 = (p4.y-p3.y)/(p4.x-p3.x);  
80.   
81.         **if** (fabs(k1-k2)<1e-6)  
82.         \{  
83.             **return** **false**;  
84.         \}  
85.         **else**   
86.         \{  
87.             line\_x = ((p3.y - p1.y) - (k2\*p3.x - k1\*p1.x)) / (k1-k2);  
88.             line\_y = k1\*(line\_x-p1.x)+p1.y;  
89.         \}  
90.   
91.         **if** (between(line\_x,p1.x,p2.x)&&between(line\_x,p3.x,p4.x))  
92.         \{  
93.             **return** **true**;  
94.         \}  
95.         **else**   
96.         \{  
97.             **return** **false**;  
98.         \}  
99.     \}  
100. \}  
101. ///------------alg 1------------

算法2：

**\[cpp\]**  [view plain][] [copy][view plain]

1.  ///------------alg 2------------  
2.  //叉积  
3.  **double** mult(Point a, Point b, Point c)  
4.  \{  
5.      **return** (a.x-c.x)\*(b.y-c.y)-(b.x-c.x)\*(a.y-c.y);  
6.  \}  
7.    
8.  //aa, bb为一条线段两端点 cc, dd为另一条线段的两端点 相交返回true, 不相交返回false  
9.  **bool** intersect(Point aa, Point bb, Point cc, Point dd)  
10. \{  
11.     **if** ( max(aa.x, bb.x)<min(cc.x, dd.x) )  
12.     \{  
13.         **return** **false**;  
14.     \}  
15.     **if** ( max(aa.y, bb.y)<min(cc.y, dd.y) )  
16.     \{  
17.         **return** **false**;  
18.     \}  
19.     **if** ( max(cc.x, dd.x)<min(aa.x, bb.x) )  
20.     \{  
21.         **return** **false**;  
22.     \}  
23.     **if** ( max(cc.y, dd.y)<min(aa.y, bb.y) )  
24.     \{  
25.         **return** **false**;  
26.     \}  
27.     **if** ( mult(cc, bb, aa)\*mult(bb, dd, aa)<0 )  
28.     \{  
29.         **return** **false**;  
30.     \}  
31.     **if** ( mult(aa, dd, cc)\*mult(dd, bb, cc)<0 )  
32.     \{  
33.         **return** **false**;  
34.     \}  
35.     **return** **true**;  
36. \}  
37. ///------------alg 2------------

算法3：[http://dec3.jlu.edu.cn/webcourse/t000096/graphics/chapter5/01\_1][http_dec3.jlu.edu.cn_webcourse_t000096_graphics_chapter5_01_1].

html

**\[c-sharp\]**  [view plain][] [copy][view plain]

1.  ///------------alg 3------------  
2.  **double** determinant(**double** v1, **double** v2, **double** v3, **double** v4)  // 行列式  
3.  \{  
4.      **return** (v1\*v3-v2\*v4);  
5.  \}  
6.    
7.  **bool** intersect3(Point aa, Point bb, Point cc, Point dd)  
8.  \{  
9.      **double** delta = determinant(bb.x-aa.x, cc.x-dd.x, bb.y-aa.y, cc.y-dd.y);  
10.     **if** ( delta<=(1e-6) && delta>=-(1e-6) )  // delta=0，表示两线段重合或平行  
11.     \{  
12.         **return** **false**;  
13.     \}  
14.     **double** namenda = determinant(cc.x-aa.x, cc.x-dd.x, cc.y-aa.y, cc.y-dd.y) / delta;  
15.     **if** ( namenda>1 || namenda<0 )  
16.     \{  
17.         **return** **false**;  
18.     \}  
19.     **double** miu = determinant(bb.x-aa.x, cc.x-aa.x, bb.y-aa.y, cc.y-aa.y) / delta;  
20.     **if** ( miu>1 || miu<0 )  
21.     \{  
22.         **return** **false**;  
23.     \}  
24.     **return** **true**;  
25. \}  
26. ///------------alg 3------------

main函数测试：

**\[cpp\]**  [view plain][] [copy][view plain]

1.  **int** main()  
2.  \{  
3.      Point p1, p2, p3, p4;  
4.      p1.x = 1;  
5.      p1.y = 4;  
6.      p2.x = 3;  
7.      p2.y = 0;  
8.      p3.x = 0;  
9.      p3.y = 1;  
10.     p4.x = 4;  
11.     p4.y = 3;  
12.   
13.   
14.     **int** i=0, j=0;  
15.     **bool** flag = **false**;  
16.     flag = intersect3(p1, p2, p3, p4);  
17.   
18.     // alg 2  
19.     **time\_t** seconds1 = time (NULL);  
20.     **for** ( ; i!=20000; ++i )  
21.     \{  
22.         **for** ( j=0; j!=60000; ++j )  
23.         \{  
24.             flag = detectIntersect(p1, p2, p3, p4);  
25.         \}  
26.     \}  
27.     **time\_t** seconds2 = time (NULL);  
28.   
29.     cout << "Time used in alg 1:" << seconds2-seconds1 << " seconds." << endl;  
30.   
31.     // alg 2  
32.     **time\_t** seconds3 = time (NULL);  
33.     i=0;  
34.     j=0;  
35.     **for** ( ; i!=20000; ++i )  
36.     \{  
37.         **for** ( j=0; j!=60000; ++j )  
38.         \{  
39.             flag = intersect(p1, p2, p3, p4);  
40.         \}  
41.     \}  
42.     **time\_t** seconds4 = time (NULL);  
43.     cout << "Time used in alg 2:" << seconds4-seconds3 << " seconds." << endl;  
44.   
45.     // alg 3  
46.     **time\_t** seconds5 = time (NULL);  
47.     i=0;  
48.     j=0;  
49.     **for** ( ; i!=20000; ++i )  
50.     \{  
51.         **for** ( j=0; j!=60000; ++j )  
52.         \{  
53.             flag = intersect3(p1, p2, p3, p4);  
54.         \}  
55.     \}  
56.     **time\_t** seconds6 = time (NULL);  
57.     cout << "Time used in alg 3:" << seconds6-seconds5 << " seconds." << endl;  
58.     **return** 0;  
59. \}

VS2008编译器环境下测试结果：

Debug模式下：

alg 1: 315 seconds;

alg 2: 832 seconds;

alg 3: 195 seconds;

Release模式下：

alg 1: 157 seconds;

alg 2: 169 seconds;

alg 3: 122 seconds;

结论： 使用算法3，时间复杂度最低。

[view plain]: http://blog.csdn.net/rickliuxiao/article/details/6259322#
[http_dec3.jlu.edu.cn_webcourse_t000096_graphics_chapter5_01_1]: http://dec3.jlu.edu.cn/webcourse/t000096/graphics/chapter5/01_1