Я хотел бы определить многоугольник и реализовать алгоритм, который бы проверял, находится ли точка внутри или вне многоугольника.
Кто-нибудь знает, есть ли какой-либо пример любого подобного алгоритма?
Geo Fencing - точка внутри/снаружи многоугольника
Ответ 1
Просто рассмотрите проблему проблема с точкой в полигоне (PIP).
Ответ 2
Если я правильно помню, алгоритм должен провести горизонтальную линию через тестовую точку. Подсчитайте, сколько линий полигона вы пересекаете, чтобы достичь своей точки.
Если ответ нечетный, вы внутри. Если ответ четный, вы снаружи.
Изменить: Да, что он сказал (Wikipedia):
Ответ 3
Код С#
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;
}
}
Ответ 4
После поиска в Интернете и тестирования различных реализаций и переноса их с С++ на С# я, наконец, получил свой код:
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
Ответ 5
Я думаю, что есть более простое и эффективное решение.
Вот код в С++. Я должен просто преобразовать его в С#.
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;
}
Ответ 6
Наше лучшее объяснение и реализация можно найти на Точка в включении числа обмоток полигонов
В конце хорошо объясненной статьи есть реализация С++. Этот сайт также содержит некоторые отличные алгоритмы/решения для других задач, основанных на геометрии.
Я изменил и использовал реализацию С++, а также создал реализацию С#. Вы определенно хотите использовать алгоритм Winding Number, поскольку он более точен, чем алгоритм пересечения границ, и он очень быстрый.
Ответ 7
Просто голова (используя ответ, поскольку я не могу комментировать), если вы хотите использовать point-in-polygon для гео-фехтования, вам нужно изменить свой алгоритм для работы со сферическими координатами. -180 долгота такая же, как 180 долготы, и точка-в-многоугольник будет ломаться в такой ситуации.
Ответ 8
Полное решение в asp.Net С#, вы можете увидеть здесь полную информацию, вы можете увидеть, как найти точку (lat, lon), будь то внутри или снаружи полигона, используя широту и долготу? Ссылка ссылки статьи
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;
}
Ответ 9
Проверьте, находится ли точка внутри многоугольника или нет -
Рассмотрим многоугольник, который имеет вершины a1, a2, a3, a4, a5. Следующий набор шагов должен помочь в определении того, находится ли точка P внутри полигона или снаружи.
Вычислить векторную область треугольника, образованного ребром a1- > a2, и векторы, соединяющие a2 с P и P с a1. Аналогичным образом вычислите векторную область каждого из возможных треугольников, имеющих одну сторону в качестве стороны многоугольника, а остальные два соединяют P с этой стороной.
Чтобы точка находилась внутри многоугольника, каждый из треугольников должен иметь положительную площадь. Даже если один из треугольников имеет отрицательную область, точка P выделяется из многоугольника.
Чтобы вычислить площадь треугольника, заданного вектором, представляющим его 3 ребра, обратитесь к http://www.jtaylor1142001.net/calcjat/Solutions/VCrossProduct/VCPATriangle.htm
Ответ 10
Проблема проще, если ваш многоугольник выпуклый. Если это так, вы можете сделать простой тест для каждой строки, чтобы увидеть, находится ли точка внутри или снаружи этой линии (до бесконечности в обоих направлениях). В противном случае для вогнутых многоугольников нарисуйте воображаемый луч с вашей точки до бесконечности (в любом направлении). Укажите, сколько раз он пересекает границу. Нечетное означает, что точка внутри, даже означает, что точка находится снаружи.
Этот последний алгоритм сложнее, чем кажется. Вы должны быть очень осторожны в том, что происходит, когда ваш воображаемый луч точно попадает на одну из вершин многоугольника.
Если ваш воображаемый луч идет в направлении -x, вы можете выбрать только подсчет строк, содержащих хотя бы одну точку, y-координата которой строго меньше координаты y вашей точки. Вот как вы можете работать с большинством странных краевых случаев.
Ответ 11
Если у вас есть простой полигон (ни одна из строк не пересекает), и у вас нет отверстий, вы также можете триангулировать многоугольник, который, вероятно, вы собираетесь делать в приложении GIS, чтобы нарисовать TIN, а затем проверьте точек в каждом треугольнике. Если у вас небольшое количество ребер многоугольника, но большое количество точек это быстро.
Для интересной точки в треугольнике см. текст ссылки
В противном случае определенно используйте правило обмотки, а не пересечение ребер, пересечение кромок имеет реальные проблемы с точками на краях, что, если ваши данные сгенерированы из GPS с ограниченной точностью, очень вероятно.
Ответ 12
многоугольник определяется как последовательный список пар точек A, B, C.... A. ни одна сторона A-B, B-C... не пересекает другую сторону
Определить поле Xmin, Xmax, Ymin, Ymax
случай 1 контрольная точка P находится вне поля
случай 2 контрольная точка P лежит внутри коробки:
Определите "диаметр" D окна {[Xmin, Ymin] - [Xmax, Ymax]} (и добавьте немного лишнего, чтобы избежать возможной путаницы с D на стороне)
Определите градиенты M всех сторон
Найти градиент Mt, отличный от всех градиентов M
Испытательная линия проходит от P в градиенте Mt на расстояние D.
Установите количество пересечений в ноль
Для каждой из сторон A-B, B-C тест для пересечения P-D со стороной от его запуска до, но НЕ ВКЛЮЧАЯ его конец. Увеличение количества пересечений если необходимо. Заметим, что нулевое расстояние от P до пересечения указывает, что P находится на стороне
Нечетное число указывает, что P находится внутри многоугольника
Ответ 13
Я перевел метод С# в Php, и я добавил много комментариев, чтобы понять код.
Описание PolygonHelps:
Проверьте, находится ли точка внутри или вне полигона. Эта процедура использует gps-координаты, и она работает, когда многоугольник имеет небольшую географическую область.
INPUT:
$poly: массив точек: список вершин полигона; [{Point}, {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;
}
}
Ответ 14
Я добавляю одну деталь, чтобы помочь людям, которые живут в... юге земли! Если вы находитесь в Бразилии (это мое дело), наша координация GPS - это все негативы. И все эти алго дают неправильные результаты.
Самый простой способ использовать абсолютные значения Lat и Long всей точки. И в этом случае Ян Коберский альго идеален.
Ответ 15
Ян ответ отличный.
Вот тот же код, использующий класс 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;
}
Ответ 16
Что касается ответа Коберса, я разработал его с более читаемым чистым кодом и изменил долготы, которые пересекают границу даты:
public bool IsPointInPolygon(List<PointPosition> polygon, double latitude, double longitude)
{
bool isInIntersection = false;
int actualPointIndex = 0;
int pointIndexBeforeActual = polygon.Count - 1;
var offset = calculateLonOffsetFromDateLine(polygon);
longitude = longitude < 0.0 ? longitude + offset : longitude;
foreach (var actualPointPosition in polygon)
{
var p1Lat = actualPointPosition.Latitude;
var p1Lon = actualPointPosition.Longitude;
var p0Lat = polygon[pointIndexBeforeActual].Latitude;
var p0Lon = polygon[pointIndexBeforeActual].Longitude;
if (p1Lon < 0.0) p1Lon += offset;
if (p0Lon < 0.0) p0Lon += offset;
// Jordan curve theorem - odd even rule algorithm
if (isPointLatitudeBetweenPolyLine(p0Lat, p1Lat, latitude)
&& isPointRightFromPolyLine(p0Lat, p0Lon, p1Lat, p1Lon, latitude, longitude))
{
isInIntersection = !isInIntersection;
}
pointIndexBeforeActual = actualPointIndex;
actualPointIndex++;
}
return isInIntersection;
}
private double calculateLonOffsetFromDateLine(List<PointPosition> polygon)
{
double offset = 0.0;
var maxLonPoly = polygon.Max(x => x.Longitude);
var minLonPoly = polygon.Min(x => x.Longitude);
if (Math.Abs(minLonPoly - maxLonPoly) > 180)
{
offset = 360.0;
}
return offset;
}
private bool isPointLatitudeBetweenPolyLine(double polyLinePoint1Lat, double polyLinePoint2Lat, double poiLat)
{
return polyLinePoint2Lat <= poiLat && poiLat < polyLinePoint1Lat || polyLinePoint1Lat <= poiLat && poiLat < polyLinePoint2Lat;
}
private bool isPointRightFromPolyLine(double polyLinePoint1Lat, double polyLinePoint1Lon, double polyLinePoint2Lat, double polyLinePoint2Lon, double poiLat, double poiLon)
{
// lon <(lon1-lon2)*(latp-lat2)/(lat1-lat2)+lon2
return poiLon < (polyLinePoint1Lon - polyLinePoint2Lon) * (poiLat - polyLinePoint2Lat) / (polyLinePoint1Lat - polyLinePoint2Lat) + polyLinePoint2Lon;
}
Ответ 17
Вы можете попробовать этот простой класс https://github.com/xopbatgh/sb-polygon-pointer
С этим легко справиться
- Вы просто вставляете координаты многоangularьника в массив
- Задать в библиотеке нужную точку с широтой/долготой внутри многоangularьника
$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
(ответ был возвращен из удаленного мной, поскольку изначально он был неверно отформатирован)