math - paises - mapa con coordenadas geográficas

Detectando si una coordenada GPS cae dentro de un polígono en un mapa

Question

Como se indica en el título, el objetivo es tener una forma de detectar si una determinada coordenada de GPS cae dentro de un polígono o no.

El polígono en sí puede ser convexo o cóncavo. Se define como un conjunto de vectores de borde y un punto conocido dentro de ese polígono. Cada vector de borde está definido además por cuatro coordenadas que son las latitudes y longitudes de los puntos de punta respectivos y un rumbo relativo al punto de inicio.

Hay un par de preguntas similares a esta aquí en StackOverflow pero describen la solución solo en términos generales y para un plano 2D, mientras que estoy buscando una implementación existente que admita los polígonos definidos por pares de latitud / longitud en WGS 84 .

¿Qué API-s o servicios existen para realizar tales pruebas de colisión?

Answer 1

Aquí está el algoritmo escrito en Ir: Toma coordenadas de puntos en formato [lat, long] y polígono en formato [[lat, long], [lat, long] ...]. Algoritmo se unirá al primer y último punto en la porción de polígono

import "math"

// ContainsLocation determines whether the point is inside the polygon
func ContainsLocation(point []float64, polygon [][]float64, geodesic 
   bool) bool {
    size := len(polygon)
    if size == 0 {
        return false
    }

    var (
        lat2, lng2, dLng3 float64
    )

    lat3 := toRadians(point[0])
    lng3 := toRadians(point[1])
    prev := polygon[size-1]
    lat1 := toRadians(prev[0])
    lng1 := toRadians(prev[1])
    nIntersect := 0

    for _, v := range polygon {
        dLng3 = wrap(lng3-lng1, -math.Pi, math.Pi)
        // Special case: point equal to vertex is inside.
        if lat3 == lat1 && dLng3 == 0 {
            return true
        }
        lat2 = toRadians(v[0])
        lng2 = toRadians(v[1])
        // Offset longitudes by -lng1.
        if intersects(lat1, lat2, wrap(lng2-lng1, -math.Pi, math.Pi), lat3, dLng3, geodesic) {
            nIntersect++
        }
        lat1 = lat2
        lng1 = lng2
    }

    return (nIntersect & 1) != 0
}

func toRadians(p float64) float64 {
    return p * (math.Pi / 180.0)
}

func wrap(n, min, max float64) float64 {
    if n >= min && n < max {
        return n
    }
    return mod(n-min, max-min) + min
}

func mod(x, m float64) float64 {
    return math.Remainder(math.Remainder(x, m)+m, m)
}

func intersects(lat1, lat2, lng2, lat3, lng3 float64, geodesic bool) bool {
    // Both ends on the same side of lng3.
    if (lng3 >= 0 && lng3 >= lng2) || (lng3 < 0 && lng3 < lng2) {
        return false
    }
    // Point is South Pole.
    if lat3 <= -math.Pi/2 {
        return false
    }
    // Any segment end is a pole.
    if lat1 <= -math.Pi/2 || lat2 <= -math.Pi/2 || lat1 >= math.Pi/2 || lat2 >= math.Pi/2 {
        return false
    }
    if lng2 <= -math.Pi {
        return false
    }
    linearLat := (lat1*(lng2-lng3) + lat2*lng3) / lng2
    // Northern hemisphere and point under lat-lng line.
    if lat1 >= 0 && lat2 >= 0 && lat3 < linearLat {
        return false
    }
    // Southern hemisphere and point above lat-lng line.
    if lat1 <= 0 && lat2 <= 0 && lat3 >= linearLat {
        return true
    }
    // North Pole.
    if lat3 >= math.Pi/2 {
        return true
    }

    // Compare lat3 with latitude on the GC/Rhumb segment corresponding to lng3.
    // Compare through a strictly-increasing function (tan() or mercator()) as convenient.
    if geodesic {
        return math.Tan(lat3) >= tanLatGC(lat1, lat2, lng2, lng3)
    }
    return mercator(lat3) >= mercatorLatRhumb(lat1, lat2, lng2, lng3)
}

func tanLatGC(lat1, lat2, lng2, lng3 float64) float64 {
    return (math.Tan(lat1)*math.Sin(lng2-lng3) + math.Tan(lat2)*math.Sin(lng3)) / math.Sin(lng2)
}

func mercator(lat float64) float64 {
    return math.Log(math.Tan(lat*0.5 + math.Pi/4))
}

func mercatorLatRhumb(lat1, lat2, lng2, lng3 float64) float64 {
    return (mercator(lat1)*(lng2-lng3) + mercator(lat2)*lng3) / lng2
}

Answer 2

Código Runner.Java en VB.NET

Para el beneficio de los usuarios de .NET, el mismo código se coloca en VB.NET. Lo he intentado y es bastante rápido. Probado con 350000 registros, termina en solo unos minutos. Pero como dijo el autor, todavía tengo que probar los escenarios que se cruzan con el ecuador, multizones, etc.

''Uso

If coordinate_is_inside_polygon(CurLat, CurLong, Lat_Array, Long_Array) Then
    MsgBox("Location " & CurLat & "," & CurLong & " is within polygon boundary")
Else
    MsgBox("Location " & CurLat & "," & CurLong & " is NOT within polygon boundary")
End If

''Funciones

Public Function coordinate_is_inside_polygon(ByVal latitude As Double, ByVal longitude As Double, ByVal lat_array() As Double, ByVal long_array() As Double) As Boolean
    Dim i As Integer
    Dim angle As Double = 0
    Dim point1_lat As Double
    Dim point1_long As Double
    Dim point2_lat As Double
    Dim point2_long As Double
    Dim n As Integer = lat_array.Length()
    For i = 0 To n - 1
        point1_lat = lat_array(i) - latitude
        point1_long = long_array(i) - longitude
        point2_lat = lat_array((i + 1) Mod n) - latitude
        point2_long = long_array((i + 1) Mod n) - longitude
        angle += Angle2D(point1_lat, point1_long, point2_lat, point2_long)
    Next

    If Math.Abs(angle) < PI Then Return False Else Return True
End Function

Public Function Angle2D(ByVal y1 As Double, ByVal x1 As Double, ByVal y2 As Double, ByVal x2 As Double) As Double
    Dim dtheta, theta1, theta2 As Double
    theta1 = Math.Atan2(y1, x1)
    theta2 = Math.Atan2(y2, x2)
    dtheta = theta2 - theta1
    While dtheta > PI
         dtheta -= TWOPI
    End While

    While dtheta < -PI
        dtheta += TWOPI
    End While
    Return (dtheta)
End Function



 Public Function is_valid_gps_coordinate(ByVal latitude As Double, ByVal longitude As Double) As Boolean
        If latitude > -90 AndAlso latitude < 90 AndAlso longitude > -180 AndAlso longitude < 180 Then
            Return True
        End If

        Return False
End Function

Answer 3

Desde la memoria, la forma de determinar si un punto se encuentra dentro de un polígono es imaginar dibujar una línea desde la posición hasta un punto lejano. Luego cuenta el número de intersecciones entre la línea y los segmentos de línea del polígono. Si el conteo es par, entonces no se encuentra dentro del polígono. Si es falso, entonces está dentro del polígono.

Answer 4

Pensé de manera similar como shab primero (su propuesta se llama Algoritmo de Ray-Casting ), pero tenía dudas como Spacedman:

... pero toda la geometría tendrá que volver a hacerse en coordenadas esféricas ...

Implementé y probé la forma matemáticamente correcta de hacerlo, ei intersectando grandes círculos y determinando si uno de los dos puntos de intersección está en ambos arcos. (Nota: seguí los pasos descritos here , pero encontré varios errores: la función de sign falta al final del paso 6 (justo antes de arcsin ), y la prueba final es basura numérica (ya que la resta está mal condicionada); L_1T >= max(L_1a, L_1b) para comprobar si S1 está en el primer arco, etc.)

Eso también es extremadamente lento y una pesadilla numérica (evalúa ~ 100 funciones trigonométricas, entre otras cosas); demostró no ser utilizable en nuestros sistemas integrados.

Sin embargo, hay un truco : si el área que está considerando es lo suficientemente pequeña, simplemente haga una proyección cartográfica estándar, por ejemplo, la proyección esférica de Mercator , de cada punto:

// latitude, longitude in radians
x = longitude;
y = log(tan(pi/4 + latitude/2));

Luego, puede aplicar el lanzamiento de rayos, donde la intersección de arcos se comprueba con esta función:

public bool ArcsIntersecting(double x1, double y1, double x2, double y2, 
  double x3, double y3, double x4, double y4)
    {

    double vx1 = x2 - x1;
    double vy1 = y2 - y1;

    double vx2 = x4 - x3;
    double vy2 = y4 - y3;

    double denom = vx1 * vy2 - vx2 * vy1;

    if (denom == 0) { return false; } // edges are parallel

    double t1 = (vx2 * (y1 - y3) - vy2 * (x1 - x3)) / denom;

    double t2;

    if (vx2 != 0) { t2 = (x1 - x3 + t1 * vx1) / vx2; }
    else if (vy2 != 0) { t2 = (y1 - y3 + t1 * vy1) / vy2; }
    else { return false; } // edges are matching

    return min(t1, t2) >= 0 && max(t1, t2) <= 1;
}

Answer 5

Si tiene coordenadas WGS84 en la esfera, entonces su polígono divide la esfera en dos áreas: ¿cómo sabemos qué área está ''dentro'' y cuál está ''fuera'' del polígono? ¡La pregunta es esencialmente sin sentido!

Por ejemplo, supongamos que el polígono formó la línea del ecuador: ¿está el hemisferio norte "dentro" o "afuera"?

Answer 6

Suponiendo que maneje el caso de envolver alrededor del meridiano y cruzar el ecuador (agregando compensaciones), ¿no puede simplemente tratar esto como un simple punto 2d en el polígono?

Answer 7

Aquí hay un programa Java que usa una función que devolverá verdadero si se encuentra una latitud / longitud dentro de un polígono definido por una lista de lat / longs, con una demostración para el estado de florida.

No estoy seguro de si se trata del hecho de que el sistema lat / long GPS no es un plano de coordenadas x / y. Para mis usos, he demostrado que funciona (creo que si especifica suficientes puntos en el cuadro delimitador, borra el efecto de que la tierra es una esfera, y que las líneas rectas entre dos puntos de la tierra no son una flecha en línea recta .

Primero, especifique los puntos que forman los puntos de esquina del polígono, puede tener esquinas cóncavas y convexas. Las coordenadas que uso a continuación rastrean el perímetro del estado de Florida.

El método coordinate_is_inside_polygon utiliza un algoritmo que no entiendo del todo. Aquí hay una explicación oficial de la fuente donde la obtuve:

"... la solución enviada por Philippe Reverdy es calcular la suma de los ángulos formados entre el punto de prueba y cada par de puntos que forman el polígono. Si esta suma es 2pi, el punto es un punto interior, si 0 es el punto es un punto exterior. Esto también funciona para polígonos con orificios dado que el polígono se define con una trayectoria formada por bordes coincidentes dentro y fuera del orificio, como es una práctica común en muchos paquetes de CAD ".

Las pruebas de mi unidad muestran que funciona de manera confiable, incluso cuando el cuadro delimitador tiene forma de "C" o incluso tiene forma de Torus . (Mis pruebas unitarias prueban muchos puntos dentro de Florida y me aseguran de que la función se vuelva verdadera. Y escojo una serie de coordenadas en cualquier otro lugar del mundo y me aseguro de que devuelva falso. Escogí lugares en todo el mundo que podrían confundirlo.

No estoy seguro de que esto funcione si el cuadro delimitador de polígonos cruza el ecuador, el primer meridiano o cualquier área donde las coordenadas cambien de -180 -> 180, -90 -> 90. O su polígono se enrolla alrededor de la tierra alrededor del norte / polos sur. Para mí, solo necesito que trabaje para el perímetro de Florida. Si tiene que definir un polígono que atraviesa la tierra o cruza estas líneas, puede trabajar alrededor de él haciendo dos polígonos, uno que represente el área en un lado del meridiano y otro que represente el área en el otro lado y pruebe si su punto está en cualquiera de esos puntos.

Aquí es donde encontré este algoritmo: Determinar si un punto se encuentra en el interior de un polígono - Solución 2

Ejecútelo usted mismo para verificarlo dos veces.

Pon esto en un archivo llamado Runner.java

import java.util.ArrayList;
public class Runner
{
    public static double PI = 3.14159265;
    public static double TWOPI = 2*PI;
    public static void main(String[] args) {
    ArrayList<Double> lat_array = new ArrayList<Double>();
    ArrayList<Double> long_array = new ArrayList<Double>();

    //This is the polygon bounding box, if you plot it, 
    //you''ll notice it is a rough tracing of the parameter of 
    //the state of Florida starting at the upper left, moving 
    //clockwise, and finishing at the upper left corner of florida.

    ArrayList<String> polygon_lat_long_pairs = new ArrayList<String>();
    polygon_lat_long_pairs.add("31.000213,-87.584839");  
    //lat/long of upper left tip of florida.
    polygon_lat_long_pairs.add("31.009629,-85.003052");
    polygon_lat_long_pairs.add("30.726726,-84.838257");
    polygon_lat_long_pairs.add("30.584962,-82.168579");
    polygon_lat_long_pairs.add("30.73617,-81.476441");  
    //lat/long of upper right tip of florida.
    polygon_lat_long_pairs.add("29.002375,-80.795288");
    polygon_lat_long_pairs.add("26.896598,-79.938355");
    polygon_lat_long_pairs.add("25.813738,-80.059204");
    polygon_lat_long_pairs.add("24.93028,-80.454712");
    polygon_lat_long_pairs.add("24.401135,-81.817017");
    polygon_lat_long_pairs.add("24.700927,-81.959839");
    polygon_lat_long_pairs.add("24.950203,-81.124878");
    polygon_lat_long_pairs.add("26.0015,-82.014771");
    polygon_lat_long_pairs.add("27.833247,-83.014527");
    polygon_lat_long_pairs.add("28.8389,-82.871704");
    polygon_lat_long_pairs.add("29.987293,-84.091187");
    polygon_lat_long_pairs.add("29.539053,-85.134888");
    polygon_lat_long_pairs.add("30.272352,-86.47522");
    polygon_lat_long_pairs.add("30.281839,-87.628784");

    //Convert the strings to doubles.       
    for(String s : polygon_lat_long_pairs){
        lat_array.add(Double.parseDouble(s.split(",")[0]));
        long_array.add(Double.parseDouble(s.split(",")[1]));
    }

   //prints TRUE true because the lat/long passed in is
    //inside the bounding box.
    System.out.println(coordinate_is_inside_polygon(
            25.7814014D,-80.186969D,
            lat_array, long_array));

    //prints FALSE because the lat/long passed in 
    //is Not inside the bounding box.
    System.out.println(coordinate_is_inside_polygon(
            25.831538D,-1.069338D, 
            lat_array, long_array));

}
public static boolean coordinate_is_inside_polygon(
    double latitude, double longitude, 
    ArrayList<Double> lat_array, ArrayList<Double> long_array)
{       
       int i;
       double angle=0;
       double point1_lat;
       double point1_long;
       double point2_lat;
       double point2_long;
       int n = lat_array.size();

       for (i=0;i<n;i++) {
          point1_lat = lat_array.get(i) - latitude;
          point1_long = long_array.get(i) - longitude;
          point2_lat = lat_array.get((i+1)%n) - latitude; 
          //you should have paid more attention in high school geometry.
          point2_long = long_array.get((i+1)%n) - longitude;
          angle += Angle2D(point1_lat,point1_long,point2_lat,point2_long);
       }

       if (Math.abs(angle) < PI)
          return false;
       else
          return true;
}

public static double Angle2D(double y1, double x1, double y2, double x2)
{
   double dtheta,theta1,theta2;

   theta1 = Math.atan2(y1,x1);
   theta2 = Math.atan2(y2,x2);
   dtheta = theta2 - theta1;
   while (dtheta > PI)
      dtheta -= TWOPI;
   while (dtheta < -PI)
      dtheta += TWOPI;

   return(dtheta);
}

public static boolean is_valid_gps_coordinate(double latitude, 
    double longitude)
{
    //This is a bonus function, it''s unused, to reject invalid lat/longs.
    if (latitude > -90 && latitude < 90 && 
            longitude > -180 && longitude < 180)
    {
        return true;
    }
    return false;
}
}

La magia demoníaca necesita ser probada por unidades. Pon esto en un archivo llamado MainTest.java para verificar que funcione para ti

import java.util.ArrayList;
import org.junit.Test;
import static org.junit.Assert.*;

public class MainTest {
@Test
public void test_lat_long_in_bounds(){
    Runner r = new Runner();
    //These make sure the lat/long passed in is a valid gps 
    //lat/long coordinate.  These should be valid. 
    assertTrue(r.is_valid_gps_coordinate(25, -82));
    assertTrue(r.is_valid_gps_coordinate(-25, -82));
    assertTrue(r.is_valid_gps_coordinate(25, 82));
    assertTrue(r.is_valid_gps_coordinate(-25, 82));
    assertTrue(r.is_valid_gps_coordinate(0, 0));
    assertTrue(r.is_valid_gps_coordinate(89, 179));
    assertTrue(r.is_valid_gps_coordinate(-89, -179));
    assertTrue(r.is_valid_gps_coordinate(89.999, 179));
    //If your bounding box crosses the equator or prime meridian, 
    then you have to test for those situations still work.
}
@Test
public void realTest_for_points_inside()
{
    ArrayList<Double> lat_array = new ArrayList<Double>();
    ArrayList<Double> long_array = new ArrayList<Double>();
    ArrayList<String> polygon_lat_long_pairs = new ArrayList<String>();
    //upper left tip of florida.
    polygon_lat_long_pairs.add("31.000213,-87.584839");
    polygon_lat_long_pairs.add("31.009629,-85.003052");
    polygon_lat_long_pairs.add("30.726726,-84.838257");
    polygon_lat_long_pairs.add("30.584962,-82.168579");
    polygon_lat_long_pairs.add("30.73617,-81.476441");  
    //upper right tip of florida.
    polygon_lat_long_pairs.add("29.002375,-80.795288");
    polygon_lat_long_pairs.add("26.896598,-79.938355");
    polygon_lat_long_pairs.add("25.813738,-80.059204");
    polygon_lat_long_pairs.add("24.93028,-80.454712");
    polygon_lat_long_pairs.add("24.401135,-81.817017");
    polygon_lat_long_pairs.add("24.700927,-81.959839");
    polygon_lat_long_pairs.add("24.950203,-81.124878");
    polygon_lat_long_pairs.add("26.0015,-82.014771");
    polygon_lat_long_pairs.add("27.833247,-83.014527");
    polygon_lat_long_pairs.add("28.8389,-82.871704");
    polygon_lat_long_pairs.add("29.987293,-84.091187");
    polygon_lat_long_pairs.add("29.539053,-85.134888");
    polygon_lat_long_pairs.add("30.272352,-86.47522");
    polygon_lat_long_pairs.add("30.281839,-87.628784");

    for(String s : polygon_lat_long_pairs){
        lat_array.add(Double.parseDouble(s.split(",")[0]));
        long_array.add(Double.parseDouble(s.split(",")[1]));
    }

    Runner r = new Runner();
    ArrayList<String> pointsInside = new ArrayList<String>();
    pointsInside.add("30.82112,-87.255249");
    pointsInside.add("30.499804,-86.8927");
    pointsInside.add("29.96826,-85.036011");
    pointsInside.add("30.490338,-83.981323");
    pointsInside.add("29.825395,-83.344116");
    pointsInside.add("30.215406,-81.828003");
    pointsInside.add("29.299813,-82.728882");
    pointsInside.add("28.540135,-81.212769");
    pointsInside.add("27.92065,-82.619019");
    pointsInside.add("28.143691,-81.740113");
    pointsInside.add("27.473186,-80.718384");
    pointsInside.add("26.769154,-81.729126");
    pointsInside.add("25.853292,-80.223999");
    pointsInside.add("25.278477,-80.707398");
    pointsInside.add("24.571105,-81.762085");   //bottom tip of keywest
    pointsInside.add("24.900388,-80.663452");
    pointsInside.add("24.680963,-81.366577");

    for(String s : pointsInside)
    {
        assertTrue(r.coordinate_is_inside_polygon(
            Double.parseDouble(s.split(",")[0]), 
            Double.parseDouble(s.split(",")[1]), 
            lat_array, long_array));
    }
}

@Test
public void realTest_for_points_outside()
{
    ArrayList<Double> lat_array = new ArrayList<Double>();
    ArrayList<Double> long_array = new ArrayList<Double>();

    ArrayList<String> polygon_lat_long_pairs = new ArrayList<String>();
    //upper left tip, florida.
    polygon_lat_long_pairs.add("31.000213,-87.584839");
    polygon_lat_long_pairs.add("31.009629,-85.003052");
    polygon_lat_long_pairs.add("30.726726,-84.838257");
    polygon_lat_long_pairs.add("30.584962,-82.168579");
    polygon_lat_long_pairs.add("30.73617,-81.476441");
    //upper right tip, florida.
    polygon_lat_long_pairs.add("29.002375,-80.795288");
    polygon_lat_long_pairs.add("26.896598,-79.938355");
    polygon_lat_long_pairs.add("25.813738,-80.059204");
    polygon_lat_long_pairs.add("24.93028,-80.454712");
    polygon_lat_long_pairs.add("24.401135,-81.817017");
    polygon_lat_long_pairs.add("24.700927,-81.959839");
    polygon_lat_long_pairs.add("24.950203,-81.124878");
    polygon_lat_long_pairs.add("26.0015,-82.014771");
    polygon_lat_long_pairs.add("27.833247,-83.014527");
    polygon_lat_long_pairs.add("28.8389,-82.871704");
    polygon_lat_long_pairs.add("29.987293,-84.091187");
    polygon_lat_long_pairs.add("29.539053,-85.134888");
    polygon_lat_long_pairs.add("30.272352,-86.47522");
    polygon_lat_long_pairs.add("30.281839,-87.628784");

    for(String s : polygon_lat_long_pairs)
    {
        lat_array.add(Double.parseDouble(s.split(",")[0]));
        long_array.add(Double.parseDouble(s.split(",")[1]));
    }

    Runner r = new Runner();

    ArrayList<String> pointsOutside = new ArrayList<String>();
    pointsOutside.add("31.451159,-87.958374");
    pointsOutside.add("31.319856,-84.607544");
    pointsOutside.add("30.868282,-84.717407");
    pointsOutside.add("31.338624,-81.685181");
    pointsOutside.add("29.452991,-80.498657");
    pointsOutside.add("26.935783,-79.487915");
    pointsOutside.add("25.159207,-79.916382");
    pointsOutside.add("24.311058,-81.17981");
    pointsOutside.add("25.149263,-81.838989");
    pointsOutside.add("27.726326,-83.695679");
    pointsOutside.add("29.787263,-87.024536");
    pointsOutside.add("29.205877,-62.102052");
    pointsOutside.add("14.025751,-80.690919");
    pointsOutside.add("29.029276,-90.805666");
    pointsOutside.add("-12.606032,-70.151369");
    pointsOutside.add("-56.520716,-172.822269");
    pointsOutside.add("-75.89666,9.082024");
    pointsOutside.add("-24.078567,142.675774");
    pointsOutside.add("84.940737,177.480462");
    pointsOutside.add("47.374545,9.082024");
    pointsOutside.add("25.831538,-1.069338");
    pointsOutside.add("0,0");

    for(String s : pointsOutside){
        assertFalse(r.coordinate_is_inside_polygon(
            Double.parseDouble(s.split(",")[0]),
            Double.parseDouble(s.split(",")[1]), lat_array, long_array));
    }
}
}
//The list of lat/long inside florida bounding box all return true.
//The list of lat/long outside florida bounding box all return false.

Usé eclipse IDE para hacer que esto funcione java usando java 1.6.0. Para mi pasan todas las pruebas unitarias. Debe incluir el archivo junit 4 jar en su classpath o importarlo en Eclipse.