C# 多边形中的点 [英] C# Point in polygon

问题描述

我正在尝试确定一个点是否在多边形内.Polygon 由 Point 对象数组定义.我可以很容易地确定该点是否在多边形的有界框内，但我不确定如何判断它是否在实际多边形内.如果可能，我只想使用 C# 和 WinForms.我宁愿不调用 OpenGL 或其他东西来完成这个简单的任务.

I'm trying to determine if a point is inside a polygon. the Polygon is defined by an array of Point objects. I can easily figure out if the point is inside the bounded box of the polygon, but I'm not sure how to tell if it's inside the actual polygon or not. If possible, I'd like to only use C# and WinForms. I'd rather not call on OpenGL or something to do this simple task.

这是我目前的代码:

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;
}

推荐答案

参见 this 它是在 c++ 中，可以在 c# 中以相同的方式完成.

See this it's in c++ and can be done in c# in a same way.

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

for convex polygon is too easy:

如果多边形是凸的，那么可以将多边形视为来自第一个顶点.一个点在如果是这个多边形的内部总是在所有人的同一边构成路径的线段.

If the polygon is convex then one can consider the polygon as a "path" from the first vertex. A point is on the interior of this polygons if it is always on the same side of all the line segments making up the path.

给定 P0 之间的线段(x0,y0) 和 P1 (x1,y1)，另一个点P(x,y)有如下关系到线段.计算 (y - y0)(x1 - x0) - (x - x0) (y1 - y0)

Given a line segment between P0 (x0,y0) and P1 (x1,y1), another point P (x,y) has the following relationship to the line segment. Compute (y - y0) (x1 - x0) - (x - x0) (y1 - y0)

如果它小于 0 则 P 是线段的右侧，如果更大比 0 靠左，如果等于0 那么它位于线段上.

if it is less than 0 then P is to the right of the line segment, if greater than 0 it is to the left, if equal to 0 then it lies on the line segment.

这是它的 C# 代码，我没有检查边缘情况.

Here is its code in c#, I didn't check edge cases.

        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;
        }

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

I test it with simple rectangle works fine:

            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 查询的说明:

Explanation on the linq query:

poly.Skip(1) ==> 创建一个新列表，从 poly 列表的位置 1 开始，然后通过(point.Y - poly[i].Y)*(pX - poly[i].X) - (point.X - poly[i].X) * (pY - poly[i].Y) 我们将计算方向(在参考段落中提到).类似的例子(有另一个操作):

poly.Skip(1) ==> creates a new list started from position 1 of the poly list and then by (point.Y - poly[i].Y)*(p.X - poly[i].X) - (point.X - poly[i].X) * (p.Y - poly[i].Y) we'll going to calculate the direction (which mentioned in referenced paragraph). similar example (with another operation):

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

这篇关于C# 多边形中的点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！