判断点在多边形内算法的C++实现

admin

1. #include<iostream>
2. #include <cmath>
3. #include <vector>
4. #include <algorithm>
6. #define EPSILON 0.000001
8. using namespace std;
10. //二维double矢量
11. struct  Vec2d
12. {
13.         double x, y;
15.         Vec2d()
16.         {
17.                 x = 0.0;
18.                 y = 0.0;
19.         }
20.         Vec2d(double dx, double dy)
21.         {
22.                 x = dx;
23.                 y = dy;
24.         }
25.         void Set(double dx, double dy)
26.         {
27.                 x = dx;
28.                 y = dy;
29.         }
30. };
32. //判断点在线段上
33. bool IsPointOnLine(double px0, double py0, double px1, double py1, double px2, double py2)
34. {
35.         bool flag = false;
36.         double d1 = (px1 - px0) * (py2 - py0) - (px2 - px0) * (py1 - py0);
37.         if ((abs(d1) < EPSILON) && ((px0 - px1) * (px0 - px2) <= 0) && ((py0 - py1) * (py0 - py2) <= 0))
38.         {
39.                 flag = true;
40.         }
41.         return flag;
42. }
44. //判断两线段相交
45. bool IsIntersect(double px1, double py1, double px2, double py2, double px3, double py3, double px4, double py4)
46. {
47.         bool flag = false;
48.         double d = (px2 - px1) * (py4 - py3) - (py2 - py1) * (px4 - px3);
49.         if (d != 0)
50.         {
51.                 double r = ((py1 - py3) * (px4 - px3) - (px1 - px3) * (py4 - py3)) / d;
52.                 double s = ((py1 - py3) * (px2 - px1) - (px1 - px3) * (py2 - py1)) / d;
53.                 if ((r >= 0) && (r <= 1) && (s >= 0) && (s <= 1))
54.                 {
55.                         flag = true;
56.                 }
57.         }
58.         return flag;
59. }
61. //判断点在多边形内
62. bool Point采用In采用Polygon采用2D(double x, double y, const vector<Vec2d> &POL)
63. {       
64.         bool isInside = false;
65.         int count = 0;
66.        
67.         //
68.         double minX = DBL采用MAX;
69.         for (int i = 0; i < POL.size(); i++)
70.         {
71.                 minX = std::min(minX, POL[i].x);
72.         }
74.         //
75.         double px = x;
76.         double py = y;
77.         double linePoint1x = x;
78.         double linePoint1y = y;
79.         double linePoint2x = minX -10;                        //取最小的X值还小的值作为射线的终点
80.         double linePoint2y = y;
82.         //遍历每一条边
83.         for (int i = 0; i < POL.size() - 1; i++)
84.         {       
85.                 double cx1 = POL[i].x;
86.                 double cy1 = POL[i].y;
87.                 double cx2 = POL[i + 1].x;
88.                 double cy2 = POL[i + 1].y;
89.                                
90.                 if (IsPointOnLine(px, py, cx1, cy1, cx2, cy2))
91.                 {
92.                         return true;
93.                 }
95.                 if (fabs(cy2 - cy1) < EPSILON)   //平行则不相交
96.                 {
97.                         continue;
98.                 }
100.                 if (IsPointOnLine(cx1, cy1, linePoint1x, linePoint1y, linePoint2x, linePoint2y))
101.                 {
102.                         if (cy1 > cy2)                        //只保证上端点+1
103.                         {
104.                                 count++;
105.                         }
106.                 }
107.                 else if (IsPointOnLine(cx2, cy2, linePoint1x, linePoint1y, linePoint2x, linePoint2y))
108.                 {
109.                         if (cy2 > cy1)                        //只保证上端点+1
110.                         {
111.                                 count++;
112.                         }
113.                 }
114.                 else if (IsIntersect(cx1, cy1, cx2, cy2, linePoint1x, linePoint1y, linePoint2x, linePoint2y))   //已经排除平行的情况
115.                 {
116.                         count++;
117.                 }
118.         }
119.        
120.         if (count % 2 == 1)
121.         {
122.                 isInside = true;
123.         }
125.         return isInside;
126. }
129. int main()
130. {       
131.         //定义一个多边形（六边形）
132.         vector<Vec2d> POL;       
133.         POL.push采用back(Vec2d(268.28, 784.75));
134.         POL.push采用back(Vec2d(153.98, 600.60));
135.         POL.push采用back(Vec2d(274.63, 336.02));
136.         POL.push采用back(Vec2d(623.88, 401.64));
137.         POL.push采用back(Vec2d(676.80, 634.47));
138.         POL.push采用back(Vec2d(530.75, 822.85));
139.         POL.push采用back(Vec2d(268.28, 784.75));                                //将起始点放入尾部，方便遍历每一条边
140.                
141.         //
142.         if (Point采用In采用Polygon采用2D(407.98, 579.43, POL))
143.         {
144.                 cout << "点（407.98, 579.43）在多边形内" << endl;
145.         }
146.         else
147.         {
148.                 cout << "点（407.98, 579.43）在多边形外" << endl;
149.         }
151.         //
152.         if (Point采用In采用Polygon采用2D(678.92, 482.07, POL))
153.         {
154.                 cout << "点（678.92, 482.07）在多边形内" << endl;
155.         }
156.         else
157.         {
158.                 cout << "点（678.92, 482.07）在多边形外" << endl;
159.         }
161.         return 0;
162. }

复制代码