如何判断一个点是否在多边形内

  1 #include <iostream>
  2 #include <string>
  3 #include <cmath>
  4 
  5 #define PI 3.1415926
  6 #define EXP 1e-6   // 精度
  7 
  8 
  9 
 10 int main() {
 11     /* start_point表示判断点，point_all代表多边形点的二维数组 */
 12     double start_point[] = { 0.0, 0.0 };
 13 
 14     double point_all[5][2] = {
 15         { 0.0, -1.0 },
 16         { -2.0, 1.0 },
 17         { 2.0, 2.0 },
 18         { 1.0, 1.0},
 19         { 1.0, 0.0 }       
 20     };
 21 
 22     const int n = 5;// +1;
 23     const int double_n = 2 * n;
 24     double All_point_xy[double_n + 2] = {};
 25 
 26     for (int i = 0; i < n; i++) {
 27         for (int j = 0; j < 2; j++) {
 28             All_point_xy[2 * i + j] = { point_all[i][j] };    // 想将接收的多边形点放到一个一维数组中
 29         }
 30     }
 31 
 32     All_point_xy[double_n] = All_point_xy[0];
 33     All_point_xy[double_n + 1] = All_point_xy[1];            // 为方便多边形边界判断，再次将开头点放到末尾
 34 
 35     printf("点元素集合（末尾重复开头）：\n");                // 验证 
 36     for (int i = 0; i < double_n + 2; i++) {
 37         printf("%f , ", All_point_xy[i]);
 38     }
 39 
 40 
 41     int counter = 0;
 42     double point_x;                     // 交点x坐标
 43     double point_y;                     // 交点y坐标
 44     double theta = 45;
 45     double theta_arr[11] = { 45, 60, 256, 128, 64, 32, 16, 8, 4, 2, 1 };    // 不同角度的射线方向 ，选择45，60进行验证，使用的时候可以直接使用{256， 128，64， 32， 16， 8， 4， 2， 1}
 46     double t, b;
 47     double Deg2rad = 180 / PI;                                              // C++ 中三角函数计算，运用的是弧度
 48     double tan_theta = tan(theta / Deg2rad);                                // 转换至弧度，进行正切值计算
 49     printf("\n验证正切值：%lf", tan_theta);                                 // 验证转换关系，以及求解是否正确
 50     
 51     bool Coincidence_judgment = false;                                      // 重合判段标识
 52     bool Coincidence_judgment02 = false;                                    // 为更好地跳出循环，进行了两次重合判断
 53     for (int i = 0; i < (std::end(theta_arr) - std::begin(theta_arr)); i++) { // 获得数组的长度方法
 54         int now_theta = theta_arr[i];
 55 
 56         for (int j = 0; j <= (n - 1); j++) {
 57             double point_start_x = All_point_xy[2 * j];
 58             double point_start_y = All_point_xy[2 * j + 1];
 59             double point_end_x = All_point_xy[2 * j + 2];
 60             double point_end_y = All_point_xy[2 * j + 3];
 61             double slope_half_line = tan( theta_arr[i] / Deg2rad );            // 射线斜率
 62             double slope_line_segment = (point_end_y - point_start_y) / (point_end_x - point_start_x);  // 两点形成直线的斜率
 63             double err_0 = abs(slope_half_line - slope_line_segment);          // 由于无法绝对相等，设计了精度差
 64         
 65             printf("\n%d", j);
 66             if ( err_0 < EXP ) {            // 斜率相等，表示射线与边界平行或重合，再次求解两点与判断点之间的斜率，如果两个相等，则表示重合
 67                 double slope2start = (point_start_y - start_point[1]) / (point_start_x - start_point[0]);   
 68                 double slope2end = (point_end_y - start_point[1]) / (point_end_x - start_point[0]);
 69                 double err_1 = abs(slope2end - slope2start);
 70                 if ( err_1 < EXP )  {
 71                     Coincidence_judgment = true;        // 重合
 72                     Coincidence_judgment02 = true;
 73                 }
 74             }
 75             if ( Coincidence_judgment == true ) {
 76                 Coincidence_judgment = false;
 77                 break;                                  // 重合则表示该斜率不可用，跳出整个循环
 78             }
 79             // 如果不重合，则利用两个直线求交点的公式求解交点坐标
 80             b = start_point[1] - slope_half_line * start_point[0];
 81             t = (slope_half_line * point_start_x + b - point_start_y) / (point_end_y - point_start_y - slope_half_line * (point_end_x - point_start_x));
 82             point_x = (point_end_x - point_start_x) * t + point_start_x;
 83             point_y = (point_end_y - point_start_y) * t + point_start_y;
 84 
 85             printf("\n%d", now_theta);
 86             printf("\n求解交点坐标：%lf, %lf ", point_x, point_y);
 87 
 88             // 判断交点是否在两点形成的线段上，如果不在，就跳过不需计数
 89             if ((point_x > point_start_x) && (point_x > point_end_x)) {
 90                 printf("x坐标上限均大于两端点，故舍弃并跳出\n ");
 91                 continue;
 92             }
 93             else if ((point_x < point_start_x) && (point_x < point_end_x)) {
 94                 printf("x坐标上限均小于两端点，故舍弃并跳出\n ");
 95                 continue;
 96             }
 97             else if ((point_y > point_start_y) && (point_y > point_end_y)) {
 98                 printf("y坐标上限均大于两端点，故舍弃并跳出\n ");
 99                 continue;
100             }
101             else if ((point_y < point_start_y) && (point_y < point_end_y)) {
102                 printf("y坐标上限均小于两端点，故舍弃并跳出\n ");
103                 continue;
104             }
105             else {
106                 printf("正常值，触发 counter++;\n ");
107 
108                 if (start_point[0] > point_x) {                 // 由于上面求解交点坐标方式是以直线形式进行的，将其转换至一个方向表示射线形式
109                     counter++;
110                 }
111  
112             }
113            
114         }
115         if (Coincidence_judgment02 == true) {
116             Coincidence_judgment02 = false;
117             counter = 0;
118             continue;
119         }
120         else {
121             break;
122         }
123         
124     }
125  
126     printf("\n交点个数 = %d", counter);
127 
128     if (counter % 2 == 1) {
129         printf("\n点在多边形的内部");
130     }
131     else {
132         printf("\n点在多边形的外部");
133     }
134     return 0;
135 }