计算几何-求线段交点算法和代码（C++语言）

admin

1. //跨立判断
2. bool isLineSegmentCross(const Point &P1,const Point &P2,const Point &Q1,const Point &Q2)
3. {
4.     if(
5.         ((Q1.x-P1.x)*(Q1.y-Q2.y)-(Q1.y-P1.y)*( Q1.x-Q2.x)) * ((Q1.x-P2.x)*(Q1.y-Q2.y)-(Q1.y-P2.y)*(Q1.x-Q2.x)) < 0 &&
6.         ((P1.x-Q1.x)*(P1.y-P2.y)-(P1.y-Q1.y)*(P1.x-P2.x)) * ((P1.x-Q2.x)*(P1.y-P2.y)-(P1.y-Q2.y)*( P1.x-P2.x)) < 0
7.     )
8.         return true;
9.     else
10.        return false;
11. }

复制代码

1. #include<stdio.h>
2. #define N 10002
4. /**
5. 算法适用于整形点，不适用于浮点型
6. **/
8. typedef struct Point
9. {
10.     int x;
11.     int y;
12. }Point;
14. double min(int x, int y)
15. {
16.     return x<y?x:y;
17. }
19. double max(int x, int y)
20. {
21.     return x>y?x:y;
22. }
24. //排斥实验
25. bool IsRectCross(const Point &p1,const Point &p2,const Point &q1,const Point &q2)
26. {
27.     bool ret = min(p1.x,p2.x) <= max(q1.x,q2.x)    &&
28.                 min(q1.x,q2.x) <= max(p1.x,p2.x) &&
29.                 min(p1.y,p2.y) <= max(q1.y,q2.y) &&
30.                 min(q1.y,q2.y) <= max(p1.y,p2.y);
31.     return ret;
32. }
34. /**这段代码不能得到正确答案，故注释
35. //跨立判断
36. bool IsLineSegmentCross(const Point &pFirst1,const Point &pFirst2,const Point &pSecond1,const Point &pSecond2)
37. {
38.     long line1,line2;
39.     line1 = pFirst1.x * (pSecond1.y - pFirst2.y) +
40.         pFirst2.x * (pFirst1.y - pSecond1.y) +
41.         pSecond1.x * (pFirst2.y - pFirst1.y);
42.     line2 = pFirst1.x * (pSecond2.y - pFirst2.y) +
43.         pFirst2.x * (pFirst1.y - pSecond2.y) +
44.         pSecond2.x * (pFirst2.y - pFirst1.y);
45.     if (((line1 ^ line2) >= 0) && !(line1 == 0 && line2 == 0))
46.         return false;
48.     line1 = pSecond1.x * (pFirst1.y - pSecond2.y) +
49.         pSecond2.x * (pSecond1.y - pFirst1.y) +
50.         pFirst1.x * (pSecond2.y - pSecond1.y);
51.     line2 = pSecond1.x * (pFirst2.y - pSecond2.y) +
52.         pSecond2.x * (pSecond1.y - pFirst2.y) +
53.         pFirst2.x * (pSecond2.y - pSecond1.y);
54.     if (((line1 ^ line2) >= 0) && !(line1 == 0 && line2 == 0))
55.         return false;
56.     return true;
57. }
58. **/
60. //跨立判断
61. bool IsLineSegmentCross(const Point &P1,const Point &P2,const Point &Q1,const Point &Q2)
62. {
63.     if(
64.         ((Q1.x-P1.x)*(Q1.y-Q2.y)-(Q1.y-P1.y)*( Q1.x-Q2.x)) * ((Q1.x-P2.x)*(Q1.y-Q2.y)-(Q1.y-P2.y)*(Q1.x-Q2.x)) < 0 ||
65.         ((P1.x-Q1.x)*(P1.y-P2.y)-(P1.y-Q1.y)*(P1.x-P2.x)) * ((P1.x-Q2.x)*(P1.y-P2.y)-(P1.y-Q2.y)*( P1.x-P2.x)) < 0
66.     )
67.         return true;
68.     else
69.        return false;
70. }
72. /**
73. 求线段P1P2与Q1Q2的交点。
74. 先进行快速排斥实验和跨立实验确定有交点再进行计算。
75. 交点（x,y）使用引用返回。
76. 没有验证过
77. **/
78. bool GetCrossPoint(const Point &p1,const Point &p2,const Point &q1,const Point &q2,long &x,long &y)
79. {
80.     if(IsRectCross(p1,p2,q1,q2))
81.     {
82.         if (IsLineSegmentCross(p1,p2,q1,q2))
83.         {
84.             //求交点
85.             long tmpLeft,tmpRight;
86.             tmpLeft = (q2.x - q1.x) * (p1.y - p2.y) - (p2.x - p1.x) * (q1.y - q2.y);
87.             tmpRight = (p1.y - q1.y) * (p2.x - p1.x) * (q2.x - q1.x) + q1.x * (q2.y - q1.y) * (p2.x - p1.x) - p1.x * (p2.y - p1.y) * (q2.x - q1.x);
89.             x = (int)((double)tmpRight/(double)tmpLeft);
91.             tmpLeft = (p1.x - p2.x) * (q2.y - q1.y) - (p2.y - p1.y) * (q1.x - q2.x);
92.             tmpRight = p2.y * (p1.x - p2.x) * (q2.y - q1.y) + (q2.x- p2.x) * (q2.y - q1.y) * (p1.y - p2.y) - q2.y * (q1.x - q2.x) * (p2.y - p1.y);
93.             y = (int)((double)tmpRight/(double)tmpLeft);
94.             return true;
95.         }
96.     }
97.     return false;
98. }

复制代码

2. #include <stdio.h>
3. #include <math.h>
4. const int N = 100010;
5. int mark[N];
6. struct Point
7. {
8.     double x,y;
9. };
10. struct stline
11. {
12.     Point a,b;
13. } line1,line2, p[N];
15. int dblcmp(double a,double b)
16. {
17.     if (fabs(a-b)<=1E-6) return 0;
18.     if (a>b) return 1;
19.     else return -1;
20. }
21. //***************点积判点是否在线段上***************
22. double dot(double x1,double y1,double x2,double y2) //点积
23. {
24.     return x1*x2+y1*y2;
25. }
27. int point采用on采用line(Point a,Point b,Point c) //求a点是不是在线段bc上，>0不在，=0与端点重合，<0在。
28. {
29.     return dblcmp(dot(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y),0);
30. }
31. //**************************************************
32. double cross(double x1,double y1,double x2,double y2)
33. {
34.     return x1*y2-x2*y1;
35. }
36. double ab采用cross采用ac(Point a,Point b,Point c) //ab与ac的叉积
37. {
38.     return cross(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);
39. }
40. int ab采用cross采用cd (Point a,Point b,Point c,Point d) //求ab是否与cd相交，交点为p。1规范相交，0交点是一线段的端点，-1不相交。
41. {
42.     double s1,s2,s3,s4;
43.     int d1,d2,d3,d4;
44.     Point p;
45.     d1=dblcmp(s1=ab采用cross采用ac(a,b,c),0);
46.     d2=dblcmp(s2=ab采用cross采用ac(a,b,d),0);
47.     d3=dblcmp(s3=ab采用cross采用ac(c,d,a),0);
48.     d4=dblcmp(s4=ab采用cross采用ac(c,d,b),0);
50. //如果规范相交则求交点
51.     if ((d1^d2)==-2 && (d3^d4)==-2)
52.     {
53.         p.x=(c.x*s2-d.x*s1)/(s2-s1);
54.         p.y=(c.y*s2-d.y*s1)/(s2-s1);
55.         return 1;
56.     }
58. //如果不规范相交
59.     if (d1==0 && point采用on采用line(c,a,b)<=0)
60.     {
61.         p=c;
62.         return 0;
63.     }
64.     if (d2==0 && point采用on采用line(d,a,b)<=0)
65.     {
66.         p=d;
67.         return 0;
68.     }
69.     if (d3==0 && point采用on采用line(a,c,d)<=0)
70.     {
71.         p=a;
72.         return 0;
73.     }
74.     if (d4==0 && point采用on采用line(b,c,d)<=0)
75.     {
76.         p=b;
77.         return 0;
78.     }
79. //如果不相交
80.     return -1;
81. }

复制代码

admin

1. Point getCrossPoint(Segment s1, Segment s2) {
2.     Vector base = s2.p2 - s2.p1;
3.     double d1 = abs(cross(base, s1.p1 - s2.p1));
4.     double d2 = abs(cross(base, s1.p2 - s2.p1));
5.     double t = d1 / (d1 + d2);
6.     return s1.p1 + (s1.p2 - s1.p1) * t;
7. }

复制代码

admin

1. #include<stdio.h>
2. #include<iostream>
3. #include<cmath>
4. using namespace std;
6. #define EPS (1e-10)
7. #define equals(a, b) (fabs((a) - (b)) < EPS)
9. class Point {//Point类，点
10.     public:
11.         double x, y;
12.         
13.         Point(double x = 0, double y = 0): x(x), y(y) {}
15.         Point operator + (Point p) { return Point(x + p.x, y + p.y); }
16.         Point operator - (Point p) { return Point(x - p.x, y - p.y); }
17.         Point operator * (double a) { return Point(a * x, a * y); }
18.         Point operator / (double a) { return Point(x / a, y / a); }
20.         double abs() { return sqrt(norm()); }
21.         double norm() { return x * x + y * y; }
22.         
23.         bool operator < (const Point &p) const {
24.             return x != p.x ? x < p.x : y < p.y;
25.         }
27.         bool operator == (const Point &p) const {
28.             return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
29.         }
30. };
32. typedef Point Vector;//Vector类，向量
34. struct Segment{//Segment 线段
35.     Point p1, p2;
36. };
37. double dot(Vector a, Vector b) {//内积
38.     return a.x * b.x + a.y * b.y;
39. }
41. double cross(Vector a, Vector b) {//外积
42.     return a.x*b.y - a.y*b.x;
43. }
45. Point getCrossPoint(Segment s1, Segment s2) {
46.     Vector base = s2.p2 - s2.p1;
47.     double d1 = abs(cross(base, s1.p1 - s2.p1));
48.     double d2 = abs(cross(base, s1.p2 - s2.p1));
49.     double t = d1 / (d1 + d2);
50.     return s1.p1 + (s1.p2 - s1.p1) * t;
51. }
53. int main(){
54.     int q;
55.     cin>>q;
56.    
57.     Segment s1, s2;
58.     Point p;
59.    
60.     while(q--){
61.         cin>>s1.p1.x>>s1.p1.y>>s1.p2.x>>s1.p2.y>>s2.p1.x>>s2.p1.y>>s2.p2.x>>s2.p2.y;
62.         p = getCrossPoint(s1, s2);
63.         printf("%.10f %.10f\n", p.x, p.y);
64.     }
65. }

复制代码