Lync.in

// thePoint：给定的点
// vSelectionPoints：给定的多边形顶点向量
BOOL CheckInside(CPoint thePoint, std::vector vSelectionPoints)
{
    int nCrossCount = 0;
    for (size_t j = 0; j < vSelectionPoints.size(); ++j)
    {
        CPoint &p1 = vSelectionPoints[j];
        CPoint &p2 = vSelectionPoints[(j+1)%vSelectionPoints.size()];
        if (thePoint == p1 || thePoint == p2)
        {
            nCrossCount = 0;
            break;
        }
        else if (thePoint.y > max(p1.y, p2.y) || thePoint.y < min(p1.y, p2.y))
        {
            continue;
        }
        else if (thePoint.y < max(p1.y, p2.y) && thePoint.y > min(p1.y, p2.y))
        {
            if (p2.x == p1.x)
            {
                if (thePoint.x == p1.x)
                {
                    nCrossCount = 0;
                    break;
                }
                else if (thePoint.x < p1.x)
                {
                    nCrossCount++;
                }
            }
            else
            {
                double fCrossX = (thePoint.y - p1.y) * double(p2.x - p1.x) / double(p2.y - p1.y) + p1.x;
                if (fabs(fCrossX - thePoint.x) < ESPILON)
                {
                    nCrossCount = 0;
                    break;
                }
                if (fCrossX > thePoint.x)
                {
                    nCrossCount++;
                }
            }
        }
        else
        {
            if (thePoint.y != p1.y && thePoint.y == p2.y && thePoint.x < p2.x)
            {
                while(TRUE)
                {
                    j++;
                    CPoint *pp3 = &vSelectionPoints[(j+1)%vSelectionPoints.size()];
                    if (pp3->y != p2.y)
                    {
                        break;
                    }
                }
 
                CPoint &p3 = vSelectionPoints[(j+1)%vSelectionPoints.size()];
 
                if (thePoint.y <= max(p1.y, p3.y) && thePoint.y >= min(p1.y, p3.y))
                {
                    nCrossCount++;
                }
            }
        }
    }
    if (nCrossCount % 2 != 0)
    {
        return TRUE;
    }
    return FALSE;
}