¿Generando ubicaciones aleatorias cerca?

28

Estoy intentando 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 las personas en StackOverFlow): (Número aleatorio entre -1 y 1) * radio + (longitud antigua) = longitud nueva dentro del radio de la longitud antigua

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

La cosa 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 java actual:

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?

    
pregunta pindleskin 21.05.2012 - 17:26

8 respuestas

43

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

Muchos GIS incluyen capacidades que manejan ambas complicaciones de forma automática y transparente. Sin embargo, las etiquetas aquí sugieren que una descripción de un algoritmo independiente de GIS 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 < em> u y v en el intervalo [0, 1). (Esto es lo que casi todos los generadores de números aleatorios te proporcionan). Calcular

    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. Al usar coordenadas geográficas (lat, lon), entonces x0 (longitud) y y0 (latitud) estarán en grados pero r probablemente estará 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 alrededor de 111,300 metros en un grado.

    Segundo, después generando x y y como en el paso (1), ajusta la coordenada x para reducir el tamaño del este. distancias al 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 al generar decenas. de miles de puntos aleatorios alrededor de cada centro (x0, y0).

respondido por el whuber 21.05.2012 - 18:39
10

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
    
respondido por el Lyra 23.01.2015 - 21:56
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 que sea más accesible.

    
respondido por el atok 09.08.2013 - 12:38
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)
}

Aquí encontrará una lista completa

En la respuesta aceptada, encontré 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 quito el ajuste de coordenada x 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, puedes ver dos jsfiddles que muestran el problema con la elipse de estiramiento

Algoritmo correcto

algoritmo distorsionado

    
respondido por el Julian Mann 12.10.2016 - 06:28
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 los puntos es 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 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

    
respondido por el Alex Punnen 04.11.2015 - 11:28
0

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

    
respondido por el Dimitriy V. Masterov 22.05.2012 - 15:23
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 longitudes de la codificación geográfica del nombre del país, ya que cada vez, el nombre del país da la misma latitud y longitudes, que también en el centro del país, por lo que necesitaba aleatoriedad. p>     

respondido por el Pulkit 16.08.2018 - 21:04
-1

drawPolyline vacío privado (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));
    
respondido por el Jeeva 22.08.2014 - 14:57

Lea otras preguntas en las etiquetas