做地图交互和图形编辑的时候我几乎每周都要处理“判断点在多边形内”这类需求。用户随便点一下屏幕你就得知道他落在哪个地块、哪个选区、哪个障碍物里多边形可能是几十个顶点的不规则地块也可能是随手画出来的凹多边形区域。射线法是这类问题里最经典也最稳的思路网上资料不少但绝大多数只给你核心那几行循环顶点穿越、边界归属、浮点误差这些真正要命的地方全靠自己踩。这篇我把自己从原理到生产级实现完整过一遍特别是边界规则为什么必须钉死以及大数据量下怎么提速看完你基本可以拿着代码直接干活。1. 为什么“画一条水平线数交点”能判断内外原理和数学化过程1.1 奇偶性是“穿墙次数”的累计射线法的几何直觉来自拓扑学里的一个朴素结论从目标点向无穷远处发出一条射线这条射线与多边形边界的交点数量如果是奇数点就在多边形内部如果是偶数点就在外部。为什么成立想象你站在多边形内部往外走走出边界的那一瞬间会穿过一次边界如果你站在外部想要进入内部必然也要穿过一次边界。把整个路径看作从目标点出发到无穷远的旅行进入和离开是一个成对事件只有起点在内部时旅行才会以“多出来的一次穿越”结束。对应到代码里就是用一个布尔值inside在每次遇到边界交点时取反最后看它是 true 还是 false。这个直觉简单但有个关键问题怎么把“引一条射线”落到代码里如果真去构造一条射线再和每条边求真正交点计算量会大不少而且射线方向选不好还会跟顶点纠缠不清。工程上普遍采用的方案是固定一条水平射线也就是从目标点向右水平延伸然后逐边判断。1.2 为什么实现里都选水平射线选择水平射线不是为了数学上更漂亮而是为了让“判断边与射线是否相交”这件事变得极其廉价。对每条边 (xi, yi) 到 (xj, yj)水平射线 y py 会穿过这条边当且仅当边线的两个端点分别位于水平线的上下两侧。也就是说yi和yj中一个大于py另一个小于py。这个条件用代码写出来就是(yi py) ! (yj py)一次比较搞定根本不需要真的把射线构造出来。真正确定交点横坐标时再用相似三角形做线性插值。从 i 到 j 的这段线段上当 y 从 yi 变化到 yj 时x 也线性变化。已知目标点的 py那么交点横坐标就是x_cross (xj - xi) * (py - yi) / (yj - yi) xi注意分母(yj - yi)在上面的端点两侧条件保证下不可能为 0所以不会出现除零错误。算出来之后只需要判断px x_cross即可。这里固定向右射线是因为我们把比较方向统一成“交点在目标点右侧”翻转标记的逻辑就非常简单直接。整个过程完全不用动态规划、不用向量场、不用包围体积就是逐条边扫一遍每次只做常数次浮点运算时间复杂度稳定在 O(n)。这个特性在数据量一般的交互场景里非常友好甚至在几千个顶点的多边形上也能保持实时性能。2. 射线穿过顶点时最容易翻车半开半闭规则怎么钉死边界2.1 顶点被射线精准命中的尴尬射线法实现里最容易出问题的不是凹多边形也不是孔洞而是“射线恰好经过顶点”。假设目标点发出的一条水平射线正好穿过某个顶点 V那么从数学上看这条射线在 V 点同时接触了相邻的两条边。如果代码里两条边都被统计进交点数量这个顶点就被算了两次如果相邻两条边因为浮点误差出现一侧漏判、另一侧补判那结果完全取决于比较时的偶然偏向。我最早写第一版实现时就吃过这个亏同样的多边形、同样的点在 A 坐标精度下返回 true换到 B 坐标精度下返回 false查了两天才定位到是顶点穿越时统计规则不统一。这个问题的根源在于交点数量的奇偶性判断依赖的是“射线对边界是否发生了穿越”而不是“射线与边界是否接触”。而顶点接触属于边界情形必须人为约定一种统一的计数规则才能让结果稳定下来。2.2 半开半闭规则的准确表述与验证主流做法是定一条“半开半闭”规则直白讲就是统计交点时边的一个端点严格大于 py另一个端点小于等于 py两者不同时才认为这条边与射线相交。对应代码是(yi py) ! (yj py)注意我这里特意写了“一个严格大于另一个小于等于”而不是两边都用大于等于。这样做的效果是如果 py 恰好等于某个顶点的 y 坐标那么共享这个顶点的两条边中只有那条以该顶点为“上端点”的边会被统计另一条不会被统计。顶点无论落在哪条相邻边上最终都只会被计数器看到一次。我用一个简单的矩形验证给你看。矩形顶点按序为 (0,0)、(4,0)、(4,4)、(0,4)目标点取 (2,0)这个点落在底边上。如果不做任何边界特殊处理按半开半闭规则扫描边 (0,0)-(4,0)两个端点都不大于 py0不统计边 (4,0)-(4,4)一端等于 0另一端为 4 大于 0统计交点在 x4px2 4翻转边 (4,4)-(0,4)两端都大于 0不统计边 (0,4)-(0,0)一端大于 0另一端等于 0统计交点在 x0px2 0 不成立不翻转。最终内部标记为 true符合“边界点位应视为内部”的直觉。更关键的是如果目标点移到 (5,0) 这种真正的外部点数值上只会经过 x4 那一次统计翻转一次后变成 outside也正确。2.3 点在边上必须单独判断射线法统计本身解决的只是“点在多边形内部还是外部”的二值问题它不负责“点在边界上”的判断。但实际业务里用户点击恰好落在描边上实在太常见了这时候你得有一个独立检测。判断点在边上的标准做法有两个条件同时成立点到线段所在直线的距离为 0也就是叉积为 0点在线段的包围盒内即坐标落在两端点之间。cross (px - xi) * (yj - yi) - (py - yi) * (xj - xi)当cross的绝对值小于某个 epsilon且px、py都落在线段的范围里就可以判定点在边界上。因为射线统计对边界点的结果不稳定所以这个检测一定要放在射线统计之前命中就直接返回“边界”或“内部”不往下走了。3. 可直接抄走的实现JavaScript 与 C 双版本走读3.1 JavaScript 实现与逐行解释下面这个版本我一直在用前端地图、可视化项目里都跑过包含边界检测、半开半闭射线统计、epsilon 容差可以直接复制使用function pointInPolygon(px, py, polygon, eps 1e-9) { let inside false; const n polygon.length; let j n - 1; for (let i 0; i n; i) { const xi polygon[i][0]; const yi polygon[i][1]; const xj polygon[j][0]; const yj polygon[j][1]; // 边界检测叉积 包围盒 const cross (px - xi) * (yj - yi) - (py - yi) * (xj - xi); if ( Math.abs(cross) eps px Math.min(xi, xj) - eps px Math.max(xi, xj) eps py Math.min(yi, yj) - eps py Math.max(yi, yj) eps ) { return true; } // 半开半闭规则一个端点严格大于 py另一个小于等于 py if ((yi py) ! (yj py)) { const xCross ((xj - xi) * (py - yi)) / (yj - yi) xi; if (px xCross) { inside !inside; } } j i; } return inside; }几个值得说明的细节let j n - 1配合循环末尾的j i让每轮处理的边都是“从 j 到 i”也就是上一条边到当前顶点形成闭合环边界检测放在循环内部最前面而不是单独对每条边预检完再进入主循环是因为这样写最自然一条边兼容了“边界返回”和“射线统计”两个职责Math.abs(cross) eps里的 eps 是容差后续会专门讲怎么选返回true时包含了“点在边上”这一情况如果你希望边界点返回 false把return true改成一个return false或者加一个模式参数即可。3.2 C 实现与循环衔接细节C 版本逻辑完全一致只是把数组换成std::vector更适合偏底层一点的项目#include vector #include cmath #include algorithm struct Point { double x; double y; }; bool pointInPolygonRayCasting(const Point p, const std::vectorPoint poly, double eps 1e-9) { bool inside false; int n static_castint(poly.size()); for (int i 0, j n - 1; i n; j i) { const Point a poly[i]; const Point b poly[j]; double cross (p.x - a.x) * (b.y - a.y) - (p.y - a.y) * (b.x - a.x); if (std::abs(cross) eps p.x std::min(a.x, b.x) - eps p.x std::max(a.x, b.x) eps p.y std::min(a.y, b.y) - eps p.y std::max(a.y, b.y) eps) { return true; } if ((a.y p.y) ! (b.y p.y)) { double xCross (b.x - a.x) * (p.y - a.y) / (b.y - a.y) a.x; if (p.x xCross) { inside !inside; } } } return inside; }这里for (int i 0, j n - 1; i n; j i)是 C 里常见的闭合环遍历写法。每一轮i是当前点j是上一个点等循环结束执行j ij就自然变成下一轮的前驱点不需要额外维护状态。3.3 关于 epsilon 和浮点误差的实测经验epsilon 的选取是整个实现里最需要根据场景调的地方我给不出一个万能值但可以给你一个参考范围。如果坐标来自整数像素点或者整数网格epsilon 设成1e-9甚至直接0都没问题因为整数运算在双精度表示下是精确的。如果坐标来自经纬度、测量数据或连续动画坐标浮点误差就会累积我自己习惯在1e-9到1e-6之间取一个值。太小则边界检测形同虚设太大则会把真正在边界附近的点错误吸入。有个很实用的技巧把 epsilon 和坐标量级绑在一起。比如坐标是十万级别就可以用1e-9 * 100000这样一个相对容差。不要直接对经纬度数据用绝对容差因为纬度一度对应的实际距离在不同地区差异非常大。4. 凹多边形、带孔多边形和脏数据真实项目里的X因素4.1 凹多边形完全不需要额外处理射线法最让我省心的地方就是它完全不在意多边形是凸是凹。凸多边形的点在内部判断可以用叉积法沿着某个方向把所有边的叉积检查一遍效率很高但前提是顶点顺序严格顺时针或逆时针。凹多边形里叉积法就废了因为凹进去的区域会让叉积符号出现翻转。射线法没有这个问题它统计的是边界穿越次数凹形区域无非是让射线多穿越几个边界段奇偶性照样成立。我另一个项目里处理过一块非常刁钻的“回”字形选区中间凹进去很深射线一次穿过就会跨越三个边界段。用射线法跑出来的结果和用户视觉判断完全吻合不需要额外写任何分支。4.2 带孔多边形分而治之优于拼接带孔多边形在 GIS 数据里很常见比如一个地块中间有块水域水域就是多边形里的孔。处理方式有两种我推荐第一种。第一种思路最简单判断点在“外环多边形”内并且不在任何一个“孔多边形”内两者同时成立才返回 true。实现上就是调用两次函数function pointInPolygonWithHoles(px, py, outerRing, holes) { if (!pointInPolygon(px, py, outerRing)) return false; for (const hole of holes) { if (pointInPolygon(px, py, hole)) return false; } return true; }第二种思路是把孔反向绕行后拼进外环的顶点数组里再用一次射线法判断。这种写法可以让调用方只看到一个多边形对象但有一个非常大的前提外环和孔洞数据必须严格有序且方向正确任何一条边的方向反转都会让结果完全错乱。在真实工程数据里这种前提往往不成立所以我几乎只推荐第一种分而治之的方式。4.3 自交多边形和重复顶点自交多边形也就是边与边自己交叉的图形射线法仍然会给出一个确定答案但那个答案不一定符合你的业务直觉。射线法对自交多边形统计的是“射线穿过的边界段数”因此它给出的内部区域是交替出现的多块地方。如果你希望自交部分所在的整个区域都算内部需要改用环绕数法。环绕数法的计算量更大但能区分绕行方向不同的区域。工程里真正遇到自交多边形的时候我通常先和业务方确认一次“内部到底是什么定义”不要在算法层面替业务做决定。重复顶点是另一个容易忽视的坑。数据里偶尔会出现连续两个相同的坐标点比如(2,3)后面又跟了一个(2,3)。这种点会让叉积检测得到零向量虽然绝大多数实现不会因此崩溃但可能让你在调试时懵很久。我习惯在预处理阶段直接把相邻重复点过滤掉。5. 点很多多边形很大的时候预筛与索引的提速组合5.1 包围盒预筛是第一道闸射线法的 O(n) 在单次调用时很香但在“一次对几万个点做空间查询”的场景里比如批量校验多个设备的位置每个点都扫一遍几千条边就太浪费了。最实用的第一道预筛是包围盒先算一次多边形的最小外接矩形如果一个点在矩形之外那必然在多边形之外直接返回 false根本不需要走进主循环。判断一次矩形包含只需要四次比较成本极低跑在射线主循环之前可以过滤掉大量明显不相关的点。function pointInPolygonFast(px, py, polygon) { // bbox 在首次调用时算好并缓存 if (px bbox.minX || px bbox.maxX || py bbox.minY || py bbox.maxY) { return false; } return pointInPolygon(px, py, polygon); }5.2 网格索引适合高频查询如果多边形顶点特别多同时查询次数也特别多包围盒就不够用了。可以建立一个网格索引把多边形的每条边根据其包围盒插入到覆盖它的网格格子里查询时先根据目标点定位到所在格子再只对格子里的边做射线统计。这个方案的本质是空间换时间。格子开得越细每个格子覆盖的边越少但索引构建和维护的成本越高。我做个简单测试一个 5000 条边的多边形对 10 万个点做归属查询纯射线法是 5000 万次边循环网格索引把每个点需要检查的边数降到几十条整体提速非常可观。网格索引最需要注意的点是格子边界。一条边可能跨越多个格子如果插入时只放进起点所在的格子查询点落在这条边位于其他格子的部分时就会漏判。所以我插入边的时候会把这条边经过的所有格子都登记上宁可多存几条重复的边引用也不能漏。5.3 预处理简化边界还有一种思路不太起眼但很有效在精度允许的前提下先对多边形做一次简化把边数降下来。比如 Douglas-Peucker 算法在保持整体形状的前提下减少顶点数量然后对简化后的多边形执行射线法。这个优化尤其适合那种顶点特别密、但形状其实很简单的多边形比如一段弯弯曲曲的等高线三千个顶点简化成一百个判断精度损失不大但性能提升是几十倍的。唯一需要注意的是不要简化掉小尺度的关键特征比如需要精确判断某个点是否在某个小凹槽里时简化容差会导致这些小特征被抹掉。6. 实际项目里最容易出问题的三种场景和我的处理习惯6.1 三态返回值比布尔值更省心我最早实现射线法时只返回布尔值后来在一个地图选区的需求里被折腾了一回选区边界是用描边样式画的用户点击边界时业务方要求不仅算“选中”还要求高亮样式跟内部选中不一样。布尔值根本表达不了三种状态。后来我把函数改成返回 -1、0、1分别对应外部、边界、内部。改造其实很简单边界检测命中时返回 0其余按照布尔统计返回 -1 或 1。这个三态版本在我后续好几个项目里都直接复用了。如果你的业务里也存在“边界单独处理”的需求强烈建议一开始就设计成三态不要等需求过来再改。6.2 坐标方向不一致容易看反结果屏幕坐标系的 y 轴是向下的数学坐标系的 y 轴是向上的。射线法本身对这个不敏感因为算法只关心相对大小但如果你把结果可视化出来调试或者把多边形数据和点击坐标混用了坐标系很容易在看结果时产生错觉。我的经验是调试任何空间算法时第一步永远是画图。把多边形、目标点、水平射线和交点位置都画出来一眼就能看出是算法问题还是坐标系问题。这东西放在脑海里想象很容易把自己绕进去。6.3 一个小工具函数封装最后给一个我认为很实用的封装思路。把射线法做成一个接受配置对象的工厂函数这样你可以在一个文件里集中定义 epsilon、边界模式、是否启用包围盒预筛等参数function createPointInPolygon({ eps 1e-9, boundary inside } {}) { return function isInside(px, py, polygon) { return pointInPolygon(px, py, polygon, eps) ? (boundary inside ? true : true) : false; }; }这段代码里的 ternary 写法有点取巧更多是示意。真正要表达的是eps 和 boundary 这些策略不应该散落在业务代码里集中到工厂函数里业务方只需要关心语义化的调用。我在实际项目中还会把射线法封装到一个独立的几何工具模块里和向量计算、包围盒计算放一起。后续不管做前端还是后端只要需要这类判断直接拉这个模块就行。判断点在多边形内这个功能看着小一旦把边界规则、容差策略、性能优化都理顺在你后续所有空间计算需求里都能用得上。
