如何判断点在多边形内部？

引射线法

从目标点出发，看这条射线与多边形所有边的交点数目，如果是奇数个。说明在多边形内部，偶数个，在多边形外部。

bool inside(vector<point> polygon, point target)
{
        int crossing = 0;
        for(int i = 1; i < polygon.size(); i++)
        {
                double slope = (polygon[i].y - polygon[i-1].y) / (polygon[i].x - polygon[ i-1 ].x);  // 两点之间的斜率
                bool cond1 = ( target.x >= polygon[i-1].x && target.x <= polygon[i].x);              // target 在某边两端点之间
                bool cond2 = ( target.x >= polygon[i].x && target.x <= polygon[i-1].x);              // target 在某边两端点之间
                bool above = (target.y < slope * ( target.x - polygon[i-1].x) + polygon[i-1].y);        // y0 < ax0+b (a = slope)即在两线的下方，因此必有一点相交
                if( (cond1 || cond2) && above) crossing++;
        }
        return (crossing % 2 != 0);                                                                     //若有奇数个点交点，在内部

}