引例

给出点P的x和y坐标，再给出一个点集A中的所有点的x和y坐标，问P是否在点集A中的点依次围成的多边形的内部？

首先还是使用剪枝算法的思想：将明显不可能的情况排除以提高算法的执行效率。

快速筛选

这个想法非常直观：如果这个点的横坐标在点集的横坐标范围之外或纵坐标在点集的纵坐标范围之外，那么这个点必然不可能处在这个多边形的内部.也就是说，我们通过遍历找到多边形点中x和y的最大最小值，判断待定点的坐标是否在这个区域之内即可。

射线交点判断

定理

从一个多边形内部的点向平面内任意方向引一条射线，射线与多边形有且仅有奇数个交点。
从一个多边形外部的点向平面内任意方向引一条射线，射线与多边形有且仅有偶数个交点。

有了如上的定理，我们就需要思考如何使用编码来把它描述下来：我们不妨让这条线平行于x轴向右，那么：

1. 若某一边的两个端点全在待定点右侧
   1. 若待定点的y坐标介于两者之间(含)，认为相交，计数器+1
   2. 否则，不相交
2. 若某一边的两个端点全在待定点左侧
   不相交
3. 若一个在左侧一个在右侧….

情况3比较复杂：我们需要解出线段上与待定点处于同一y值的点的x坐标，与待定点的x坐标比较，若待定点在右侧，则不相交，否则相交。

综合上述两个方法

typedef pair<double, double> point;

bool inPolygon (point thePoint, const vector<point> &polygon) {
    point max = {DBL_MIN, DBL_MIN}, min = {DBL_MAX, DBL_MAX};
    for_each(polygon.begin(), polygon.end(), [&max, &min](point tempPoint) {
        if (tempPoint.first > max.first) max.first = tempPoint.first;
        if (tempPoint.second > max.second) max.second = tempPoint.second;
        if (tempPoint.first < min.first) min.first = tempPoint.first;
        if (tempPoint.second < min.second) min.second = tempPoint.second;
    });
    if (!(thePoint.first >= min.first && thePoint.first <= max.first && 
        thePoint.second >= min.second && thePoint.second <= max.second)) {
        return false;
    }//快速排除
    
    auto isIntersect = [&thePoint](point a, point b) {
        if (thePoint.first <= a.first && thePoint.first <= b.first) {
            return (thePoint.second - a.second) * (thePoint.second - b.second) < 0;
        } else if (thePoint.first > a.first && thePoint.first > b.first) {
            return false;
        } else {
            if ((thePoint.second - a.second) * (thePoint.second - b.second) > 0) {
                return false;
            } else {
                double slope = (a.second - b.second) / (a.first - b.first);
                double intercept = a.second - slope * a.first;
                return thePoint.first <= (thePoint.second - intercept) / slope;
            }
        }
    };

    int counter = 0;
    for (int i = 0; i < polygon.size() - 1; i++) {
        if (isIntersect(polygon[i], polygon[i + 1]))
            counter++;
    }
    if (isIntersect(polygon.back(), polygon.front()))
        counter++;
    return counter % 2 == 1;
}