Générer des emplacements aléatoires à proximité?

30

J'essaie de créer des emplacements aléatoires à proximité de mon emplacement. Ce que je veux, c'est créer des paires de latitude / longitude aléatoires à l'intérieur d'un cercle de 200 mètres entourant mon emplacement.

Voici la formule que j'ai trouvée (avec l'aide des gens de StackOverFlow): (nombre aléatoire entre -1 et 1) * rayon + (ancienne longitude) = nouvelle longitude dans le rayon de l'ancienne longitude

(Nombre aléatoire entre -1 et 1) * rayon + (ancienne latitude) = nouvelle latitude dans le rayon de l'ancienne latitude

Le truc, c'est que quelque chose d'étrange se passe avec mon implémentation car tous les emplacements aléatoires sont trop proches de mon centre de localisation, il semble que la formule ne couvre pas tout le rayon.

Une idée de ce qui pourrait mal avec ma formule?

Modifié pour montrer l'implémentation Java actuelle:

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

Je ne suis pas sûr de ce que je fais mal, car les nouveaux emplacements sont créés au milieu de la mer.

Une idée?

peau de fusain
la source
Comment mettez-vous en œuvre cette formule? Pouvez-vous présenter cette partie de votre code? Peut-être votre problème dans le générateur de nombres pseudo-aléatoires ?
Alex Markov
En ce qui concerne la dernière question, des procédures comme celle-ci rencontrent de tels problèmes car (i) les distances sont incorrectement converties en degrés de latitude ou de longitude et (ii) la distorsion métrique du système de coordonnées n'est pas prise en compte ou est prise en compte de manière incorrecte. L'utilisation d'un système de coordonnées projeté au lieu d'un système de coordonnées géographiques contourne généralement ces deux problèmes. Cela exposera une propriété fondamentale de votre formule, qui pourrait être souhaitable ou non: elle génère des emplacements dans un rectangle autour d'un emplacement, pas dans un cercle.
whuber
Merci Alex, le code java est publié sur stackoverflow: stackoverflow.com/questions/10682743/…
pindleskin
Concernant le code édité: (i) random.nextInt(1001)/1000renverra une valeur supérieure à 1 environ 0,1% du temps. Pourquoi n'utilisez-vous pas random.nextDoubleou random.nextFloat? (ii) La multiplication x0et y0par 1E6est plutôt mystérieuse; il ne semble pas que cela produira des résultats corrects.
whuber
C'est vrai, j'ai édité la méthode en utilisant nextDouble et je me suis débarrassé de 1E6. Maintenant, tous les emplacements générés au hasard ont les mêmes coordonnées que mon emplacement. Merci pour l'aide, il semble que je vais le résoudre bientôt
pindleskin

Réponses:

46

Ceci est délicat pour deux raisons: premièrement, limiter les points à un cercle au lieu d'un carré; deuxièmement, la prise en compte des distorsions dans les calculs de distance.

De nombreux SIG incluent des capacités qui gèrent automatiquement et de manière transparente les deux complications. Cependant, les balises suggèrent ici qu'une description indépendante d'un SIG d'un algorithme peut être souhaitable.

  1. Pour générer des points de manière uniforme, aléatoire et indépendante dans un cercle de rayon r autour d'un emplacement (x0, y0), commencez par générer deux valeurs aléatoires uniformes indépendantes u et v dans l'intervalle [0, 1). (C'est ce que presque tous les générateurs de nombres aléatoires vous fournissent.) Calcul

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

    Le point aléatoire souhaité est à l'emplacement (x + x0, y + y0).

  2. Lorsque vous utilisez des coordonnées géographiques (lat, lon), alors x0 (longitude) et y0 (latitude) seront en degrés mais r sera très probablement en mètres (ou pieds ou miles ou toute autre mesure linéaire). Tout d'abord, convertissez le rayon r en degrés comme si vous étiez situé près de l'équateur. Ici, il y a environ 111 300 mètres dans un degré.

    Deuxièmement, après avoir généré x et y comme à l'étape (1), ajustez la coordonnée x pour le rétrécissement des distances est-ouest:

    x' = x / cos(y0)

    Le point aléatoire souhaité est à l'emplacement (x '+ x0, y + y0). Il s'agit d'une procédure approximative. Pour les petits rayons (moins de quelques centaines de kilomètres) qui ne s'étendent sur aucun des pôles de la terre, il sera généralement si précis que vous ne pourrez détecter aucune erreur même en générant des dizaines de milliers de points aléatoires autour de chaque centre (x0, y0) .

whuber
la source
2
Grande explication whuber, c'est ce que j'avais besoin de savoir. Maintenant, je vais le mettre en œuvre. Merci
Pindleskin
1
J'ai édité la question pour montrer une implémentation Java de la formule
pindleskin
1
"il y a environ 111 300 mètres dans un degré" juste pour noter que la virgule est utilisée comme mille séparateur. radiusInDegrees = radius / 111300
RMalke
2
pour lat, les coordonnées longues ne devraient pas vous faire x '= x / cos (y0 * Pi / 180)
Aaron Stainback
2
L'esprit @whuber soufflé, et cela a du sens. Une autre façon de voir les choses, je suppose, est d'imaginer que 55 rayons aléatoires sont générés pour un rayon de 20. Disons que chaque rayon aléatoire est uniforme et exactement égal à 0 à 20, donc 0, 2, 4, ..., 20 Il y aura donc 5 points avec des rayons de, 5 des rayons de 2, etc. Les 5 points avec des rayons de 2 (autour d'un cercle de rayon 2) seront BEAUCOUP plus proches les uns des autres que les 5 points avec des rayons du 20.
Aziz Javed
11

Implémenté pour 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
Lyra
la source
10

L'implémentation correcte est:

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

J'ai supprimé la dépendance aux bibliothèques externes pour la rendre plus accessible.

atok
la source
Modification proposée de l'OP Selon ce Q&A stackoverflow, dans Java Math.cos () attend des entrées en radians.
MikeJRamsey56
3

La réponse acceptée et les dérivés n'ont pas fonctionné pour moi. Les résultats étaient très inexacts.

Implémentation correcte 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)
}

L'essentiel ici

Dans la réponse acceptée - j'ai trouvé que les points sont répartis dans une ellipse avec sa largeur 1,5 fois sa hauteur (au Panama) et 8 fois sa hauteur (dans le nord de la Suède). Si j'ai supprimé l'ajustement de coordonnée x de la réponse de @ whuber, l'ellipse est déformée dans l'autre sens, 8 fois plus élevée que sa largeur.

Le code dans ma réponse était basé sur des algorithmes d' ici

Ci-dessous, vous pouvez voir deux jsfiddles qui montrent le problème avec l'ellipse d'étirement

Algorithme correct

Algorithme déformé

Julian Mann
la source
Votre description des problèmes que vous avez rencontrés suggère que votre implémentation était incorrecte.
whuber
Vous avez peut-être raison. Pourriez-vous jeter un œil aux jsfiddles que j'ai faits et me dire où je me suis trompé.
Julian Mann
Je comparais avec la réponse Java atôk ci - dessus, et fait ce changement à votre jsFiddle de l'algorithme Distored dans whuberPointAtDistance(): x1 = (w * Math.cos(t)) / Math.cos(y0 * (Math.PI / 180)).
Matt
1
Malgré ma correction, j'ai eu des résultats beaucoup plus précis avec l'essentiel de Julian. En ajoutant mes corrections à whuberPointAtDistance () et en les exécutant dans l'essentiel avec le rapport d'erreur, il a montré une erreur de 0,05% dans les trois scénarios (significativement plus élevé que l'alternative.)
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()

Sortie

La distance entre les points est de 0,288044147914 La distance entre les points est de 0,409557451806 La distance entre les points est de 0,3668260305716 La distance entre les points est de 0,340720560546 La distance entre les points est de 0,453773334731 La distance entre les points est de 0,460608754561 La distance entre les points est de 0,497188825576 La distance entre les points est de 0,603178188859 La distance entre les points est 0,416629 La distance entre les points est de 0,503691568896 La distance entre les points est de 0,175153349209 La distance entre les points est de 0,195149463735 La distance entre les points est de 0,424094009858 La distance entre les points est de 0,286807741494 La distance entre les points est de 0,558049206307 La distance entre les points est de 0,498612171417 La distance entre les points est de 0,047344718215 La distance entre les points est de 0,484

entrez la description de l'image ici

Alex Punnen
la source
0

Vous pouvez vérifier les résultats de vos calculs ici . Faites défiler vers le bas jusqu'à la section intitulée «Point de destination en fonction de la distance et du relèvement par rapport au point de départ». Il y a même une simple formule JavaScript en bas pour implémenter cela. Vous devrez toujours générer un palier aléatoire $ \ theta $ en radians (mesuré dans le sens des aiguilles d'une montre à partir du nord), mais cela devrait être assez simple. Ces formules supposent une terre sphérique (bien qu'elle soit ellipsoïdale), ce qui est assez bon car elle produit des erreurs allant jusqu'à 0,3%.

Dimitriy V. Masterov
la source
0

Implémentation pour Swift

Obtenir le lat et le lng du géoencodeur et le passer à cette fonction

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

Dans mon exemple ci-dessus, j'obtiens la latitude et les longitudes en géoencodant le nom du pays, car chaque fois, le nom du pays donne la même latitude et les mêmes longitudes, que trop au milieu du pays, donc j'avais besoin d'aléatoire.

Pulkit
la source
-1

tirage privé nulPolyline (double lat, double 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
la source
5
Pourriez-vous développer un peu comment cela résout les problèmes de PO et expliquer votre code rapidement?
Martin