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

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

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

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

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

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

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

alt text

Код C #

bool IsPointInPolygon(List 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; } 

Локальный class

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

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

  public static bool PointInPolygon(LatLong p, List 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 <= Py 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 > Py (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

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

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

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

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

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

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

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

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

  List objList = new List(); // 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 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; } 

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

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

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

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

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

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

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

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

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

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

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

многоугольник определяется как последовательный список пар точек A, B, C …. A. ни одна сторона AB, BC … не пересекает любую другую сторону

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

случае 1 контрольная точка P лежит вне коробки

случае 2 контрольная точка P лежит внутри коробки:

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

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

Найти gradleиент Mt, отличный от всех gradleиентов M

Испытательная линия проходит от P в gradleиенте Mt на расстояние D.

Установите количество пересечений в ноль

Для каждой из сторон AB, BC тест для пересечения PD со стороной от ее запуска до NOT, ВКЛЮЧАЯ ее конец. При необходимости увеличивайте количество пересечений. Заметим, что нулевое расстояние от P до пересечения указывает, что P находится на стороне

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

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

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

ВХОД:
$ poly: массив списка точек Point: polygon vertices; [{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; } } 

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

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

Давайте будем гением компьютера.