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

Ответ 1

Посмотрите это это в c++ и можете сделать в С# таким же образом.

для выпуклого многоangularьника это слишком просто:

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

Given a line segment between P0 (x0,y0) и 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 тогда он лежит на отрезке.

Вот его код в С#, я не проверял крайние случаи.

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

Я проверяю это с простым прямоangularьником, работает нормально:

            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

Ответ 2

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

Лучший способ:

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

Ответ 3

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

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

Ответ 4

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

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

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

Ответ 5

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

Ответ 6

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

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

Ответ 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;
}

Ответ 8

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

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

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

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

Удачи.

Ответ 9

Моя критически важная бизнес-реализация функции PointInPolygon, работающей с целыми числами (как, кажется, использует OP), является модульным тестированием для горизонтальных, вертикальных и диагональных линий, точки на линии включены в тест (функция возвращает true).

Это кажется старым вопросом, но все предыдущие примеры трассировки имеют некоторые недостатки: не учитывают горизонтальные или вертикальные линии многоangularьника, границу линии многоangularьника или порядок ребер (по часовой стрелке, против часовой стрелки).

Следующая функция проходит тесты, которые я придумала (квадрат, ромб, диагональный крест, всего 124 теста) с точками на ребрах, вершинах и только внутри и снаружи ребра и вершины.

Код выполняет следующие действия для каждой последовательной пары координат многоangularьника:

1. Проверяет, равна ли вершина многоangularьника точке
2. Проверяет, находится ли точка на горизонтальной или вертикальной линии
3. Вычисляет (как двойное) и собирает пересечения с преобразованием в целое число
4. Сортировка пересекается, поэтому порядок ребер не влияет на алгоритм
5. Проверяет, находится ли точка на четном пересечении (равно - в многоangularьнике)
6. Проверяет, является ли количество пересечений перед точкой x нечетной - в многоangularьнике

Алгоритм может быть легко адаптирован для чисел с плавающей запятой и удваивается при необходимости.

В качестве примечания: мне интересно, сколько программ было создано за последние почти 10 лет, которые проверяют точку в многоangularьнике и в некоторых случаях дают сбой.

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

Ответ 10

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

    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.