点在多边形内判定 | Codeboy's Blog

形式陈述

输入是顶点循环序列定义的简单多边形 $P$ 和查询点 $q$ ，输出 inside、outside 或 boundary。算法先对每条边用方向测试与坐标包围判断 $q$ 是否在线段上；命中则立即返回边界。

Ray crossing 方法从 $q$ 向 $+x$ 方向发射水平射线，先用半开纵向区间筛选边：一个端点严格高于 $q$ ，另一个低于或等于 $q$ ，即

(y_i>y_q)\ne(y_{i+1}>y_q).

对通过筛选的边，计算水平交点

x_* = x_i + (y_q-y_i)\frac{x_{i+1}-x_i}{y_{i+1}-y_i}.

仅当 $x_*>x_q$ 时翻转奇偶位。实现时可完全避免这次除法：由

\operatorname{orient}(v_i,v_{i+1},q) =(y_{i+1}-y_i)(x_*-x_q),

对已通过纵向筛选的上升边，只在 orientation 为正时翻转；对下降边，只在它为负时翻转。这样交点比较也使用同一个精确符号谓词，不必先舍入一个交点坐标。分母不会为零，因为水平边已经被纵向条件排除。普通顶点的上下邻边合计一次，局部极值处则合计零次或两次，因此奇偶性反映真正的横穿。最终奇数为内部、偶数为外部。Winding number 方法则按边向上或向下穿越的方向累加 $+1$ 或 $-1$ ；对简单有向多边形，内部绕数为 $\pm1$ ，外部为 $0$ 。单次查询需要 $O(n)$ 次坐标比较与方向谓词、 $O(1)$ 个额外工作寄存器；在每个基本操作单位成本的模型下时间为 $O(n)$ 。任意精度实现的算术位成本另计。

直觉

Jordan 曲线定理保证这里的两侧确为内部与外部。从内部走向无穷远，每次真正横穿边界都会在内部与外部之间切换；终点在外部，所以起点在内部恰对应奇数次切换。恰好触碰顶点却不穿过去时，不应发生切换。半开规则让这类触碰贡献偶数次，同时让普通穿越贡献一次。

边界是第三种真实答案，不应在最后随意并入内部或外部。API 若只允许布尔值，必须明确 boundary 的归属。

例子与边界

按顺序取 L 形顶点 $(0,0),(3,0),(3,1),(1,1),(1,3),(0,3)$ ，最后连回起点。查询 $q=(0.5,2)$ 时，纵向条件仅留下 $x=0$ 和 $x=1$ 的两条竖边；其中只有 $x=1$ 的交点在右侧，翻转一次，故在内部。查询 $(2,2)$ 时，两交点都在左侧，右射线交数为零，故在外部。两点却都位于同一包围盒内，说明包围盒只能快速排除，不能确认点在内部。

查询 $(1,2)$ 时，方向测试为零，且坐标落在线段 $(1,1)$ 到 $(1,3)$ 的包围范围内，应在奇偶计数前返回边界。同一直线上的 $(1,4)$ 不在这个坐标范围内，不能仅因共线就判为边界。

若射线穿过局部极值顶点，相邻两边都在水平线同侧，几何上只是触碰边界而未真正穿入另一区域。半开条件会让两边贡献零或配对抵消；若简单地把“射线与闭线段相交”全部计数，就可能把一次触碰误当横穿。

浮点坐标下，点几乎落在线上会让 orientation 的符号不稳定。精确整数谓词、自适应精度或明确误差模型比统一 epsilon 更可靠；后者可能破坏对称性，使同一点在相邻边测试中得到互相矛盾的结果。自交多边形还需先选择奇偶填充或非零绕数规则，本页结论只针对简单多边形。

推论与应用

点内判定用于拾取、地图围栏、碰撞检测和多边形布尔运算。大量静态查询可先三角剖分，再建立具有相应最坏界的平面点定位结构，将查询降到 $O(\log n)$ 。只有三角剖分本身，或任意一个通用空间索引，并不自动保证这个界；预处理时间、存储与退化处理需另行计入。

Ray crossing 与 winding number 在简单多边形上给一致分类，却携带不同推广能力：绕数保留方向信息，可描述某些自交曲线；奇偶法只记录穿越次数的模二值。

参考资料

W. Randolph Franklin，PNPOLY — Point Inclusion in Polygon Test，作者技术说明，访问于2026年，The Inequality Tests are Tricky、Point on a (Boundary) Edge：半开计数与单独的边界检测。
Franco P. Preparata and Michael I. Shamos, Computational Geometry: An Introduction, Springer, 1985, Ch. 2.
Joseph O’Rourke, Computational Geometry in C, 2nd ed., Cambridge University Press, 1998, §7.4.

形式陈述 ​

反向链接

形式陈述