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

Question

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

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

Answer 1

Просто взгляните на point-in-polygon (PIP) problem.

Answer 2

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

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

Edit: Да, что he сказал (Wikipedia):

Answer 3

Проверьте, если точка находится внутри многоугольника или нет -

Рассмотрим многоугольник, который имеет вершины a1, a2, a3 , a4, a5. Следующий набор шагов должен помочь в определении того, находится ли точка P внутри полигона или снаружи.

Вычислить векторную область треугольника, образованного ребром a1-> a2, и векторы, соединяющие a2 с P и P с a1. Аналогичным образом вычислите векторную область каждого из возможных треугольников, имеющих одну сторону, в качестве стороны многоугольника, а остальные два соединяют P с этой стороной.

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

Для того, чтобы вычислить площадь треугольника с учетом векторов, представляющих свои 3 ребра, см http://www.jtaylor1142001.net/calcjat/Solutions/VCrossProduct/VCPATriangle.htm

Answer 4

Проблема проще, если ваш многоугольник является выпуклым. Если это так, вы можете сделать простой тест для каждой строки, чтобы увидеть, находится ли точка внутри или снаружи этой линии (до бесконечности в обоих направлениях). В противном случае для вогнутых многоугольников нарисуйте воображаемый луч от вашей точки до бесконечности (в любом направлении). Укажите, сколько раз он пересекает границу. Нечетное означает, что точка внутри, даже означает, что точка находится снаружи.

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

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

Answer 5

Безусловно лучшее объяснение и внедрение можно найти на Point In Polygon Winding Number Inclusion

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

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

Answer 6

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

Интересный момент в треугольнике см link text

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

Answer 7

После поиска в Интернете и пробовать различные реализации и перенос их из 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 8

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

Вот код на 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 9

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

класс Loc

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 10

Комплексное решение в asp.Net C#, вы можете увидеть полный деталь здесь, вы можете увидеть, как найти точку (lat, lon), будь то внутри или снаружи многоугольника, используя широту и долготу? Article Reference Link

частная статическое BOOL checkPointExistsInGeofencePolygon (строка latlnglist, строка лат, строка 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 11

многоугольник определен как последовательный список пара точек А, В, С .... A . нет стороны AB, BC ...пересекает любую другую сторону

Определить окно Xmin, Xmax, Ymin, Ymax

случай 1 тест точка Р лежит вне коробки

случай 2 тест точка Р лежит внутри коробки:

Определите «диаметр» D коробки {[Xmin, Ymin] - [Xmax, Ymax]} (и добавьте немного лишнего, чтобы избежать возможной путаницы с D, находящимся сбоку)

Определите градиенты M всех сторон

Найти градиент Мт наиболее отличается от всех градиентов M

Испытание линия проходит от Р при градиентном Mt расстояние D.

Установите отсчет пересечений нулевого до

Для каждой из сторон AB, BC для пересечения PD со стороной с момента ее запуска, но НЕ ВКЛЮЧАЯ его конец. Увеличьте количество пересечений при необходимости. Отметим, что нулевое расстояние от Р до пересечения указывает на то, что P находится на стороне

Странный счетчик показывает P находится внутри многоугольника

Answer 12

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

Answer 13

Я перевел метод C# в Php, и я добавил много комментариев, чтобы понять код.

Описание PolygonПодписчики:
Проверьте, находится ли точка внутри или вне полигона. Эта процедура использует gps-координаты, и она работает, когда многоугольник имеет небольшую географическую область.


INPUT:
$ poly: массив точек: список вершин полигона; [{Point}, {Point}, ...];
$ point: точка для проверки; Точка: {"lat" => "x.xxx", "lng" => "y.yyy"}


Когда $ c ложно, число пересечений с многоугольником четное, поэтому точка находится за пределами многоугольник;
Когда $ c истинно, число пересечений с многоугольником нечетно, поэтому точка находится внутри полигона;
$ n - количество вершин в многоугольнике;
Для каждой вершины в полигоне метод вычисляет линию через текущую вершину и предыдущую вершину и проверяет, есть ли две линии точки пересечения.
$ c изменяется, когда точка пересечения существует.
Таким образом, метод может возвращать true, если точка находится внутри многоугольника, иначе возвращает false.

class PolygonHelps { 

    public static function isPointInPolygon(&$poly, $point){ 

     $c = false; 
     $n = $j = count($poly); 


     for ($i = 0, $j = $n - 1; $i < $n; $j = $i++){ 

      if (((($poly[$i]->lat <= $point->lat) && ($point->lat < $poly[$j]->lat)) 
       || (($poly[$j]->lat <= $point->lat) && ($point->lat < $poly[$i]->lat))) 

      && ($point->lng < ($poly[$j]->lng - $poly[$i]->lng) 
           * ($point->lat - $poly[$i]->lat) 
          /($poly[$j]->lat - $poly[$i]->lat) 
           + $poly[$i]->lng)){ 

       $c = !$c; 
      } 
     } 

     return $c; 
    } 
} 

Answer 14

добавить одну деталь, чтобы помочь людям, которые живут в ... к югу от земли !! Если вы находитесь в Бразилии (это мой случай), наша координация GPS - это все негативы. И все эти алго дают неправильные результаты.

Самый простой способ использовать абсолютные значения Lat и Long всей точки. И в этом случае закон Ян Коберского идеален.