代码之家 › 专栏 › 技术社区 › jb.

多边形中的C点

algorithm .net c#

jb. · 技术社区 · 14 年前

我想确定一个点是否在多边形内。多边形由点对象数组定义。我可以很容易地找出点是否在多边形的有界框内,但我不知道如何判断它是否在实际多边形内。如果可能的话,我只想使用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;
}

9 回复 | 直到 7 年前

Saeed Amiri 6 年前

见 this 它是用c++编写的,也可以用同样的方法用c++编写。

对于凸多边形太容易了:

如果多边形是凸的,则可以将多边形视为第一个顶点。有一点这个多边形的内部如果它是总是站在同一边构成路径的线段。

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

如果小于0,则P是线段右侧,如果大于如果等于0,则它在左侧 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

meowNET 12 年前

我查过这里的代码,都有问题。

最好的方法是:

    /// <summary>
    /// Determines if the given point is inside the polygon
    /// </summary>
    /// <param name="polygon">the vertices of polygon</param>
    /// <param name="testPoint">the given point</param>
    /// <returns>true if the point is inside the polygon; otherwise, false</returns>
    public static bool IsPointInPolygon4(PointF[] polygon, PointF testPoint)
    {
        bool result = false;
        int j = polygon.Count() - 1;
        for (int i = 0; i < polygon.Count(); i++)
        {
            if (polygon[i].Y < testPoint.Y && polygon[j].Y >= testPoint.Y || polygon[j].Y < testPoint.Y && polygon[i].Y >= testPoint.Y)
            {
                if (polygon[i].X + (testPoint.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) < testPoint.X)
                {
                    result = !result;
                }
            }
            j = i;
        }
        return result;
    }

gunr2171 7 年前

在我的项目中,接受的答案对我不起作用。我最终使用了找到的代码 here .

public static bool IsInPolygon(Point[] poly, Point p)
{
    Point p1, p2;
    bool inside = false;

    if (poly.Length < 3)
    {
        return inside;
    }

    var oldPoint = new Point(
        poly[poly.Length - 1].X, poly[poly.Length - 1].Y);

    for (int i = 0; i < poly.Length; i++)
    {
        var newPoint = new Point(poly[i].X, poly[i].Y);

        if (newPoint.X > oldPoint.X)
        {
            p1 = oldPoint;
            p2 = newPoint;
        }
        else
        {
            p1 = newPoint;
            p2 = oldPoint;
        }

        if ((newPoint.X < p.X) == (p.X <= oldPoint.X)
            && (p.Y - (long) p1.Y)*(p2.X - p1.X)
            < (p2.Y - (long) p1.Y)*(p.X - p1.X))
        {
            inside = !inside;
        }

        oldPoint = newPoint;
    }

    return inside;
}

R. Martinho Fernandes 14 年前

可以使用光线投射算法。它在维基百科的页面上有很好的描述 Point in polygon problem .

这就像计算光线从外部到该点接触多边形边界的次数一样简单。如果它接触偶数次,则该点位于多边形外部。如果它碰到奇数次,那点就在里面。

若要计算光线接触的次数,请检查光线与所有多边形边之间的交点。

Dubbs777 7 年前

meowNET anwser不包括多边形中的多边形顶点和完全位于水平边上的点。如果需要精确的“包含”算法:

public static bool IsInPolygon(this Point point, IEnumerable<Point> polygon)
{
    bool result = false;
    var a = polygon.Last();
    foreach (var b in polygon)
    {
        if ((b.X == point.X) && (b.Y == point.Y))
            return true;

        if ((b.Y == a.Y) && (point.Y == a.Y) && (a.X <= point.X) && (point.X <= b.X))
            return true;

        if ((b.Y < point.Y) && (a.Y >= point.Y) || (a.Y < point.Y) && (b.Y >= point.Y))
        {
            if (b.X + (point.Y - b.Y) / (a.Y - b.Y) * (a.X - b.X) <= point.X)
                result = !result;
        }
        a = b;
    }
    return result;
}

basarat 14 年前

完整的算法和C代码可在 http://alienryderflex.com/polygon/
将它转换为c#/winforms将是很简单的。

Community CDub 8 年前

我的答案来自这里: Link

我把C代码转换成C并使之生效

static bool pnpoly(PointD[] poly, PointD pnt )
    {
        int i, j;
        int nvert = poly.Length;
        bool c = false;
        for (i = 0, j = nvert - 1; i < nvert; j = i++)
        {
            if (((poly[i].Y > pnt.Y) != (poly[j].Y > pnt.Y)) &&
             (pnt.X < (poly[j].X - poly[i].X) * (pnt.Y - poly[i].Y) / (poly[j].Y - poly[i].Y) + poly[i].X))
                c = !c; 
        }
        return c;
    }

可以使用以下示例进行测试:

PointD[] pts = new PointD[] { new PointD { X = 1, Y = 1 }, 
                                    new PointD { X = 1, Y = 2 }, 
                                    new PointD { X = 2, Y = 2 }, 
                                    new PointD { X = 2, Y = 3 },
                                    new PointD { X = 3, Y = 3 },
                                    new PointD { X = 3, Y = 1 }};

        List<bool> lst = new List<bool>();
        lst.Add(pnpoly(pts, new PointD { X = 2, Y = 2 }));
        lst.Add(pnpoly(pts, new PointD { X = 2, Y = 1.9 }));
        lst.Add(pnpoly(pts, new PointD { X = 2.5, Y = 2.5 }));
        lst.Add(pnpoly(pts, new PointD { X = 1.5, Y = 2.5 }));
        lst.Add(pnpoly(pts, new PointD { X = 5, Y = 5 }));

Owen Godfrey 9 年前

我推荐Kai Hormann(爱尔兰根大学)和Alexander Agathos(雅典大学)这篇15页的精彩论文。它整合了所有最好的算法,并将允许您检测缠绕和光线投射解决方案。

The Point in Polygon Problem for Arbitrary Polygons

该算法实现起来很有趣,非常值得。然而,它是如此的复杂,以至于我对它的任何部分都没有意义。我会坚持说,如果你想要最有效和最通用的算法,我确信这就是它。

由于算法是高度优化的,因此变得复杂,因此需要大量的阅读才能理解和实现。然而,它结合了光线投射和缠绕数算法的优点,结果是一个同时提供两个答案的数字。如果结果大于零且为奇数,则该点完全包含,但如果结果为偶数,则该点包含在自折叠的多边形的一部分中。

祝你好运。

too 6 年前

我的PointInPolygon函数的业务关键实现(正如OP似乎正在使用的那样)是对水平线、垂直线和对角线进行单元测试的,行上的点包含在测试中(函数返回true)。

这似乎是一个老问题,但之前的所有跟踪示例都有一些缺陷:不要考虑水平或垂直多边形线、多边形边界线或边的顺序(顺时针、逆时针)。

下面的函数通过了我提出的测试(正方形、菱形、对角线交叉、总共124个测试),测试的点在边上、顶点上,以及边和顶点的内部和外部。

代码对每个连续的多边形坐标对执行以下操作:

检查多边形顶点是否等于该点
检查点是否在水平或垂直线上
计算(作为double)并收集转换为整数的相交
对相交进行排序,使边的顺序不影响算法
检查点是否在偶数相交处(多边形中等于)
检查点x坐标前的相交数是否为奇数多边形

算法可以很容易地适应浮点数和双倍数(如果需要)。

顺便说一下,我想知道在过去的近10年里,有多少软件是用来检查多边形中的某个点的,但在某些情况下却失败了。

    public static bool IsPointInPolygon(Point point, IList<Point> polygon)
    {
        var intersects = new List<int>();
        var a = polygon.Last();
        foreach (var b in polygon)
        {
            if (b.X == point.X && b.Y == point.Y)
            {
                return true;
            }

            if (b.X == a.X && point.X == a.X && point.X >= Math.Min(a.Y, b.Y) && point.Y <= Math.Max(a.Y, b.Y))
            {
                return true;
            }

            if (b.Y == a.Y && point.Y == a.Y && point.X >= Math.Min(a.X, b.X) && point.X <= Math.Max(a.X, b.X))
            {
                return true;
            }

            if ((b.Y < point.Y && a.Y >= point.Y) || (a.Y < point.Y && b.Y >= point.Y))
            {
                var px = (int)(b.X + 1.0 * (point.Y - b.Y) / (a.Y - b.Y) * (a.X - b.X));
                intersects.Add(px);
            }

            a = b;
        }

        intersects.Sort();
        return intersects.IndexOf(point.X) % 2 == 0 || intersects.Count(x => x < point.X) % 2 == 1;
    }

z3nth10n 6 年前

这是个老问题,但我优化了答案:

    public static bool IsInPolygon(this List<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));

        var coefNum = coef.GetEnumerator();

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

        int lastCoef = coefNum.Current,
            count = coef.Count();

        coefNum.MoveNext();

        do
        {
            if (coefNum.Current - lastCoef < 0)
                return false;

            lastCoef = coefNum.Current;
        }
        while (coefNum.MoveNext());

        return true;
    }

使用IEnumerators和IEnumerables。