如何判断点是否在一个不规则的多边形区域内?

Question

请教不使用API CreatePolygonRgn和PtInRegion 方法
如何判断点是否在一个不规则的多边形区域内?
例如判断(x:973763,y:144393)点是否在由
(964826, 140636), (982918, 136537), (990120, 144293), (966908, 151285)
四个顶点组成的不规则多边行区域内呢?
在线等...
小弟在此先谢谢了!

Answer 1

本人找到一段VC 的代码,懂VC的可以借鉴下或帮小弟翻译成为delphi,谢谢!bool   IsPtInArea(AcGePoint3d pt, AcGePoint3dArray& pt3dArr)
{
    int iLen = pt3dArr.length();
    if (iLen < 3)
        return false;
    // 首先构造最小包络面并得到最大 x 坐标
    int i;
    double dblMaxX = pt3dArr[0].x;
    double dblMinX = pt3dArr[0].x;
    double dblMaxY = pt3dArr[0].y;
    double dblMinY = pt3dArr[0].y;
    for (i = 1; i < iLen; i++)
    {
        if (pt3dArr[i].x > dblMaxX)
            dblMaxX = pt3dArr[i].x;
        if (pt3dArr[i].x < dblMinX)
            dblMinX = pt3dArr[i].x;
        if (pt3dArr[i].y > dblMaxY)
            dblMaxY = pt3dArr[i].y;
        if (pt3dArr[i].y < dblMinY)
            dblMinY = pt3dArr[i].y;
    }
    // 如果点位于最小包络面之外，则肯定不在区域内，直接返回 false
    if (( pt.x > dblMaxX) ||
        ( pt.x < dblMinX) ||
        ( pt.y > dblMaxY) ||
        ( pt.y < dblMinY)
        )
        return false;    // 循环求取交点
    pt.z = 0.0;
    AcGePoint3d xpt, ipt; 
    xpt = pt;
    xpt.x = dblMaxX + 10.0;
    //xpt.x = 1.7e208;
    AcGeLineSeg3d lineseg3d(pt, xpt);
    AcGePoint3d p1 = pt3dArr.first();    p1.z = 0.0;
    bool bAdd = false;
    if (!pt3dArr[iLen - 1].isEqualTo(p1)){
        pt3dArr.append(p1);
        iLen++;
        bAdd = true;
    }    AcGePoint3d p2;
    int nCount = 0;
    for (i=1; i < iLen; i++)
    {
        p2 = pt3dArr[i];
        p2.z = 0.0;
        // 如果所给点与顶点相等，直接返回
        if (pt.isEqualTo(p1))
        {
            if (bAdd)
                pt3dArr.removeLast();
            return true;
        }
        AcGeLineSeg3d xlineseg3d(p1, p2);
        // 如果所给点在某一条边上，直接返回
        if (xlineseg3d.isOn(pt) == Adesk::kTrue)
        {
            if (bAdd)
                pt3dArr.removeLast();
            return true;
        }
        // 如果构造线段与交点存在，加入交点表
        if (lineseg3d.intersectWith(xlineseg3d, ipt) == Adesk::kTrue)
        {
            //bool bAdd = true;
            // 如果交点正好为顶点，判断另外的端点在哪一侧
            if (ipt.isEqualTo(p1))
            {
                if (p2.y > ipt.y)
                    nCount++;
            }
            else if(ipt.isEqualTo(p2))
            {
                if (p1.y > ipt.y)
                    nCount++;
            }
            else
                nCount++;
        }
        p1 = p2;
    }    if (bAdd)
        pt3dArr.removeLast();
    
    if ((nCount % 2) == 0)
        return false; // 交点数为偶数，不在区域内
    else
        return true; // 交点数为奇数，在区域内
}

Answer 2

首先你没确定你的不规则多边形是多少条边，这样的话算法写起来比较麻烦
实际算法无非就是几条直线的算法 在直线上恻还是下侧，例如 直线是 y=x+1  那么 y>x+1 则在直线上 y<x+1 在直线下
我也不愿意写，提供个思路，如果要求不是特别精确的话近似处理成个圆 坐起来就简单了
最多判断N次 N=边数

Answer 3

换个思路，你看看GDI+。里面有个“区域”（可以是任何形状），它提供了一个方法可以直接判断某个点是不是在里面。

Answer 4

MMI_BOOL mmi_pen_check_inside_polygon(mmi_pen_polygon_area_struct *polygon, mmi_pen_point_struct pos)
{
    /*----------------------------------------------------------------*/
    /* Local Variables                                                */
    /*----------------------------------------------------------------*/
    MMI_BOOL c = MMI_FALSE;
    S16 i, j;
    S16 nPoints = polygon->num;
    mmi_pen_point_struct *outline = polygon->points;
    S16 x = pos.x;
    S16 y = pos.y;     for (i = 0, j = nPoints - 1; i < nPoints; j = i++)
    {
        mmi_pen_point_struct *a = &outline[i];
        mmi_pen_point_struct *b = &outline[j];        if (((a->y <= y && y < b->y) || (b->y <= y && y < a->y)) &&
            (x < (b->x - a->x) * (y - a->y) / (b->y - a->y) + a->x))
        {
            c = !c;
        }
    }
        return c;
}