Zufälliges Erzeugen einer Entfernung innerhalb eines Radius ergibt einen Punkt außerhalb der Grenzen

Question

Ich versuche, einen Punkt innerhalb eines Radius zu generieren, und ich bekomme falsche Werte. Irgendjemand, der sich die Mühe macht, einen Blick darauf zu werfen und mir zu sagen, was ich für die Länge falsch mache? Dies war ein formelhafte Ansatz auf einer andere Frage gestellt ...

public static Location generateLocationWithinRadius(Location myCurrentLocation) { 
    return getLocationInLatLngRad(1000, myCurrentLocation); 
} 

protected static Location getLocationInLatLngRad(double radiusInMeters, Location currentLocation) { 
    double x0 = currentLocation.getLatitude(); 
    double y0 = currentLocation.getLongitude(); 

    Random random = new Random(); 

    // Convert radius from meters to degrees 
    double radiusInDegrees = radiusInMeters/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); 

    double new_x = x/Math.cos(y0); 
    double new_y = y/Math.cos(x0); 
    double foundLatitude; 
    double foundLongitude; 
    boolean shouldAddOrSubtractLat = random.nextBoolean(); 
    boolean shouldAddOrSubtractLon = random.nextBoolean(); 
    if (shouldAddOrSubtractLat) { 
     foundLatitude = new_x + x0; 
    } else { 
     foundLatitude = x0 - new_x; 
    } 
    if (shouldAddOrSubtractLon) { 
     foundLongitude = new_y + y0; 
    } else { 
     foundLongitude = y0 - new_y; 
    } 
    Location copy = new Location(currentLocation); 
    copy.setLatitude(foundLatitude); 
    copy.setLongitude(foundLongitude); 
    return copy; 
} 

ich auch, dass aus irgendeinem Grunde ergeben die gültigen Punkte eine einheitliche Linie von Koordinaten sagen soll, wenn sie anzusehen.

Ich denke, der Breitengrad wird korrekt verarbeitet, während der Längengrad nicht ist.

Answer 1

Ihr Code scheint auf einer Idee, es in this discussion und in this discussion einige weitere which is presented at gis.stackexchange.com und diskutiert mehr oder weniger zu stellen sind.

Wenn wir es anhand dieser Diskussionen näher betrachten, macht es vielleicht mehr Sinn.

Um die Werte auf einen Kreis zu beschränken, wird der Ansatz verwendet, eine Richtung und eine Entfernung zu randomisieren. Zuerst haben wir zwei zufällige Doppel Werte zwischen 0,0 erhalten ... 1.0:

double u = random.nextDouble(); 
double v = random.nextDouble(); 

Da der Radius in Metern angegeben wird und die Berechnungen erfordern Grad, wird es umgesetzt:

double radiusInDegrees = radiusInMeters/111000f; 

Der Grad vs. Meter-Verhältnis des Äquators wird hier verwendet. (Wikipedia legt nahe, 111320 m).

zu einer gleichmäßigeren Verteilung der Zufallspunkte der Abstand mit einer Quadratwurzel kompensiert wird:

w = r * sqrt(u) 

Ansonsten gibt in der Nähe eine statistische Vorspannung in der Menge der Punkte würde das Zentrum vs. weit vom Zentrum entfernt.Die Quadratwurzel von 1 ist 1 und 0 natürlich 0, also multipliziert die Wurzel des zufälligen Doppelten mit dem beabsichtigten max. Radius gibt immer einen Wert zwischen 0 und dem Radius an.

Dann wird die anderen zufälligen Doppel von 2 * pi multipliziert werden, weil es 2 * pi Radian in einem vollen Kreis ist:

t = 2 * Pi * v 

Wir haben jetzt einen Winkel irgendwo zwischen 0 ... 2 * pi dh 0 ... 360 Grad.

Dann wird die Zufalls x und y-Koordinate Deltas mit basischen Trigonometrie berechnet werden, um die Zufallsabstand und zufälligen Winkel unter Verwendung von:

x = w * cos(t) 
y = w * sin(t) 

Die [x,y] zeigt dann einige zufällige Abstand w weg von den ursprünglichen Koordinaten in die Richtung t.

Dann wird der variierende Abstand zwischen den Längengradlinien kompensiert mit Trigonometrie (y0 Zentrum der y-Koordinate ist):

x' = x/cos(y0) 

Above y0 Bedürfnisse Bogenmaß umgewandelt werden, wenn die cos() den Winkel Bogenmaß als erwartet. In Java tut es das.

Es wird dann vorgeschlagen, dass diese Delta-Werte zu den ursprünglichen Koordinaten hinzugefügt werden. Die cos und sin sind negativ für die Hälfte der vollen Winkel des Kreises, so einfach Hinzufügen ist in Ordnung. Einige der zufälligen Punkte werden westlich von Greenwich und südlich vom Äquator liegen. Es ist nicht notwendig, zu randomisieren, sollte eine Addition oder Subtraktion durchgeführt werden.

So wäre der zufällige Punkt bei (x'+x0, y+y0).

Ich weiß nicht, warum Ihr Code hat:

double new_y = y/Math.cos(x0); 

Und wie gesagt, wir shouldAddOrSubtractLat und shouldAddOrSubtractLon ignorieren können.

In meinen Gedanken bezieht sich x auf etwas, das von links nach rechts oder von West nach Ost geht. So wachsen die Längenwerte, obwohl die Längenlinien von Süden nach Norden gehen. Also benutzen wir x als Längengrad und y als Breitengrad.

Also was ist dann übrig? Etwas wie:

protected static Location getLocationInLatLngRad(double radiusInMeters, Location currentLocation) { 
    double x0 = currentLocation.getLongitude(); 
    double y0 = currentLocation.getLatitude(); 

    Random random = new Random(); 

    // Convert radius from meters to degrees. 
    double radiusInDegrees = radiusInMeters/111320f; 

    // Get a random distance and a random angle. 
    double u = random.nextDouble(); 
    double v = random.nextDouble(); 
    double w = radiusInDegrees * Math.sqrt(u); 
    double t = 2 * Math.PI * v; 
    // Get the x and y delta values. 
    double x = w * Math.cos(t); 
    double y = w * Math.sin(t); 

    // Compensate the x value. 
    double new_x = x/Math.cos(Math.toRadians(y0)); 

    double foundLatitude; 
    double foundLongitude; 

    foundLatitude = y0 + y; 
    foundLongitude = x0 + new_x; 

    Location copy = new Location(currentLocation); 
    copy.setLatitude(foundLatitude); 
    copy.setLongitude(foundLongitude); 
    return copy; 
} 

Answer 2

Es ist schwer für mich, Ihnen eine reine Android-Lösung zu bieten, da ich diese API noch nie benutzt habe. Ich bin mir jedoch sicher, dass Sie diese Lösung leicht anpassen können, um einen zufälligen Punkt innerhalb eines gegebenen Radius von einem vorhandenen Punkt zu generieren.

Das Problem ist in einem zweidimensionalen Raum gelöst, aber es ist leicht zu erweitern, um Höhe zu unterstützen.

Bitte sehen Sie sich den folgenden Code an. Es bietet Ihnen eine LocationGenerator sowie meine eigene Location Implementierung und einen Komponententest, der beweist, dass es funktioniert.

Meine Lösung basiert auf der Lösung die Kreisgleichung (x-a)^2 + (y-b)^2 = r^2

package my.test.pkg; 

import org.junit.Test; 

import java.util.Random; 

import static org.junit.Assert.assertTrue; 

public class LocationGeneratorTest { 
    private class Location { 
     double longitude; 
     double latitude; 

     public Location(double longitude, double latitude) { 
      this.longitude = longitude; 
      this.latitude = latitude; 
     } 
    } 

    private class LocationGenerator { 
     private final Random random = new Random(); 

     Location generateLocationWithinRadius(Location currentLocation, double radius) { 
      double a = currentLocation.longitude; 
      double b = currentLocation.latitude; 
      double r = radius; 

      // x must be in (a-r, a + r) range 
      double xMin = a - r; 
      double xMax = a + r; 
      double xRange = xMax - xMin; 

      // get a random x within the range 
      double x = xMin + random.nextDouble() * xRange; 

      // circle equation is (y-b)^2 + (x-a)^2 = r^2 
      // based on the above work out the range for y 
      double yDelta = Math.sqrt(Math.pow(r, 2) - Math.pow((x - a), 2)); 
      double yMax = b + yDelta; 
      double yMin = b - yDelta; 
      double yRange = yMax - yMin; 
      // Get a random y within its range 
      double y = yMin + random.nextDouble() * yRange; 

      // And finally return the location 
      return new Location(x, y); 
     } 
    } 

    @Test 
    public void shoulRandomlyGeneratePointWithinRadius() throws Exception { 
     LocationGenerator locationGenerator = new LocationGenerator(); 
     Location currentLocation = new Location(20., 10.); 
     double radius = 5.; 
     for (int i=0; i < 1000000; i++) { 
      Location randomLocation = locationGenerator.generateLocationWithinRadius(currentLocation, radius); 
      try { 
       assertTrue(Math.pow(randomLocation.latitude - currentLocation.latitude, 2) + Math.pow(randomLocation.longitude - currentLocation.longitude, 2) < Math.pow(radius, 2)); 
      } catch (Throwable e) { 
       System.out.println("i= " + i + ", x=" + randomLocation.longitude + ", y=" + randomLocation.latitude); 
       throw new Exception(e); 
      } 
     } 

    } 
} 

HINWEIS: Dies ist nur eine generische Lösung, die einen beliebigen Punkt innerhalb eines Kreises mit dem Zentrum in (a, b) zu erhalten, und ein Radius von r, der verwendet werden kann, um Ihr Problem zu lösen und nicht eine direkte Lösung, die Sie als solche verwenden können. Sie müssen es wahrscheinlich an Ihren Anwendungsfall anpassen.

Ich glaube, das ist eine natürliche Lösung.

Grüße

Answer 3

Länge und Breite verwendet Ellipsoid-Koordinaten so für großen Radius (hundert Meter) der Fehler dieser Methode würde sinificant werden. Ein möglicher Trick besteht darin, in kartesische Koordinaten zu konvertieren, die Radius-Randomisierung durchzuführen und dann wieder in ellipsenförmige Koordinaten für den Lang-Breitengrad umzuwandeln. Ich habe dies bis zu einigen Kilometern mit großem Erfolg unter Verwendung von this java library von ibm getestet. Länger als das könnte funktionieren, aber irgendwann würde der Radius abfallen, wenn die Erde ihre sphärische Natur zeigt.