1. 射线法:不需考虑精度误差和多边形点给出的顺序。

    计算几何-射线法

  2. 转角法:要求多边形是有顺序的,按照多边形顶点逆时针顺序,从 P 点到顶点 Vi 分别做连线,其中 αi 为 Vi 和 Vi+1 之间的夹角。其中 α 角度逆时针为正,顺时针为负,这样所有到顶点做连线之间夹角和为(环绕数)0,这点P在多边形外部,否则在内部。

    计算几何-转角法

  3. 射线法改进:针对有方向的多边形,通过判断射线穿过的边和点的位置(比如点在线的左侧为正,右侧为负),和为 0 则点在外部。

    计算几何-射线法改进

  4. 叉积法:适用凸多边形,如果一个点在多边形所有有向边的左边,那么这个点一定在多边形内部。

  5. 面积法:类似叉积法,适用凸多边形。如果点在多边形内部或者边上,那么点与多边形所有边组成的三角形面积和等于多边形面积。

参考:

  1. 详谈判断点在多边形内的七种方法(最全面) hdu1756 hrbust1429 为例