algorithm - applications - Esgrima Geo-punto dentro/fuera del polígono
"computational geometry an introduction" (14)
¡Agrego un detalle para ayudar a las personas que viven en el ... sur de la Tierra! Si estás en Brasil (ese es mi caso), nuestra coordenada de GPS son todas negativas. Y todos estos algo dan resultados equivocados.
La forma más fácil si se utilizan los valores absolutos de Lat y Long de todos los puntos. Y en ese caso, algo de Jan Kobersky es perfecto.
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?
Compruebe si un punto está dentro de un polígono o no.
Considera el polígono que tiene vértices a1, a2, a3, a4, a5. El siguiente conjunto de pasos debería ayudar a determinar si el punto P está dentro o fuera del polígono.
Calcule el área vectorial del triángulo formado por el borde a1-> a2 y los vectores que conectan a2 a P y P a a1. De manera similar, calcule el área vectorial de cada uno de los triángulos posibles que tienen un lado como el lado del polígono y los otros dos P que se conectan a ese lado.
Para que un punto esté dentro de un polígono, cada uno de los triángulos debe tener un área positiva. Incluso si uno de los triángulos tiene un área negativa, entonces el punto P sobresale del polígono.
Para calcular el área de un triángulo, los vectores dados representan sus 3 bordes, consulte http://www.jtaylor1142001.net/calcjat/Solutions/VCrossProduct/VCPATriangle.htm
Con mucho, la mejor explicación e implementación se puede encontrar en Punto en Polígono Inclusión de números de liquidación
Incluso hay una implementación de C ++ al final del artículo bien explicado. Este sitio también contiene algunos algoritmos / soluciones excelentes para otros problemas basados en geometría.
He modificado y usado la implementación de C ++ y también he creado una implementación de C #. Definitivamente desea utilizar el algoritmo de Número de Bobina ya que es más preciso que el algoritmo de cruce de borde y es muy rápido.
Creo que hay una solución más sencilla y 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;
}
Después de buscar en la web y probar varias implementaciones y trasladarlas de C ++ a C #, finalmente obtuve mi código correcto:
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;
}
La función isLeft me estaba dando problemas de redondeo y pasé horas sin darme cuenta de que estaba haciendo la conversión incorrectamente, así que perdóname por el bloque de cojo al final de esa función.
Por cierto, este es el código y el artículo original: http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.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 (extendiéndose hasta el infinito en ambas direcciones). De lo contrario, para polígonos cóncavos, dibuje un rayo imaginario desde su punto al infinito (en cualquier dirección). Cuenta cuántas veces cruza una línea de límite. Impar significa que el punto está dentro, incluso significa que está fuera.
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 toque exactamente uno de los vértices del polígono.
Si su rayo imaginario va en la dirección -x, puede elegir solo contar las líneas que incluyen al menos un punto cuya coordenada y sea estrictamente menor que la coordenada y de su punto. Así es como consigues que la mayoría de los casos de borde extraño funcionen correctamente.
La solución completa en asp.Net C #, puede ver el detalle completo aquí, puede ver cómo encontrar el punto (lat, lon) si está dentro o fuera del polígono utilizando la latitud y las longitudes. Enlace de referencia del artículo
private static bool checkPointExistsInGeofencePolygon (string latlnglist, string lat, string 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;
}
Si tiene un polígono simple (ninguna de las líneas se cruza) y no tiene orificios, también puede triangular el polígono, lo que probablemente va a hacer de todos modos en una aplicación GIS para dibujar un TIN y luego probar los puntos en cada triángulo. Si tiene un pequeño número de bordes en el polígono pero un gran número de puntos, esto es rápido.
Para un punto interesante en triángulo ver el texto del enlace
De lo contrario, definitivamente use la regla de enrollamiento en lugar del cruce de bordes, el cruce de bordes tiene problemas reales con los puntos en los bordes, lo cual es muy probable que si sus datos se generan desde un GPS con precisión limitada.
Solo eche un vistazo al problema de punto en polígono (PIP) .
Solo un aviso (usando la respuesta como no puedo comentar), si desea usar el punto en polígono para cercas geográficas, necesita cambiar su algoritmo para trabajar con coordenadas esféricas. La longitud -180 es la misma que la longitud 180 y el punto en el polígono se romperá en tal situación.
Traduje el método c # en PHP y agregué muchos comentarios para entender el código.
Descripción de PolygonHelps:
Compruebe 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: matriz de puntos: lista de vértices de polígonos; [{Punto}, {Punto}, ...];
$ punto: punto a 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 el número de vértices en el polígono;
Para cada vértice en polígono, el método calcula la línea a través del vértice actual y el vértice anterior y verifica si las dos líneas tienen un punto de intersección.
$ c cambia cuando existe un 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;
}
}
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:
Determine el ''diámetro'' D de la casilla {[Xmin, Ymin] - [Xmax, Ymax]} (y agregue un poco más para evitar posibles confusiones con D en un lado)
Determinar los gradientes M de todos los lados.
Encuentra un gradiente Mt más diferente de todos los gradientes M
La línea de prueba va desde P a gradiente Mt a distancia D.
Establecer el recuento de intersecciones a cero
Para cada uno de los lados AB, BC prueba la intersección de PD con un lado desde su inicio hasta pero NO INCLUYE su final. Incrementa el recuento de intersecciones si es necesario. Tenga en cuenta que una distancia cero de P a la intersección indica que P está en un lado ON
Una cuenta impar indica que P está dentro del polígono
Código 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;
}
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;
}
}