1、概述
判断一个点是否在多边形内有几种不同的思路，相应的方法有很多：
- 射线法：从判断点向某个统一方向作射线，依交点个数的奇偶判断；
- 转角法：按照多边形顶点逆时针顺序，根据顶点和判断点连线的方向正负（设定角度逆时针为正）求和判断；
- 夹角和法：求判断点与所有边的夹角和，等于360度则在多边形内部。
- 面积和法：求判断点与多边形边组成的三角形面积和，等于多边形面积则点在多边形内部
因此，本文是通过射线法来进行判断点是否在多边形内的，主要用于无人机判断有没有进入准飞行区和禁飞区。 2、射线法的实现
射线法就是以判断点开始，向右（或向左）的水平方向作一射线，计算该射线与多边形每条边的交点个数，如果交点个数为奇数，则点位于多边形内，偶数则在多边形外。
网上大部分的射线法都是以向右或者向左作一射线的方法，但是都存在一个没有考虑的情况（类似下图，如何判断点所作的射线与多边形一条边界重合了，该怎么判断）：
为此，在使用C++编写代码时，对于射线的方向进行了改进，不再采用单一的射线方向，而是给它一个数组的形式来存放不同斜率的射线方向。
整体代码如下：（可直接运行）
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 }
3、补充知识点
C++实现求两条直线的交点
C++实现求两条直线的交点，以及已知直线外一点求垂足_c++求两直线交点_只道寻常zero的博客-CSDN博客
标签：判断,一个点,point,int,double,射线,printf,多边形 From： https://www.cnblogs.com/Zhouce/p/17680781.html