¿Generar ubicaciones aleatorias cercanas?

Question

Estoy tratando de crear lugares aleatorios cerca de mi ubicación. Lo que quiero es crear pares de latitud/longitud aleatorios 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 la gente de StackOverFlow): (Número aleatorio entre -1 y 1)*radio + (longitud antigua) = nueva longitud dentro del radio de la longitud antigua

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

El caso es que algo raro está pasando con mi implementación porque todas las localizaciones aleatorias están demasiado cerca de mi centro de localizació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?

Answer 1

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

Muchos SIG incluyen funciones que gestionan de forma automática y transparente ambas complicaciones. Sin embargo, las etiquetas aquí presentes sugieren que puede ser deseable una descripción de un algoritmo independiente del SIG.

1. Generar puntos de manera uniforme, aleatoria e independiente dentro de un círculo de radio r alrededor de un lugar (x0, y0), se empieza generando dos valores aleatorios uniformes e independientes u y v en el intervalo [0, 1). (Esto es lo que te proporcionan casi todos los generadores de números aleatorios). Calcula

   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 r probablemente será en metros (o pies o millas o alguna otra medida lineal). Primero, convierta el radio r en grados como si estuvieras situado cerca del ecuador. Aquí hay unos 111.300 metros en un grado.

   Segundo, después de generando x y y como en el paso (1), ajuste la coordenada x para la reducción de 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 cientos de kilómetros) que no se extienden sobre ninguno de los polos de la tierra, suele ser tan preciso que no se puede detectar ningún error ni siquiera al generar decenas de miles de puntos aleatorios alrededor de cada centro (x0,y0).

Answer 2

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

He eliminado la dependencia de bibliotecas externas para hacerlo más accesible.

Answer 3

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

Answer 4

La respuesta aceptada y las derivadas no me sirvieron. Los resultados eran 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)
}

El resumen completo aquí

En la respuesta aceptada - encontré que los puntos se distribuyen en una elipse con su ancho 1,5 veces su altura (en Panamá) y 8 veces su altura (en el norte de Suecia). Si he eliminado el ajuste de la coordenada x de la respuesta de @whuber la elipse se distorsiona al revés, 8 veces más alta que su anchura.

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

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

Algoritmo correcto

Algoritmo distorsionado

Answer 5

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 los puntos es de 0.288044147914 La distancia entre los puntos es 0.409557451806 La distancia entre los puntos es 0.368260305716 La distancia entre los puntos es 0.340720560546 La distancia entre los puntos es 0.453773334731 La distancia entre los puntos es 0.460608754561 La distancia entre los puntos es 0.497188825576 La distancia entre los puntos es 0.603178188859 La distancia entre los puntos es 0.628898384307 La distancia entre los puntos es 0.416297587754 La distancia entre los puntos es 0.503691568896 La distancia entre los puntos es 0.175153349209 La distancia entre los puntos es de 0.195149463735 La distancia entre los puntos es 0.424094009858 La distancia entre los puntos es 0.286807741494 La distancia entre los puntos es 0.558049206307 La distancia entre los puntos es 0.498612171417 La distancia entre los puntos es 0.047344718215 La distancia entre los puntos es 0.484232497086