多边形内外点判断

当我们用凸包检测(凸边形)或其他方法计算出了多边形边形的边界时，而接下来由于算法需要，需要区分出多边形的内点与外点。那么如何判断一个图像中一个点在凸包内还是外呢？
一. 理论思路

1. 方法一：夹角判断法，目标点与所有边的夹角和是否为，为，则在多边形内部；
2. 方法二：面积判断法，目标点与多边形每条边组成的三角形面积和是否等于该多边形的面积之和，若相等，则在多边形内部；
3. 方法三：引射线法：从目标点引发出一条射线，看这条射线与多边形所有边的交点数目，如果有奇数个角点，则说明在内部，如果有偶数个交点，则说明在外部，射线法的示意图如图1所示。算法PNPoly
   
   图1 射线法示意图
   
   二. 详细代码 (c++)

/// step1 判断点是否在包围多边形的最大四边形内
if (p.x < minX || p.x > maxX || p.y < minY || p.y > maxY)
 {
return 0;
}
/// step 2 基于采用方法三，判断目标点与多边形的交点个数
/// 其中nvert为多边形的顶点个数
/// vertx、verty为顺时针存储的多边形的顶点的x-、y-坐标
/// testx、testy为目标点坐标
/// 语句(verty[i]>testy) != (verty[j]>testy)表达了目标点Y轴在起始结束点之间，
又同时解决了射线点如果和边框线顶点重合的问题
int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int node = 0;
  for (int i = 0, j = nvert-1; i < nvert; j = i++) 
  {
    if ( ((verty[i]>testy) != (verty[j]>testy)) &&
     (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       node  = !node ;
  }
  return node ;
}

参考链接
判断一个坐标点是否在不规则多边形内部的算法
如何判断一个点是否在多边形内部