判断点是否处于多边形内的方法(含凸凹多边形)
1. 叉乘判别法（只适用于凸多边形）
想象一个凸多边形，其每一个边都将整个2D屏幕划分成为左右两边，连接每一边的第一个端点和要测试的点得到一个矢量v，将两个2维矢量扩展成3维的，然后将该边与v叉乘，判断结果3维矢量中Z分量的符号是否发生变化，进而推导出点是否处于凸多边形内外。这里要注意的是，多边形顶点究竟是左手序还是右手序，这对具体判断方式有影响。
2. 面积判别法（只适用于凸多边形）
第四点分别与三角形的两个点组成的面积分别设为S1,S2,S3，只要S1+S2+S3>原来的三角形面积就不在三角形范围中.可以使用海伦公式 。推广一下是否可以得到面向凸多边形的算法？（不确定）
3. 角度和判别法（适用于任意多边形）
double angle = 0;
realPointList::iterator iter1 = points.begin();
for (realPointList::iterator iter2 = (iter1 + 1); iter2 < points.end(); ++iter1, ++iter2)
{
double x1 = (*iter1).x - p.x;
double y1 = (*iter1).y - p.y;
double x2 = (*iter2).x - p.x;
double y2 = (*iter2).y - p.y;
angle += angle2D(x1, y1, x2, y2);
}
if (fabs(angle - span::PI2) < 0.01) return true;
else return false;
另外，可以使用bounding box来加速。
if (p.x < (*iter)->boundingBox.left ||
p.x > (*iter)->boundingBox.right ||
p.y < (*iter)->boundingBox.bottom ||
p.y > (*iter)->boundingBox.top) 。。。。。。
对于多边形来说，计算bounding box非常的简单。只需要把水平和垂直方向上的最大最小值找出来就可以了。
对于三角形：第四点分别与三角形的两个点的交线组成的角度分别设为j1,j2,j3，只要j1+j2+j3>360就不在三角形范围中。
4. 水平/垂直交叉点数判别法（适用于任意多边形）
注意到如果从P作水平向左的射线的话，如果P在多边形内部，那么这条射线与多边形的交点必为奇数，如果P在多边形外部，则交点个数必为偶数（0也在内）。所以，我们可以顺序考虑多边形的每条边，求出交点的总个数。还有一些特殊情况要考虑。假如考虑边(P1,P2)，
1)如果射线正好穿过P1或者P2,那么这个交点会被算作2次，处理办法是如果P的从坐标与P1,P2中较小的纵坐标相同，则直接忽略这种情况
2)如果射线水平，则射线要么与其无交点，要么有无数个，这种情况也直接忽略。
3)如果射线竖直，而P0的横坐标小于P1,P2的横坐标，则必然相交。
4)再判断相交之前，先判断P是否在边(P1,P2)的上面，如果在，则直接得出结论：P再多边形内部。
再经典不过的算法了：
// 功能：判断点是否在多边形内
// 方法：求解通过该点的水平线与多边形各边的交点
// 结论：单边交点为奇数，成立!
//参数：
// POINT p 指定的某个点
// LPPOINT ptPolygon 多边形的各个顶点坐标（首末点可以不一致）
// int nCount 多边形定点的个数
BOOL PtInPolygon (POINT p, LPPOINT ptPolygon, int nCount)
{
int nCross = 0;
for (int i = 0; i < nCount; i++)
{
POINT p1 = ptPolygon[i];
POINT p2 = ptPolygon[(i + 1) % nCount];
// 求解 y=p.y 与 p1p2 的交点
if ( p1.y == p2.y ) // p1p2 与 y=p0.y平行
continue;
if ( p.y < min(p1.y, p2.y) ) // 交点在p1p2延长线上
continue;
if ( p.y >= max(p1.y, p2.y) ) // 交点在p1p2延长线上
continue;
// 求交点的 X 坐标 --------------------------------------------------------------
double x = (double)(p.y - p1.y) * (double)(p2.x - p1.x) / (double)(p2.y - p1.y) + p1.x;
if ( x > p.x )
nCross++; // 只统计单边交点
}
// 单边交点为偶数，点在多边形之外 ---
return (nCross % 2 == 1);
}
一、从三角形开始说起---怎么判断一个点在三角形内
三角形是最简单的多边形了。先说说三角形有哪些判断方法。
几种方法判断平面点在三角形内独L无二的博客-CSDN博客判断点在三角形内
先假设有△ABC，平面上某点为P。
下面只给出简述，具体实现还得去看参考链接：
1.面积法
简述：将P点与三角形的三个顶点A、B、C连接，分割成三个小三角形△PAB、△PAC、△PBC，这三个小三角形面积之和等于△ABC面积之和则说明P在三角形内。
2.叉积法
简述：对三角形逆时针取向量，那么P点必然在这三个向量的左侧。依照这个特性进行叉积判断叉积后的方向是否指向同一个位置可判断是否在三角形内。
3.重心坐标法(斜坐标系法)
可参考这个链接辅助理解：三角形重心坐标 - 知乎
本质上是以三角形的边建立一个坐标系.
以上三种方法应该是最经典的三种方法了。
二、怎么判断一个点在多边形内
参考自：
判断点是否在多边形内部致守的博客-CSDN博客判断点是否在多边形内部的方法
详谈判断点在多边形内的七种方法（最全面） hdu1756 hrbust1429 为例WilliamSun0122的博客-CSDN博客判断点在多边形内算法
假设为判断某点P是否在多边形A1A2A3A...内。
1.面积和判断法
同上面三角形的判断方法一样，可以将点P与多边形所有顶点连线构成子三角形，判断这些子三角形的面积之和是否等于多边形面积之和。
2.叉积法(适合凸多边形)
同上面三角形的判断方法一样，对凸多边形逆时针取向量，那么P点必然在这些向量的左侧。依照这个特性进行叉积判断叉积后的方向是否指向同一个位置可判断是否在多边形内。
3.重心坐标法
同上面三角形的判断方法一样，将多边形划分成若干三角形，然后用重心坐标性质判断。
4.内角和法
将P点与多边形各个顶点连线，环绕多边形一周，内角和为360°说明在多边形内。
5.光线投射算法
又称交叉数算法或奇偶规则算法
以被P为端点，向任意方向作射线（一般水平向右作射线），统计该射线与多边形的交点数。如果为奇数，P在多边形内；如果为偶数，P在多边形外。
6.二分法
这个是最巧妙的方法。将多边形划分为若干区域，二分地去查询落在哪个子区域，判断是落在哪个子区域内后判断是否落在该区域的三角形内，若是则在多边形内，若不是则在多边形外。
f54a2bd0f9a0b1013113f986c11be052_08d4d632e4714e5989ca26ee9f564f1f.png
