Точка C # в многоугольнике

Question

Я пытаюсь определить, находится ли точка внутри многоугольника. полигон определяется массивом объектов 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;
}

Answer 1

Я проверил коды здесь, и у всех есть проблемы.

Лучший метод:

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

Answer 2

Принятый ответ не сработал для меня в моем проекте.Я использовал код, найденный здесь .

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

Answer 3

См. , это , это на 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

Answer 4

Вы можете использовать алгоритм наведения лучей. Это хорошо описано на странице википедии для задачи Точка в многоугольнике .

Это так же просто, как подсчет количества раз, когда луч снаружи к этой точке касается границ многоугольника. Если оно касается четного числа раз, точка находится за пределами многоугольника. Если оно касается нечетного числа раз, точка находится внутри.

Для подсчета количества касаний луча вы проверяете пересечения между лучом и всеми сторонами многоугольника.

Answer 5

Мой ответ взят здесь: Ссылка

Я взял код 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 }));

Answer 6

Полный алгоритм вместе с кодом C доступен на http://alienryderflex.com/polygon/Преобразование его в c # / winforms будет тривиальным.

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

Answer 8

Я рекомендую эту замечательную 15-страничную статью Кая Хорманна (Университет Эрлангена) и Александра Агафоса (Университет Афин). Он объединяет в себе все лучшие алгоритмы и позволит вам обнаружить решения как для намотки, так и для литья лучей.

Точка в задаче о многоугольнике для произвольных многоугольников

Алгоритм интересен для реализации и стоит того. Тем не менее, это настолько сложно, что для меня бессмысленно напрямую относиться к какой-либо его части. Вместо этого я скажу, что если вы хотите самый эффективный и универсальный алгоритм, я уверен, что это он.

Алгоритм становится сложным, потому что он очень высоко оптимизирован, поэтому для его понимания и реализации потребуется много чтения. Тем не менее, он сочетает в себе преимущества алгоритмов наведения луча и числа обмоток, и в результате получается одно число, обеспечивающее оба ответа одновременно. Если результат больше нуля и нечетного, то точка полностью содержится, но если результат является четным числом, то точка содержится в части многоугольника, которая складывается обратно на себя.

Удачи.

Answer 9

Это старый вопрос, но я оптимизировал ответ Саида:

    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.