如何判断一个点在多边形内

一、从三角形开始说起---怎么判断一个点在三角形内

三角形是最简单的多边形了。先说说三角形有哪些判断方法。

参考自：

先假设有

下面只给出简述，具体实现还得去看参考链接：

1.面积法

简述：将P点与三角形的三个顶点A、B、C连接，分割成三个小三角形

 2.叉积法

简述：对三角形逆时针取向量，那么P点必然在这三个向量的左侧。依照这个特性进行叉积判断叉积后的方向是否指向同一个位置可判断是否在三角形内。

3.重心坐标法(斜坐标系法)

可参考这个链接辅助理解：

本质上是以三角形的边建立一个坐标系.

以上三种方法应该是最经典的三种方法了。

二、怎么判断一个点在多边形内

参考自：

假设为判断某点P是否在多边形A1A2A3A...内。

1.面积和判断法

同上面三角形的判断方法一样，可以将点P与多边形所有顶点连线构成子三角形，判断这些子三角形的面积之和是否等于多边形面积之和。

2.叉积法(适合凸多边形)

同上面三角形的判断方法一样，对凸多边形逆时针取向量，那么P点必然在这些向量的左侧。依照这个特性进行叉积判断叉积后的方向是否指向同一个位置可判断是否在多边形内。

3.重心坐标法

同上面三角形的判断方法一样，将多边形划分成若干三角形，然后用重心坐标性质判断。

4.内角和法

将P点与多边形各个顶点连线，环绕多边形一周，内角和为360°说明在多边形内。

5.光线投射算法

又称交叉数算法或奇偶规则算法

以被P为端点，向任意方向作射线（一般水平向右作射线），统计该射线与多边形的交点数。如果为奇数，P在多边形内；如果为偶数，P在多边形外。

6.二分法

这个是最巧妙的方法。将多边形划分为若干区域，二分地去查询落在哪个子区域，判断是落在哪个子区域内后判断是否落在该区域的三角形内，若是则在多边形内，若不是则在多边形外。