Geo Fencing - точка внутри / снаружи полигона

Question

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

Кто-нибудь знает, есть ли какой-либо пример подобного алгоритма?

Answer 1

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

Если ответ странный, вы внутри. Если ответ четный, вы снаружи.

Редактировать: Да, что он сказал ( Википедия ):

Answer 2

код C #

bool IsPointInPolygon(List<Loc> poly, Loc point)
{
    int i, j;
    bool c = false;
    for (i = 0, j = poly.Count - 1; i < poly.Count; j = i++)
    {
        if ((((poly[i].Lt <= point.Lt) && (point.Lt < poly[j].Lt)) 
                || ((poly[j].Lt <= point.Lt) && (point.Lt < poly[i].Lt))) 
                && (point.Lg < (poly[j].Lg - poly[i].Lg) * (point.Lt - poly[i].Lt) 
                    / (poly[j].Lt - poly[i].Lt) + poly[i].Lg))
        {

            c = !c;
        }
    }

    return c;
}

Класс местоположения

public class Loc
{
    private double lt;
    private double lg;

    public double Lg
    {
        get { return lg; }
        set { lg = value; }
    }

    public double Lt
    {
        get { return lt; }
        set { lt = value; }
    }

    public Loc(double lt, double lg)
    {
        this.lt = lt;
        this.lg = lg;
    }
}

Answer 3

Просто взгляните на проблему точка-полигон (PIP) .

Answer 4

После поиска в Интернете, пробуя различные реализации и портируя их с C ++ на C #, я наконец-то понял свой код:

        public static bool PointInPolygon(LatLong p, List<LatLong> poly)
    {
        int n = poly.Count();

        poly.Add(new LatLong { Lat = poly[0].Lat, Lon = poly[0].Lon });
        LatLong[] v = poly.ToArray();

        int wn = 0;    // the winding number counter

        // loop through all edges of the polygon
        for (int i = 0; i < n; i++)
        {   // edge from V[i] to V[i+1]
            if (v[i].Lat <= p.Lat)
            {         // start y <= P.y
                if (v[i + 1].Lat > p.Lat)      // an upward crossing
                    if (isLeft(v[i], v[i + 1], p) > 0)  // P left of edge
                        ++wn;            // have a valid up intersect
            }
            else
            {                       // start y > P.y (no test needed)
                if (v[i + 1].Lat <= p.Lat)     // a downward crossing
                    if (isLeft(v[i], v[i + 1], p) < 0)  // P right of edge
                        --wn;            // have a valid down intersect
            }
        }
        if (wn != 0)
            return true;
        else
            return false;

    }

    private static int isLeft(LatLong P0, LatLong P1, LatLong P2)
    {
        double calc = ((P1.Lon - P0.Lon) * (P2.Lat - P0.Lat)
                - (P2.Lon - P0.Lon) * (P1.Lat - P0.Lat));
        if (calc > 0)
            return 1;
        else if (calc < 0)
            return -1;
        else
            return 0;
    }

Функция isLeft доставляла мне проблемы с округлением, и я потратил часы, не осознавая, что неправильно выполнял преобразование, так что простите мне за неудачный блок в конце этой функции.

Кстати, это оригинальный код и статья: http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

Answer 5

Я думаю, что есть более простое и эффективное решение.

Вот код на C ++. Мне должно быть просто преобразовать его в C #.

int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
  int i, j, c = 0;
  for (i = 0, j = npol-1; i < npol; j = i++) {
    if ((((yp[i] <= y) && (y < yp[j])) ||
         ((yp[j] <= y) && (y < yp[i]))) &&
        (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
      c = !c;
  }
  return c;
}

Answer 6

Наилучшее объяснение и реализацию можно найти на Включение номера обмотки точки в многоугольнике

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

Я изменил и использовал реализацию C ++, а также создал реализацию C #. Вы определенно хотите использовать алгоритм числа обмоток, поскольку он более точен, чем алгоритм пересечения ребер, и он очень быстрый.

Answer 7

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

Answer 8

Полное решение в asp.Net C #, вы можете увидеть полную информацию здесь, вы можете увидеть, как найти точку (широта, долгота), внутри или вне полигона, используя широту и долготу? Ссылка на статью Ссылка

private static bool checkPointExistsInGeofencePolygon (строка latlnglist, строка lat, строка lng) {

    List<Loc> objList = new List<Loc>();
    // sample string should be like this strlatlng = "39.11495,-76.873259|39.114588,-76.872808|39.112921,-76.870373|";
    string[] arr = latlnglist.Split('|');
    for (int i = 0; i <= arr.Length - 1; i++)
    {
        string latlng = arr[i];
        string[] arrlatlng = latlng.Split(',');

        Loc er = new Loc(Convert.ToDouble(arrlatlng[0]), Convert.ToDouble(arrlatlng[1]));
        objList.Add(er);
    }
    Loc pt = new Loc(Convert.ToDouble(lat), Convert.ToDouble(lng));

    if (IsPointInPolygon(objList, pt) == true)
    {
          return true;
    }
    else
    {
           return false;
    }
}
private static bool IsPointInPolygon(List<Loc> poly, Loc point)
{
    int i, j;
    bool c = false;
    for (i = 0, j = poly.Count - 1; i < poly.Count; j = i++)
    {
        if ((((poly[i].Lt <= point.Lt) && (point.Lt < poly[j].Lt)) |
            ((poly[j].Lt <= point.Lt) && (point.Lt < poly[i].Lt))) &&
            (point.Lg < (poly[j].Lg - poly[i].Lg) * (point.Lt - poly[i].Lt) / (poly[j].Lt - poly[i].Lt) + poly[i].Lg))
            c = !c;
    }
    return c;
}

Answer 9

Ян отвечает отлично.

Здесь тот же код, использующий класс GeoCoordinate.

using System.Device.Location;

...

public static bool IsPointInPolygon(List<GeoCoordinate> poly, GeoCoordinate point)
{
    int i, j;
    bool c = false;
    for (i = 0, j = poly.Count - 1; i < poly.Count; j = i++)
    {
        if ((((poly[i].Latitude <= point.Latitude) && (point.Latitude < poly[j].Latitude))
                || ((poly[j].Latitude <= point.Latitude) && (point.Latitude < poly[i].Latitude)))
                && (point.Longitude < (poly[j].Longitude - poly[i].Longitude) * (point.Latitude - poly[i].Latitude)
                    / (poly[j].Latitude - poly[i].Latitude) + poly[i].Longitude))
            c = !c;
    }

    return c;
}

Answer 10

Вы можете попробовать этот простой класс https://github.com/xopbatgh/sb-polygon-pointer

С этим легко справиться

1. Вы просто вставляете координаты многоугольника в массив
2. Задайте нужную библиотеку с широтой / долготой внутри многоугольника

$polygonBox = [
    [55.761515, 37.600375],
    [55.759428, 37.651156],
    [55.737112, 37.649566],
    [55.737649, 37.597301],
];

$sbPolygonEngine = new sbPolygonEngine($polygonBox);

$isCrosses = $sbPolygonEngine->isCrossesWith(55.746768, 37.625605);

// $isCrosses is boolean

(ответ был возвращен из удаленного мной, поскольку изначально он был неверно отформатирован)