多边形中的C＃点

一尘不染

多边形中的C＃点

我试图确定一个点是否在多边形内。多边形是由Point对象数组定义的。我可以很容易地弄清楚该点是否在多边形的边界框内，但是我不确定如何判断它是否在实际的多边形内。如果可能的话，我只想使用C＃和WinForms。我宁愿不调用OpenGL或执行某些简单任务。

这是我到目前为止的代码：

private void CalculateOuterBounds()
{
    //m_aptVertices is a Point[] which holds the vertices of the polygon.
    // and X/Y min/max are just ints
    Xmin = Xmax = m_aptVertices[0].X;
    Ymin = Ymax = m_aptVertices[0].Y;

    foreach(Point pt in m_aptVertices)
    {
        if(Xmin > pt.X)
            Xmin = pt.X;

        if(Xmax < pt.X)
            Xmax = pt.X;

        if(Ymin > pt.Y)
            Ymin = pt.Y;

        if(Ymax < pt.Y)
            Ymax = pt.Y;
    }
}

public bool Contains(Point pt)
{
    bool bContains = true; //obviously wrong at the moment :)

    if(pt.X < Xmin || pt.X > Xmax || pt.Y < Ymin || pt.Y > Ymax)
        bContains = false;
    else
    {
        //figure out if the point is in the polygon
    }

    return bContains;
}

阅读 455

2020-05-19

共1个答案

一尘不染

见这是在C
++中，可以在C＃中的相同方式进行。

对于凸多边形来说太简单了：

如果多边形是凸的，则可以将多边形视为从第一个顶点开始的“路径”。如果一个点始终位于构成路径的所有线段的同一侧，则该点位于该多边形的内部。

给定P0（x0，y0）和P1（x1，y1）之间的线段，另一个点P（x，y）与该线段具有以下关系。计算（y-y0）（x1-x0）-（x-x0）（y1-y0）

如果小于0，则P位于线段的右侧；如果大于0，则P位于线段的左侧；如果等于0，则位于线段上。

这是它在C＃中的代码，我没有检查边缘情况。

        public static bool IsInPolygon(Point[] poly, Point point)
        {
           var coef = poly.Skip(1).Select((p, i) => 
                                           (point.Y - poly[i].Y)*(p.X - poly[i].X) 
                                         - (point.X - poly[i].X) * (p.Y - poly[i].Y))
                                   .ToList();

            if (coef.Any(p => p == 0))
                return true;

            for (int i = 1; i < coef.Count(); i++)
            {
                if (coef[i] * coef[i - 1] < 0)
                    return false;
            }
            return true;
        }

我用简单的矩形测试它工作正常：

            Point[] pts = new Point[] { new Point { X = 1, Y = 1 }, 
                                        new Point { X = 1, Y = 3 }, 
                                        new Point { X = 3, Y = 3 }, 
                                        new Point { X = 3, Y = 1 } };
            IsInPolygon(pts, new Point { X = 2, Y = 2 }); ==> true
            IsInPolygon(pts, new Point { X = 1, Y = 2 }); ==> true
            IsInPolygon(pts, new Point { X = 0, Y = 2 }); ==> false

关于linq查询的说明：

poly.Skip(1)==>创建一个新的列表，从位置开始1的的poly名单，然后由 (point.Y - poly[i].Y)*(p.X - poly[i].X) - (point.X - poly[i].X) * (p.Y - poly[i].Y)我们要计算（这在引用的段落中提到的方向）。相似的例子（另一个操作）：

lst = 2,4,8,12,7,19
lst.Skip(1) ==> 4,8,12,7,19
lst.Skip(1).Select((p,i)=>p-lst[i]) ==> 2,4,4,-5,12

2020-05-19