algorithm - punto - como saber si una coordenada esta dentro de un poligono

¿Comprobar si una coordenada de longitud/latitud reside dentro de un polígono complejo en un dispositivo integrado?

Question

Necesito que el usuario pueda dibujar un polígono complejo en un mapa y luego hacer que la aplicación verifique si una longitud / latitud dada reside dentro de ese polígono.

Solo pude encontrar algoritmos que usaban un sistema de coordenadas cartesiano x / y simple que no compensa la curvatura de la tierra.

El usuario dibuja el polígono en una PC, donde los puntos se transfieren a través de la radio a un dispositivo integrado, que luego debe verificar si el polígono dado se encuentra dentro de su posición actual (tomado del GPS).

Como esto es para un dispositivo integrado, no puedo usar bibliotecas enormes, sino que necesito el algoritmo para realizar la comprobación por mí mismo o una biblioteca muy pequeña. Pero parece que soy incapaz de encontrar tal algoritmo.

Answer 1

Aquí hay una implementación que escribí en C # para una clase de Polígono que contiene una lista de vértices. No considera la curvatura de la tierra. En su lugar, antes de ejecutar esto, procesaría el polígono en segmentos más pequeños.

El rendimiento de este algoritmo es muy bueno. Incluso para polígonos con miles de bordes, se completa en uno o dos milisegundos en mi escritorio.

El código se ha optimizado bastante y, por lo tanto, no es tan legible como psuedo-code.

public bool Contains(GeoLocation location)
{
if (!Bounds.Contains(location))
return false;
var lastPoint = _vertices[_vertices.Length - 1];
var isInside = false;
var x = location.Longitude;
foreach (var point in _vertices)
{
var x1 = lastPoint.Longitude;
var x2 = point.Longitude;
var dx = x2 - x1;
if (Math.Abs(dx) > 180.0)
{
// we have, most likely, just jumped the dateline (could do further validation to this effect if needed). normalise the numbers.
if (x > 0)
{
while (x1 < 0)
x1 += 360;
while (x2 < 0)
x2 += 360;
}
else
{
while (x1 > 0)
x1 -= 360;
while (x2 > 0)
x2 -= 360;
}
dx = x2 - x1;
}
if ((x1 <= x && x2 > x) || (x1 >= x && x2 < x))
{
var grad = (point.Latitude - lastPoint.Latitude) / dx;
var intersectAtLat = lastPoint.Latitude + ((x - x1) * grad);
if (intersectAtLat > location.Latitude)
isInside = !isInside;
}
lastPoint = point;
}
return isInside;
}

La idea básica es encontrar todos los bordes del polígono que abarquen la posición ''x'' del punto contra el que estás probando. Luego, encuentra cuántos de ellos se intersecan con la línea vertical que se extiende por encima de tu punto. Si un número par se cruza sobre el punto, entonces estás fuera del polígono. Si un número impar cruza arriba, entonces estás dentro.

Answer 2

Buenas explicaciones y código C simple que puede convertir a sus necesidades

http://alienryderflex.com/polygon/

Combine la comprobación de polígonos con un RTree para eliminar rápidamente el árbol de búsqueda si tiene muchos polígonos que no se superponen.