Zufällige Orte in der Nähe generieren?

30

Ich versuche, zufällige Standorte in der Nähe meines Standorts zu erstellen. Ich möchte zufällige Längen- und Breitengrade in einem 200-Meter-Kreis um meinen Standort erstellen.

Dies ist die Formel, die ich (mithilfe von Leuten bei StackOverFlow) gefunden habe: (Zufallszahl zwischen -1 und 1) * Radius + (alter Längengrad) = neuer Längengrad innerhalb des Radius des alten Längengrads

(Zufallszahl zwischen -1 und 1) * Radius + (alter Breitengrad) = neuer Breitengrad innerhalb des Radius des alten Breitengrads

Die Sache ist, dass mit meiner Implementierung etwas Seltsames passiert, weil alle zufälligen Orte zu nahe an meinem Standortzentrum liegen. Es scheint, dass die Formel nicht den gesamten Radius abdeckt.

Irgendeine Idee, was mit meiner Formel falsch sein könnte?

Bearbeitet, um die aktuelle Java-Implementierung anzuzeigen:

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

Ich bin mir nicht sicher, was ich falsch mache, weil die neuen Orte mitten auf dem Meer entstehen.

Irgendeine Idee?

pindleskin
quelle
Wie implementieren Sie diese Formel? Können Sie diesen Teil Ihres Codes präsentieren? Kann Ihr Problem im Pseudozufallszahlengenerator sein ?
Alex Markov
Was die letzte Frage betrifft, stoßen Prozeduren wie diese auf solche Probleme, weil (i) Entfernungen falsch in Breiten- oder Längengrade umgewandelt werden und (ii) die metrische Verzerrung des Koordinatensystems nicht oder falsch berücksichtigt wird. Die Verwendung eines projizierten Koordinatensystems anstelle eines geografischen Koordinatensystems umgeht normalerweise beide Probleme. Wenn Sie dies tun, wird eine grundlegende Eigenschaft Ihrer Formel angezeigt, die möglicherweise wünschenswert oder nicht wünschenswert ist: Es werden Positionen innerhalb eines Rechtecks um eine Position generiert , nicht innerhalb eines Kreises.
whuber
Danke Alex, der Java-Code ist auf stackoverflow zu finden: stackoverflow.com/questions/10682743/…
pindleskin
Bezüglich des bearbeiteten Codes: (i) random.nextInt(1001)/1000wird in etwa 0,1% der Fälle ein Wert größer als 1 zurückgegeben. Warum benutzt du nicht random.nextDoubleoder random.nextFloat? (ii) Multipliziert x0und y0durch 1E6ist ziemlich mysteriös; es scheint nicht so, als würde es zu korrekten Ergebnissen führen.
whuber
Richtig, ich habe die Methode mit nextDouble bearbeitet und 1E6 entfernt. Jetzt haben alle zufällig generierten Standorte dieselben Koordinaten wie mein Standort. Vielen Dank für die Hilfe, es scheint, dass ich es bald lösen werde
Pindleskin

Antworten:

46

Dies ist aus zwei Gründen schwierig: Erstens: Beschränken der Punkte auf einen Kreis anstelle eines Quadrats; zweitens die Berücksichtigung von Verzerrungen bei den Entfernungsberechnungen.

Viele GIS enthalten Funktionen, die beide Komplikationen automatisch und transparent behandeln. Die Tags hier legen jedoch nahe, dass eine GIS-unabhängige Beschreibung eines Algorithmus wünschenswert sein kann.

  1. Um Punkte gleichmäßig, zufällig und unabhängig voneinander innerhalb eines Kreises mit dem Radius r um einen Ort (x0, y0) zu erzeugen, erzeugen Sie zunächst zwei unabhängige gleichmäßige Zufallswerte u und v im Intervall [0, 1). (Dies ist, was fast jeder Zufallszahlengenerator bietet.) Compute

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

    Der gewünschte zufällige Punkt befindet sich an der Position (x + x0, y + y0).

  2. Bei Verwendung von geografischen Koordinaten (Lat, Lon) werden x0 (Längengrad) und y0 (Breitengrad) in Grad angegeben , r wird jedoch höchstwahrscheinlich in Metern (oder Fuß oder Meilen) oder einem anderen linearen Maß angegeben. Berechnen Sie zunächst den Radius r in Grad, als ob Sie sich in der Nähe des Äquators befänden. Hier sind es etwa 111.300 Meter in einem Grad.

    Zweitens stellen Sie nach dem Erzeugen von x und y wie in Schritt (1) die x-Koordinate für das Schrumpfen der Ost-West-Abstände ein:

    x' = x / cos(y0)

    Der gewünschte zufällige Punkt befindet sich an der Position (x '+ x0, y + y0). Dies ist eine ungefähre Vorgehensweise. Bei kleinen Radien (weniger als ein paar hundert Kilometer), die sich nicht über einen der Erdpole erstrecken, ist die Genauigkeit in der Regel so hoch, dass Sie selbst dann keinen Fehler feststellen können, wenn Sie zehntausende zufällige Punkte um jedes Zentrum (x0, y0) erzeugen. .

whuber
quelle
2
Tolle Erklärung, genau das musste ich wissen. Jetzt werde ich es implementieren. Danke
Pindleskin
1
Ich habe die Frage bearbeitet, um eine Java-Implementierung der Formel zu zeigen
pindleskin
1
"Es gibt ungefähr 111.300 Meter in einem Grad", nur um das Komma als Tausendertrennzeichen zu kennzeichnen. radiusInDegrees = radius / 111300
RMalke
2
für lat, lange Koordinaten sollten Sie nicht tun x '= x / cos (y0 * Pi / 180)
Aaron Stainback
2
Geist geblasen @whuber, und es macht Sinn. Eine andere Art, es zu betrachten, ist, sich 55 zufällige Radien für einen Radius von 20 vorzustellen. Nehmen wir an, jeder zufällige Radius ist einheitlich und genau gleich entweder 0 bis 20, also 0, 2, 4, ..., 20 Es gibt also 5 Punkte mit einem Radius von, 5 mit einem Radius von usw. Die 5 Punkte mit einem Radius von 2 (um einen Kreis mit einem Radius von 2) sehen VIEL näher zueinander aus als die 5 Punkte mit einem Radius von 20.
Aziz Javed
11

Implementiert für 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
quelle
10

Die korrekte Implementierung ist:

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

Ich habe die Abhängigkeit von externen Bibliotheken entfernt, um den Zugriff zu erleichtern.

atok
quelle
Vorgeschlagene Bearbeitung von OP Gemäß diesen Fragen und Antworten zum Stackoverflow erwartet Math.cos () in Java Eingaben im Bogenmaß.
MikeJRamsey56
3

Akzeptierte Antworten und Derivate haben bei mir nicht funktioniert. Die Ergebnisse waren sehr ungenau.

Richtige Implementierung in 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)
}

Voller Kern hier

In der akzeptierten Antwort stellte ich fest, dass Punkte in einer Ellipse mit der 1,5-fachen Breite (in Panama) und der 8-fachen Höhe (in Nordschweden) verteilt sind. Wenn ich die x-Koord-Anpassung aus der @ whuber-Antwort entfernt habe, ist die Ellipse in die andere Richtung verzerrt, achtmal höher als ihre Breite.

Der Code in meiner Antwort basierte auf Algorithmen von hier

Unten sehen Sie zwei jsfiddles, die das Problem mit der Streckellipse zeigen

Richtiger Algorithmus

Verzerrter Algorithmus

Julian Mann
quelle
Ihre Beschreibung der aufgetretenen Probleme weist darauf hin, dass Ihre Implementierung nicht korrekt war.
whuber
Sie haben vielleicht recht. Möchten Sie sich die von mir erstellten Jsfiddles ansehen und mir sagen, wo ich falsch liege?
Julian Mann
Ich habe mit der obigen Java-Antwort von atok verglichen und diese Änderung an Ihrer jsfiddle des verzerrten Algorithmus in whuberPointAtDistance(): vorgenommen x1 = (w * Math.cos(t)) / Math.cos(y0 * (Math.PI / 180)).
Matt
1
Trotz meiner Korrektur hatte ich viel genauere Ergebnisse mit Julians Kern. Wenn ich meine Korrekturen zu whuberPointAtDistance () hinzufüge und sie in der Liste mit dem Fehlerbericht ausführe, wird in allen drei Szenarien ein Fehler von 0,05% angezeigt (deutlich höher als bei der Alternative.)
Matt
1

In 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()

Ausgabe

Die Entfernung zwischen Punkten beträgt 0.288044147914. Die Entfernung zwischen Punkten beträgt 0.409557451806. Die Entfernung zwischen Punkten beträgt 0.368260305716. Die Entfernung zwischen Punkten beträgt 0.340720560546. Die Entfernung zwischen Punkten beträgt 0.453773334731. Die Entfernung zwischen Punkten beträgt 0.497188825576. Die Entfernung zwischen Punkten beträgt 0.6031781888888 Die Entfernung zwischen Punkten beträgt 0.503691568896. Die Entfernung zwischen Punkten beträgt 0.175153349209. Die Entfernung zwischen Punkten beträgt 0.195149463735. Die Entfernung zwischen Punkten beträgt 0.424094009858. Die Entfernung zwischen Punkten beträgt 0.558049206307. Die Entfernung zwischen Punkten beträgt 0.498612171417. Die Entfernung zwischen Punkten beträgt 0.047344718215

Bildbeschreibung hier eingeben

Alex Punnen
quelle
0

Sie können die Ergebnisse Ihrer Berechnungen überprüfen hier . Scrollen Sie zum Abschnitt "Zielpunkt bei gegebener Entfernung und Peilung vom Startpunkt". Es gibt sogar eine einfache JavaScript-Formel am unteren Rand, um dies zu implementieren. Sie müssen weiterhin eine zufällige Peilung $ \ theta $ im Bogenmaß (gemessen im Uhrzeigersinn von Norden) generieren, obwohl dies ziemlich einfach sein sollte. Diese Formeln gehen von einer kugelförmigen Erde aus (obwohl sie ellipsoidisch ist), was gut genug ist, da sie Fehler von bis zu 0,3% erzeugt.

Dimitriy V. Masterov
quelle
0

Implementierung für Swift

Lat und Lng vom Geoencoder holen und an diese Funktion übergeben

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

In meinem obigen Beispiel erhalte ich die geografischen Längen- und Breitengrade, indem ich den Namen des Landes geografisch codiere, da der Name des Landes jedes Mal die gleichen Breiten- und Längengrade angibt, die auch in der Mitte des Landes vorkommen, sodass ich Zufälligkeit brauchte.

Pulkit
quelle
-1

private void drawPolyline (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
quelle
5
Könnten Sie etwas näher darauf eingehen, wie dies die OP-Probleme löst, und Ihren Code kurz erläutern?
Martin