1. 概述
在本教程中，我们将研究如何判断一个点是否位于某个多边形内部。
这个技术在地理围栏（Geofencing）和地理空间分析（Geospatial Analysis）中非常常见。例如在自动入侵检测、车队管理等场景中都有广泛的应用。
2. 点与多边形
2.1. 地理围栏问题
判断一个点是否在某个特定多边形内部，是地理围栏中的典型问题。很多现实应用都需要这个功能，比如：
- 自动识别非法闯入者
- 管理无人机或船舶的活动范围
地理围栏需要先定义一个多边形边界和一个点，然后判断这个点是否在其内部：
如果点在多边形外部：
如果点在多边形内部：
2.2. 简单多边形的判断
对于一些简单多边形（如矩形），我们可以通过数学规则判断点是否在内部：
比如下图这个正方形，如果一个点的坐标满足：
✅ (1 ≤ p_x ≤ 2, 1 ≤ p_y ≤ 2)，则说明该点在内部。
但对于复杂多边形，我们就不能靠简单的数学规则了：
这时候就需要一个通用算法，仅凭顶点坐标就能判断点是否在内部。
3. 判断算法：射线法（Ray Casting）
为了提高效率，我们首先会做一个快速判断：检查点是否在包含多边形的最小矩形内。如果不是，直接判定为外部。
这个最小矩形的边界可以通过以下方式确定：
✅ min(x), max(x), min(y), max(y)
如果点不在这个矩形内，直接返回 false；否则继续下一步。
3.1. 射线法原理
我们使用射线法（Ray Casting Algorithm）来判断点是否在多边形内部。
原理很简单：
- 从点出发，向任意方向发射一条射线（通常选水平向左或向右）
- 统计这条射线与多边形边界的交点数量
- 如果交点数是奇数，则点在内部
- 如果交点数是偶数，则点在外部
这个方法适用于任何形状的多边形，不管多复杂。
如下图所示：
内部点：射线与边界交点数为奇数
外部点：交点数为偶数
3.2. 算法实现细节
实际实现中，我们通常从点向左边发射一条水平射线，并统计与多边形各边的交点数。
算法流程如下：
- 遍历多边形所有边（即顶点两两组成的线段）
- 对于每条边，判断是否与射线相交
- 如果相交，则统计交点数
- 最后根据交点数奇偶性判断是否在内部
判断交点的两个条件：
✅ 条件一：
两个顶点的 y 坐标不能同时大于或小于点的 y 坐标（即它们不在射线同一侧）
(u_y > p_y) != (v_y > p_y)
✅ 条件二：
计算边与射线的交点 x 坐标 s_x：
s_x = u_x + (v_x - u_x) * (p_y - u_y) / (v_y - u_y)
然后判断点的 x 坐标是否在交点的左侧（如果是向右射线则相反）：
if (p_x < s_x) {
count++;
}
如果两个条件都满足，则交点计数加一。
3.3. 流程图
下面是该算法的流程图：
- 初始化
inside = false - 遍历所有顶点对
- 满足两个条件则翻转
inside的值 - 最终
inside为true表示点在多边形内部
4. 实际应用
4.1. 安全防护
地理围栏技术可用于识别非法闯入者，例如：
- 无人机闯入机场禁飞区
- 未经授权的人员进入私人区域
比如在机场，可以设置一个虚拟围栏，当无人机进入该区域时触发警报：
这时就需要使用我们上面提到的算法来判断无人机是否进入禁区。
4.2. 自主导航船舶
国际海事法规定，某些靠近海岸线的海域是禁止进入的，除非获得授权。
如果我们开发一个自动航行系统，必须避免船舶误入这些区域：
这时候可以使用浮标定义一个虚拟围栏，并用该算法判断船只是否在安全区域内。
5. 总结
在本文中，我们学习了如何判断一个点是否在多边形内部。我们介绍了：
- 射线法（Ray Casting Algorithm）的基本原理
- 如何高效判断点是否在多边形内部
- 实现算法的关键逻辑和条件判断
- 该算法在安全防护和自动导航中的实际应用
该算法不仅适用于地理围栏，在图形学、游戏开发、路径规划等领域也有广泛应用。