//判断点是否在闭合区域内

admin1

判断一个点，或者说某个物体是否在一个多边形内，或者说是否在某个区域内，在几何算法中还是比较常见的也比较实用的，如何判断呢，这在凸多边形里面应该比较容易，但是不规则多边形就需要比较特殊的方法了。无论是凹多边形，凸多边形，长歪了的各种多边形里面都适用。 本文使用射线法判断点是否在多边形内部。[code]//判断点是否在闭合区域内
bool IsPointInPolygon(Point p, vector points)
{
//vector points:表示闭合区域由这些点围成
    double minX = points[ 0 ].x;
    double maxX = points[ 0 ].x;
    double minY = points[ 0 ].y;
    double maxY = points[ 0 ].y;
    for ( unsigned int i = 1 ; i < points.size() ; i++ )
    {
        Point q = points[ i ];
        minX = min( q.x, minX );
        maxX = max( q.x, maxX );
        minY = min( q.y, minY );
        maxY = max( q.y, maxY );
    }
​
    if ( p.x < minX || p.x > maxX || p.y < minY || p.y > maxY )
    {
        return false;
    }
​
    bool inside = false;
    for ( unsigned int i = 0, j = points.size() - 1 ; i < points.size() ; j = i++ )
    {
        if ( ( points[ i ].y > p.y ) != ( points[ j ].y > p.y ) &&
            p.x < ( points[ j ].x - points[ i ].x ) * ( p.y - points[ i ].y ) / ( points[ j ].y - points[ i ].y ) + points[ i ].x )
        {
            inside = !inside;
        }
    }
​
    return inside;
}[/code]