Geo Fencing – punto dentro / fuera del polígono

Me gustaría determinar un polígono e implementar un algoritmo que compruebe si un punto está dentro o fuera del polígono.

¿Alguien sabe si hay algún ejemplo disponible de algún algoritmo similar?

Solo eche un vistazo al problema del punto en el polígono (PIP) .

Si mal no recuerdo, el algoritmo es dibujar una línea horizontal a través de su punto de prueba. Cuenta cuántas líneas del polígono intersectas para llegar a tu punto.

Si la respuesta es impar, estás adentro. Si la respuesta es pareja, estás afuera.

Editar: Sí, lo que dijo ( Wikipedia ):

texto alternativo

C # code

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

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

Después de buscar en la web y probar varias implementaciones y portarlas de C ++ a C # finalmente obtuve mi código:

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

La función isLeft me estaba dando problemas de redondeo y pasé horas sin darme cuenta de que estaba haciendo una conversión incorrecta, así que perdónenme por el cojo si bloquean al final de esa función.

Por cierto, este es el código y el artículo originales: http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

Creo que hay una solución más simple y más eficiente.

Aquí está el código en C ++. Debería ser simple convertirlo a 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; } 

Con mucho, la mejor explicación e implementación se puede encontrar en Point In Polygon Winding Number Inclusion

Incluso hay una implementación de C ++ al final del artículo bien explicado. Este sitio también contiene algunos algoritmos / soluciones geniales para otros problemas basados ​​en la geometría.

Modifiqué y usé la implementación de C ++ y también creé una implementación de C #. Definitivamente desea utilizar el algoritmo de número de cuerda ya que es más preciso que el algoritmo de cruce de bordes y es muy rápido.

Solo un aviso (usando la respuesta ya que no puedo hacer ningún comentario), si quiere usar el punto en el polígono para geoespaño, entonces necesita cambiar su algoritmo para trabajar con coordenadas esféricas. -180 de longitud es igual a 180 de longitud y punto-en-polígono se romperá en tal situación.

La solución completa en asp.Net C #, puede ver el detalle completo aquí, puede ver cómo encontrar el punto (lat, lon) ya sea dentro o fuera del polígono usando la latitud y las longitudes? Enlace de referencia del artículo

private static bool checkPointExistsInGeofencePolygon (string latlnglist, string lat, string 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; } 

Compruebe si un punto está dentro de un polígono o no –

Considere el polígono que tiene los vértices a1, a2, a3, a4, a5. El siguiente conjunto de pasos debería ayudar a determinar si el punto P se encuentra dentro del polígono o afuera.

Calcule el área vectorial del triángulo formado por el borde a1-> a2 y los vectores que conectan a2 con P y P con a1. De manera similar, calcule el área del vector de cada uno de los triangularjs posibles que tienen un lado como el lado del polígono y los otros dos que conectan a ese lado.

Para que un punto esté dentro de un polígono, cada uno de los triangularjs debe tener un área positiva. Incluso si uno de los triangularjs tiene un área negativa, entonces el punto P sobresale del polígono.

Para calcular el área de un triángulo dado vectores que representan sus 3 aristas, consulte http://www.jtaylor1142001.net/calcjat/Solutions/VCrossProduct/VCPATriangle.htm

El problema es más fácil si tu polígono es convexo. Si es así, puede hacer una prueba simple para cada línea para ver si el punto está dentro o fuera de esa línea (se extiende hasta el infinito en ambas direcciones). De lo contrario, para polígonos cóncavos, dibuja un rayo imaginario desde tu punto hacia fuera hasta el infinito (en cualquier dirección). Cuenta cuántas veces cruza una línea límite. Impar significa que el punto está adentro, incluso significa que el punto está afuera.

Este último algoritmo es más complicado de lo que parece. Tendrás que tener mucho cuidado con lo que sucede cuando tu rayo imaginario golpea exactamente uno de los vértices del polígono.

Si su rayo imaginario va en la dirección -x, puede elegir solo contar líneas que incluyan al menos un punto cuya coordenada y sea estrictamente menor que la coordenada y de su punto. Así es como logras que la mayoría de los casos de bordes extraños funcionen correctamente.

Si tienes un polígono simple (ninguna de las líneas se cruza) y no tienes agujeros, también puedes triangular el polígono, lo que probablemente harás de todos modos en una aplicación GIS para dibujar un TIN, luego, prueba los puntos en cada uno triángulo. Si tiene una pequeña cantidad de bordes en el polígono pero una gran cantidad de puntos, esto es rápido.

Para un punto interesante en triángulo, vea el texto del enlace

De lo contrario, definitivamente use la regla de bobinado en lugar de cruzar el borde, el cruce del borde tiene problemas reales con los puntos en los bordes, que si sus datos se generan desde un GPS con una precisión limitada es muy probable.

el polígono se define como una lista secuencial de pares de puntos A, B, C …. A. ningún lado AB, BC … cruza cualquier otro lado

Determine la caja Xmin, Xmax, Ymin, Ymax

caso 1, el punto de prueba P se encuentra fuera de la caja

caso 2, el punto de prueba P se encuentra dentro de la caja:

Determina el ‘diámetro’ D de la caja {[Xmin, Ymin] – [Xmax, Ymax]} (y agrega un poco más para evitar posibles confusiones con D estando de costado)

Determine los gradientes M de todos los lados

Encuentra un gradiente Mt más diferente de todos los gradientes M

La línea de prueba se extiende desde P al gradiente Mt a distancia D.

Establezca el recuento de intersecciones en cero

Para cada uno de los lados AB, BC prueba la intersección de PD con un lado desde su inicio hasta NO INCLUYENDO su extremo. Incremente el recuento de intersecciones si es necesario. Tenga en cuenta que una distancia cero desde P a la intersección indica que P está EN UN lado

Un recuento impar indica que P está dentro del polígono

Traducí el método de c # en Php y agregué muchos comentarios para entender el código.

Descripción de PolygonHelps:
Verifica si un punto está dentro o fuera de un polígono. Este procedimiento utiliza coordenadas gps y funciona cuando el polígono tiene un área geográfica pequeña.

ENTRADA:
$ poly: array de Point: polígono vértices lista; [{Point}, {Point}, …];
$ punto: señalar para verificar; Punto: {“lat” => “x.xxx”, “lng” => “y.yyy”}

Cuando $ c es falso, el número de intersecciones con el polígono es par, por lo que el punto está fuera del polígono;
Cuando $ c es verdadero, el número de intersecciones con el polígono es impar, por lo que el punto está dentro del polígono;
$ n es la cantidad de vértices en el polígono;
Para cada vértice en el polígono, el método calcula la línea a través del vértice actual y el vértice anterior y comprueba si las dos líneas tienen un punto de intersección.
$ c cambia cuando existe punto de intersección.
Entonces, el método puede devolver verdadero si el punto está dentro del polígono, de lo contrario devuelve falso.

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

Agrego un detalle para ayudar a las personas que viven en … ¡al sur de la tierra! Si estás en Brasil (ese es mi caso), nuestras coord GPS son todas negativas. Y todos estos algo dan resultados incorrectos.

La forma más fácil es usar los valores absolutos de Lat y Long de todos los puntos. Y en ese caso, el algo de Jan Kobersky es perfecto.