点在多边形内判定

形式陈述 ​

输入是顶点循环序列定义的简单多边形公理库简单多边形Simple polygon由不自交的闭合折线围成、没有孔洞并具有明确内部与外部的平面多边形。 $P$ 和查询点 $q$，输出 inside、outside 或 boundary。算法先对每条边用方向测试公理库方向判定Orientation test用二维或高维行列式符号判断点组转向或仿射定向的基本谓词。与坐标包围判断 $q$ 是否在线段上；命中则立即返回边界。

Ray crossing 方法从 $q$ 向 $+x$ 方向发射水平射线，只统计边的两个端点严格位于 $q$ 水平线两侧的情形：

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

对这些边判断交点是否在 $q$ 右侧，并翻转一个奇偶 bit。使用半开端点规则后，穿过顶点只由相邻两边中的一条计数，水平边不重复贡献。最终奇数为内部、偶数为外部。Winding number 方法则按边向上或向下穿越的方向累加 $+1$ 或 $-1$；对简单有向多边形，内部绕数为 $\pm 1$，外部为 $0$。单次查询时间 $O(n)$、额外空间 $O(1)$。

直觉 ​

从内部走向无穷远，必须跨过边界奇数次；从外部出发则跨过偶数次。顶点恰落在射线上时，若两条邻边都计会凭空增加两次，半开规则相当于把顶点只归给其中一个纵向区间。

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

例子与边界 ​

凹 L 形多边形的包围盒内部含有缺口。位于缺口中的点虽通过最小最大坐标测试，向右射线却与边界横截偶数次，正确分类为外部；这说明包围盒只能快速排除，不是点内证书。

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

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

推论与应用 ​

点内判定用于拾取、地图围栏、碰撞检测和多边形布尔运算。大量静态查询可用三角剖分或空间索引预处理，把每次线性扫描降到对数级；预处理时间和退化处理需另行计入。

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

参考资料

• 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.