[C++知识库]C++ 判断点是否在闭合多边形内部(射线法）

1.判断是否在多边形内，法则是点A沿一个方向轴发射一条射线，其中以x轴的右正方向发射射线。接触到多边形的个数为奇数就是在多边形内，否则在多边形外。

2.主要有两种特例，接触顶点和接触线段。

1.接触顶点

图1

?2.接触线段

这两种的处理方法的巧妙之处就在于一开始规定x正向轴发射射线。

这时候可以将与A接触的线段进行判断，如果接触的线段的一个端点的y轴低于A的y轴，认为算一个接触点，否则不算。比如A点的坐标是(10,10)?，图1中的第一个图形，接触顶点的两条线段的两个端点的y轴都没有低于A的y轴坐标，所以不算接触点，总共的接触只有1个。图二中，接触顶点的两条线段的两个端点都低于A的y轴坐标，所以算2个接触点，总共的接触只有3个，所以在多边形内。

//判断点是否在平面多边形范围内,传入一堆顺序的点，每两个点构成一条直线
bool CubeExportYJKHelper::CheckPointIsInPolygon(const iCoord3d &originPt, const vector<iCoord3d> &pts)
{
    //将所有的点转化成线段，首尾相接
    vector<pair<iCoord2d, iCoord2d>> lines;
    for (int i=0;i<pts.size();++i)
    {
        int nextPt = (i + 1) % pts.size();
        lines.emplace_back(make_pair(pts[i], pts[nextPt]));
    }
    iCoord2d oriPt(originPt);
    iVec2d   vec(1,0);
    iCoord2d contactPt(0,0);
    int      count = 0;
    for (const auto&line:lines)
    {
        //判断射线是否和直线相交
        InterResult result =
            Cube::Intersection2Impl::Inter_Segment_Ray(line.first, line.second, oriPt, vec, &contactPt);
        //只要不是交于一点，就继续
        if (result != InterResult::InterPoint)
            continue;
        //判断交点是端点，判断另一点是否在射线下端，如果是，就加1
        double disStartPt = contactPt.DistPtPt(line.first);
        double disEndPt   = contactPt.DistPtPt(line.second);
        //如果不是端点，就加一，跳出
        if (disStartPt > DTE && disEndPt>DTE)
        {
            count++;
            continue;
        }
        //如果一个点大于0，则另外一个点一定小于0
        contactPt = disStartPt <= DTE ? line.second : line.first;
        //如果这个端点的y轴小于起始点的y轴，就加1
        count += contactPt[1] < oriPt[1] ? 1:0;
    }  
    //如果接触点的个数是奇数，就在多边形内部
    return count % 2 == 0 ? true : false;
}

?

?