¿Generando ubicaciones aleatorias cerca?

30

Estoy tratando de crear ubicaciones aleatorias cerca de mi ubicación. Lo que quiero es crear pares aleatorios de latitud / longitud dentro de un círculo de 200 metros que rodea mi ubicación.

Esta es la fórmula que se me ocurrió (con la ayuda de personas en StackOverFlow): (Número aleatorio entre -1 y 1) * radio + (longitud anterior) = longitud nueva dentro del radio de longitud anterior

(Número aleatorio entre -1 y 1) * radio + (latitud anterior) = nueva latitud dentro del radio de la latitud anterior

Lo que pasa es que algo extraño está sucediendo con mi implementación porque todas las ubicaciones aleatorias están demasiado cerca de mi centro de ubicación, parece que la fórmula no cubre todo el radio.

¿Alguna idea de lo que podría estar mal con mi fórmula?

Editado para mostrar la implementación actual de Java:

public static Location getLocation(Location location, int radius) {
    Random random = new Random();

    // Convert radius from meters to degrees
    double radiusInDegrees = radius / METERS_IN_DEGREES;

    double x0 = location.getLongitude() * 1E6;
    double y0 = location.getLatitude() * 1E6;
    double u = random.nextInt(1001) / 1000;
    double v = random.nextInt(1001) / 1000;
    double w = radiusInDegrees * Math.sqrt(u);
    double t = 2 * Math.PI * v;
    double x = w * Math.cos(t);
    double y = w * Math.sin(t);

    // Adjust the x-coordinate for the shrinking of the east-west distances
    double new_x = x / Math.cos(y0);

    // Set the adjusted location
    Location newLocation = new Location("Loc in radius");
    newLocation.setLongitude(new_x + x0);
    newLocation.setLatitude(y + y0);

    return newLocation;
}

No estoy seguro de lo que estoy haciendo mal, porque las nuevas ubicaciones se crean en medio del mar.

¿Alguna idea?

piel de ante
fuente
¿Cómo implementas esta fórmula? ¿Puedes presentar esta parte de tu código? ¿Puede ser su problema en el generador de números pseudoaleatorios ?
Alex Markov
En lo que respecta a la pregunta final, los procedimientos como este encuentran estos problemas porque (i) las distancias se convierten incorrectamente a grados de latitud o longitud y (ii) la distorsión métrica del sistema de coordenadas no se tiene en cuenta o se tiene en cuenta de manera incorrecta. El uso de un sistema de coordenadas proyectadas en lugar de un sistema de coordenadas geográficas generalmente soluciona estos dos problemas. Hacer eso expondrá una propiedad fundamental de su fórmula, que podría o no ser deseable: genera ubicaciones dentro de un rectángulo alrededor de una ubicación, no dentro de un círculo.
whuber
Gracias Alex, el código de Java se publica en stackoverflow: stackoverflow.com/questions/10682743/…
pindleskin
Re el código editado: (i) random.nextInt(1001)/1000devolverá un valor mayor que 1 aproximadamente 0.1% del tiempo. ¿Por qué no estás usando random.nextDoubleo random.nextFloat? (ii) Multiplicar x0y y0por 1E6es bastante misterioso; no parece que produzca resultados correctos.
whuber
Es cierto, edité el método usando nextDouble y me libré de 1E6. Ahora, todas las ubicaciones generadas al azar tienen las mismas coordenadas que mi ubicación. Gracias por la ayuda, parece que voy a resolverlo pronto
pindleskin

Respuestas:

46

Esto es complicado por dos razones: primero, limitar los puntos a un círculo en lugar de un cuadrado; segundo, teniendo en cuenta las distorsiones en los cálculos de distancia.

Muchos SIG incluyen capacidades que manejan de manera automática y transparente ambas complicaciones. Sin embargo, las etiquetas aquí sugieren que una descripción independiente de SIG de un algoritmo puede ser deseable.

  1. Para generar puntos de manera uniforme, aleatoria e independiente dentro de un círculo de radio r alrededor de una ubicación (x0, y0), comience generando dos valores aleatorios uniformes independientes u y v en el intervalo [0, 1). (Esto es lo que casi todos los generadores de números aleatorios le proporcionan).

    w = r * sqrt(u)
    t = 2 * Pi * v
    x = w * cos(t) 
    y = w * sin(t)
    

    El punto aleatorio deseado está en la ubicación (x + x0, y + y0).

  2. Cuando se utilizan coordenadas geográficas (lat, lon), entonces x0 (longitud) e y0 (latitud) estarán en grados, pero lo más probable es que r esté en metros (o pies o millas o alguna otra medida lineal). Primero, convierta el radio r en grados como si estuviera ubicado cerca del ecuador. Aquí, hay unos 111.300 metros en un grado.

    En segundo lugar, después de generar x e y como en el paso (1), ajuste la coordenada x para reducir las distancias este-oeste:

    x' = x / cos(y0)

    El punto aleatorio deseado está en la ubicación (x '+ x0, y + y0). Este es un procedimiento aproximado. Para radios pequeños (menos de unos pocos cientos de kilómetros) que no se extienden sobre ninguno de los polos de la tierra, por lo general será tan preciso que no podrá detectar ningún error incluso cuando genere decenas de miles de puntos aleatorios alrededor de cada centro (x0, y0) .

whuber
fuente
2
Gran explicación whuber, eso es lo que necesitaba saber. Ahora lo voy a implementar. Gracias
pindleskin
1
Edité la pregunta para mostrar alguna implementación de Java de la fórmula
pindleskin
1
"hay unos 111.300 metros en un grado" solo por tener en cuenta que la coma se usa como separador de miles. radiusInDegrees = radius / 111300
RMalke
2
para lat, coordenadas largas no deberías hacer x '= x / cos (y0 * Pi / 180)
Aaron Stainback
2
Alucinante @whuber, y tiene sentido. Supongo que otra forma de verlo es imaginar que se generen 55 radios aleatorios para un radio de 20. Digamos que cada radio aleatorio es uniforme y exactamente igual a 0 a 20, entonces 0, 2, 4, ..., 20 Habrá 5 puntos con un radio de 5, un radio de 2, etc. Los 5 puntos con un radio de 2 (alrededor de un círculo de radio 2) se verán MUCHO más cerca entre sí que los 5 puntos con un radio de 20.
Aziz Javed
11

Implementado para Javascript:

var r = 100/111300 // = 100 meters
  , y0 = original_lat
  , x0 = original_lng
  , u = Math.random()
  , v = Math.random()
  , w = r * Math.sqrt(u)
  , t = 2 * Math.PI * v
  , x = w * Math.cos(t)
  , y1 = w * Math.sin(t)
  , x1 = x / Math.cos(y0)

newY = y0 + y1
newX = x0 + x1
Lira
fuente
10

La implementación correcta es:

public static void getLocation(double x0, double y0, int radius) {
    Random random = new Random();

    // Convert radius from meters to degrees
    double radiusInDegrees = radius / 111000f;

    double u = random.nextDouble();
    double v = random.nextDouble();
    double w = radiusInDegrees * Math.sqrt(u);
    double t = 2 * Math.PI * v;
    double x = w * Math.cos(t);
    double y = w * Math.sin(t);

    // Adjust the x-coordinate for the shrinking of the east-west distances
    double new_x = x / Math.cos(Math.toRadians(y0));

    double foundLongitude = new_x + x0;
    double foundLatitude = y + y0;
    System.out.println("Longitude: " + foundLongitude + "  Latitude: " + foundLatitude );
}

Eliminé la dependencia de bibliotecas externas para hacerlo más accesible.

atok
fuente
Edición propuesta de OP Según este Q de preguntas y respuestas de stackoverflow, en Java Math.cos () espera entradas en radianes.
MikeJRamsey56
3

La respuesta aceptada y los derivados no funcionaron para mí. Los resultados fueron muy inexactos.

Implementación correcta en javascript:

function pointAtDistance(inputCoords, distance) {
    const result = {}
    const coords = toRadians(inputCoords)
    const sinLat =  Math.sin(coords.latitude)
    const cosLat =  Math.cos(coords.latitude)

    /* go a fixed distance in a random direction*/
    const bearing = Math.random() * TWO_PI
    const theta = distance/EARTH_RADIUS
    const sinBearing = Math.sin(bearing)
    const cosBearing =  Math.cos(bearing)
    const sinTheta = Math.sin(theta)
    const cosTheta =    Math.cos(theta)

    result.latitude = Math.asin(sinLat*cosTheta+cosLat*sinTheta*cosBearing);
    result.longitude = coords.longitude + 
        Math.atan2( sinBearing*sinTheta*cosLat, cosTheta-sinLat*Math.sin(result.latitude )
    );
    /* normalize -PI -> +PI radians (-180 - 180 deg)*/
    result.longitude = ((result.longitude+THREE_PI)%TWO_PI)-Math.PI

    return toDegrees(result)
}

function pointInCircle(coord, distance) {
    const rnd =  Math.random()
    /*use square root of random number to avoid high density at the center*/
    const randomDist = Math.sqrt(rnd) * distance
    return pointAtDistance(coord, randomDist)
}

La esencia completa aquí

En la respuesta aceptada, descubrí que los puntos se distribuyen en una elipse con un ancho de 1.5 veces su altura (en Panamá) y 8 veces su altura (en el norte de Suecia). Si eliminé el ajuste x coord de la respuesta de @ whuber, la elipse se distorsiona de la otra manera, 8 veces más que su ancho.

El código en mi respuesta se basó en algoritmos de aquí

A continuación puede ver dos jsfiddles que muestran el problema con la elipse de estiramiento

Algoritmo correcto

Algoritmo distorsionado

Julian Mann
fuente
Su descripción de los problemas que ha tenido sugiere que su implementación fue incorrecta.
whuber
Puede que tengas razón. ¿Te gustaría echar un vistazo a los jsfiddles que hice y decirme dónde me equivoqué?
Julian Mann
He comparado con la respuesta de Java atok anteriormente, e hice este cambio a su jsFiddle del algoritmo distored en whuberPointAtDistance(): x1 = (w * Math.cos(t)) / Math.cos(y0 * (Math.PI / 180)).
Matt
1
A pesar de mi corrección, obtuve resultados mucho más precisos con la esencia de Julian. Al agregar mis correcciones a whuberPointAtDistance () y ejecutarlas en la esencia con el informe de error, mostró un error del 0.05% en los tres escenarios (significativamente más alto que la alternativa)
Matt
1

En python

# Testing simlation of generating random points 
from __future__ import division
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.axes_grid1 import host_subplot
import mpl_toolkits.axisartist as AA

def create_random_point(x0,y0,distance):
    """
            Utility method for simulation of the points
    """   
    r = distance/ 111300
    u = np.random.uniform(0,1)
    v = np.random.uniform(0,1)
    w = r * np.sqrt(u)
    t = 2 * np.pi * v
    x = w * np.cos(t)
    x1 = x / np.cos(y0)
    y = w * np.sin(t)
    return (x0+x1, y0 +y)

fig = plt.figure()
ax = host_subplot(111, axes_class=AA.Axes)

#ax.set_ylim(76,78)
#ax.set_xlim(13,13.1)
ax.set_autoscale_on(True)

latitude1,longitude1 = 13.04738626,77.61946793  
ax.plot(latitude1,longitude1,'ro')

for i in range(1,20):
    x,y = create_random_point(latitude1,longitude1 ,500 )
    ax.plot(x,y,'bo')
    dist = haversine(x,y,latitude1,longitude1)
    print "Distance between points is " ,dist    # a value approxiamtely less than 500 meters   


plt.show()

Salida

La distancia entre puntos es 0.288044147914 La distancia entre puntos es 0.409557451806 La distancia entre puntos es 0.368260305716 La distancia entre puntos es 0.340720560546 La distancia entre puntos es 0.453773334731 La distancia entre puntos es 0.460608754561 La distancia entre puntos es 0.497188825577 La distancia entre puntos es 0.6031781888598 La distancia entre puntos es 0.6031781888598 La distancia entre puntos Distancia entre puntos es 0.503691568896 Distancia entre puntos es 0.175153349209 Distancia entre puntos es 0.195149463735 Distancia entre puntos es 0.424094009858 Distancia entre puntos es 0.286807741494 Distancia entre puntos es 0.558049206307 Distancia entre puntos es 0.498612171417 Distancia entre puntos es 0.047344718215 Distancia entre puntos es 0.047344718242 Distancia entre puntos

ingrese la descripción de la imagen aquí

Alex Punnen
fuente
0

Puede consultar los resultados de sus cálculos aquí . Desplácese hacia abajo hasta la sección llamada "Distancia dada del punto de destino y demora desde el punto de inicio". Incluso hay una fórmula simple de JavaScript en la parte inferior para implementar esto. Aún necesitará generar un rumbo aleatorio $ \ theta $ en radianes (medido en sentido horario desde el norte), aunque eso debería ser bastante sencillo. Estas fórmulas suponen una tierra esférica (aunque es elipsoidal), que es lo suficientemente buena, ya que produce errores de hasta 0.3%.

Dimitriy V. Masterov
fuente
0

Implementación para Swift

Obtener el lat y lng del geoencoder y pasarlo a esta función

func generateRandomLocation(lat: CLLocationDegrees, lng: CLLocationDegrees){
    let radius : Double = 100000 // this is in meters so 100 KM
    let radiusInDegrees: Double = radius / 111000
    let u : Double = Double(arc4random_uniform(100)) / 100.0
    let v : Double = Double(arc4random_uniform(100)) / 100.0
    let w : Double = radiusInDegrees * u.squareRoot()
    let t : Double = 2 * Double.pi * v
    let x : Double = w * cos(t)
    let y : Double = w * sin(t)

    // Adjust the x-coordinate for the shrinking of the east-west distances
    //in cos converting degree to radian
    let new_x : Double = x / cos(lat * .pi / 180 )

    processedLat = new_x + lat
    processedLng = y + lng

    print("The Lat are :- ")
    print(processedLat)
    print("The Lng are :- ")
    print(processedLng)
}

En mi ejemplo anterior, obtengo la latitud y las longitudes al geocodificar el nombre del país, ya que cada vez el nombre del país proporciona la misma latitud y longitud, que también en el medio del país, por lo que necesitaba aleatoriedad.

Pulkit
fuente
-1

privado vacío drawPolyline (doble lat, doble lng) {

         double Pi=Math.PI;

         double lt=lat;
         double ln=lng;

        //Earth’s radius, sphere
         double R=6378137;

         double dn = 50;
         double de = 50;

         //Coordinate offsets in radians
         double dLat = dn/R;
         double dLon = de/(R*Math.cos(Pi*lat/180));

        //OffsetPosition, decimal degrees
        double lat2 = lt + dLat * 180/Pi;
        double lon2 = ln + dLon * 180/Pi ;



            //12.987859, 80.231038
            //12.987954, 80.231252

        double lat3 = lt - dLat * 180/Pi;
        double lon3 = ln - dLon * 180/Pi ;

            LatLng origin=new LatLng(lt, lon3);

            LatLng dest=new LatLng(lt, lon2);




          Polyline line = googleMap.addPolyline(new PolylineOptions()
         .add(origin, dest)
         .width(6)
         .color(Color.RED));
Jeeva
fuente
55
¿Podría ampliar un poco sobre cómo esto resuelve los problemas de los OP y explicar brevemente su código?
Martin