Generujesz losowe lokalizacje w pobliżu?

30

Próbuję utworzyć losowe lokalizacje w pobliżu mojej lokalizacji. Chcę stworzyć losowe pary szerokości i długości geograficznej wewnątrz 200-metrowego okręgu otaczającego moją lokalizację.

Oto formuła, którą wymyśliłem (z pomocą ludzi z StackOverFlow): (Losowa liczba od -1 do 1) * promień + (stara długość geograficzna) = nowa długość w promieniu starej długości geograficznej

(Liczba losowa od -1 do 1) * promień + (stara szerokość geograficzna) = nowa szerokość w promieniu starej szerokości geograficznej

Chodzi o to, że coś dziwnego dzieje się z moją implementacją, ponieważ wszystkie losowe lokalizacje znajdują się zbyt blisko centrum lokalizacji, wydaje się, że formuła nie obejmuje całego promienia.

Masz pojęcie, co może być nie tak z moją formułą?

Edytowane, aby pokazać bieżącą implementację 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;
}

Nie jestem pewien, co robię źle, ponieważ nowe lokalizacje są tworzone na środku morza.

Dowolny pomysł?

pindleskin
źródło
Jak wdrożyć tę formułę? Czy możesz przedstawić tę część swojego kodu? Może być twój problem z generatorem liczb pseudolosowych ?
Alex Markov
Jeśli chodzi o ostatnie pytanie, takie procedury napotykają takie problemy, ponieważ (i) odległości są niepoprawnie przeliczane na stopnie szerokości i długości geograficznej oraz (ii) zniekształcenie metryczne układu współrzędnych nie jest uwzględniane lub jest uwzględniane nieprawidłowo. Użycie rzutowanego układu współrzędnych zamiast układu współrzędnych geograficznych zwykle rozwiązuje oba te problemy. W ten sposób ujawnisz podstawową właściwość formuły, która może, ale nie musi być pożądana: generuje lokalizacje w prostokącie wokół lokalizacji, a nie w okręgu.
whuber
Dzięki Alex, kod Java został opublikowany na stackoverflow: stackoverflow.com/questions/10682743/…
pindleskin
Ponownie zmodyfikowany kod: (i) random.nextInt(1001)/1000zwróci wartość większą niż 1 przez około 0,1% czasu. Dlaczego nie używasz random.nextDoublelub random.nextFloat? (ii) Mnożenie x0i y0przez 1E6jest raczej tajemnicze; nie wydaje się, aby przyniosło prawidłowe wyniki.
whuber
To prawda, że ​​edytowałem metodę za pomocą nextDouble i pozbyłem się 1E6. Teraz wszystkie losowo generowane lokalizacje mają te same współrzędne, co moja lokalizacja. Dzięki za pomoc, wygląda na to, że wkrótce ją
rozwiążę

Odpowiedzi:

46

Jest to trudne z dwóch powodów: po pierwsze, ograniczenie punktów do koła zamiast kwadratu; po drugie, uwzględniając zniekształcenia w obliczeniach odległości.

Wiele GIS zawiera funkcje, które automatycznie i transparentnie obsługują oba powikłania. Jednak tagi tutaj sugerują, że pożądany może być niezależny od GIS opis algorytmu.

  1. Aby wygenerować punkty równomiernie, losowo i niezależnie w okręgu o promieniu r wokół lokalizacji (x0, y0), zacznij od wygenerowania dwóch niezależnych jednorodnych wartości losowych u i v w przedziale [0, 1). (Właśnie to zapewnia prawie każdy generator liczb losowych.) Oblicz

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

    Pożądany punkt losowy znajduje się w miejscu (x + x0, y + y0).

  2. Gdy używasz współrzędnych geograficznych (lat, lon), wówczas x0 (długość geograficzna) i y0 (szerokość geograficzna) będą wyrażone w stopniach, ale r najprawdopodobniej będzie wyrażone w metrach (stopach lub milach lub w innym pomiarze liniowym). Najpierw zamień promień r na stopnie , jakbyś znajdował się w pobliżu równika. Tutaj jest około 111 300 metrów na stopień.

    Po drugie, po generowanie X i Y , jak w punkcie (1), wyregulować współrzędna x dla kurczenia odległościach Wschód-Zachód:

    x' = x / cos(y0)

    Pożądany punkt losowy znajduje się w miejscu (x '+ x0, y + y0). To jest przybliżona procedura. W przypadku małych promieni (mniejszych niż kilkaset kilometrów), które nie rozciągają się nad żadnym biegunem ziemi, zwykle będzie tak dokładna, że ​​nie można wykryć żadnego błędu, nawet podczas generowania dziesiątek tysięcy losowych punktów wokół każdego centrum (x0, y0) .

Whuber
źródło
2
Świetne wytłumaczenie, właśnie to musiałem wiedzieć. Teraz zamierzam to zaimplementować. Dzięki
pindleskin
1
Zredagowałem pytanie, aby pokazać implementację tej formuły w
Javie
1
„w stopniach jest około 111 300 metrów”, dla przypomnienia przecinek jest używany jako separator tysięcy. radiusInDegrees = promień / 111300
RMalke
2
dla lat, długie współrzędne nie powinieneś robić x '= x / cos (y0 * Pi / 180)
Aaron Stainback
2
Umysł wysadzony w powietrze, i to ma sens. Innym sposobem, aby na to spojrzeć, jest wyobrażenie sobie, że generuje się 55 losowych promieni dla promienia równego 20. Powiedzmy, że każdy losowy promień jest jednolity i dokładnie równy 0 do 20, więc 0, 2, 4, ..., 20 Będzie więc 5 punktów o promieniu, 5 promieni 2, itd. 5 punktów o promieniu 2 (wokół okręgu o promieniu 2) będzie wyglądało DUŻO bliżej siebie niż 5 punktów o promieniu z 20.
Aziz Javed
11

Zaimplementowane dla 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
źródło
10

Prawidłowa implementacja to:

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

Usunąłem zależność od bibliotek zewnętrznych, aby była bardziej dostępna.

atok
źródło
Proponowane edycja PO, jak na to stackoverflow Q &, Java Math.cos (wejścia) oczekuje w radianach.
MikeJRamsey56,
3

Akceptowana odpowiedź i pochodne nie działały dla mnie. Wyniki były bardzo niedokładne.

Prawidłowa implementacja w 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)
}

Pełna treść tutaj

W przyjętej odpowiedzi stwierdziłem, że punkty są rozmieszczone w elipsie o szerokości 1,5 razy większej niż wysokość (w Panamie) i 8 razy większej (wysokość na północy Szwecji). Jeśli usunęłem korektę współrzędnych x z odpowiedzi @ Whubera, elipsa jest zniekształcona w drugą stronę, 8 razy większa niż jej szerokość.

Kod w mojej odpowiedzi został oparty na algorytmach stąd

Poniżej widać dwa jsfiddle, które pokazują problem z elipsą rozciągającą

Prawidłowy algorytm

Zniekształcony algorytm

Julian Mann
źródło
Twój opis problemów, które miałeś, sugeruje, że wdrożenie było niepoprawne.
whuber
Możesz mieć rację. Czy chciałbyś rzucić okiem na jsfiddles, które zrobiłem i powiedzieć mi, gdzie popełniłem błąd?
Julian Mann
I w porównaniu z ATOK Javy odpowiedzi powyżej, i dokonaniu tej zmiany do swojego jsfiddle z distored algorytmu whuberPointAtDistance(): x1 = (w * Math.cos(t)) / Math.cos(y0 * (Math.PI / 180)).
Matt
1
Pomimo mojej korekty miałem znacznie dokładniejsze wyniki z istotą Juliana. Dodanie moich poprawek do whuberPointAtDistance () i uruchomienie ich w zestawieniu z raportem błędów, pokazało błąd 0,05% we wszystkich trzech scenariuszach (znacznie wyższy niż alternatywa.)
Matt
1

W Pythonie

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

Wydajność

Odległość między punktami wynosi 0,288044147914 Odległość między punktami wynosi 0,409557451806 Odległość między punktami wynosi 0,3668260305716 Odległość między punktami wynosi 0,340720560546 Odległość między punktami wynosi 0,453773334731 Odległość między punktami wynosi 0,460608754561 Odległość między punktami wynosi 0,4797188825576 Odległość między punktami wynosi 0,603178188859 Odległość między punktami wynosi 0,603178188859 Odległość między punktami wynosi 0,603178188859 Odległość między punktami wynosi 0,503691568896 Odległość między punktami wynosi 0,175153349209 Odległość między punktami wynosi 0,195149463735 Odległość między punktami wynosi 0,424094009858 Odległość między punktami wynosi 0,286807741494 Odległość między punktami wynosi 0,558049206307 Odległość między punktami wynosi 0,498612171417 Odległość między punktami wynosi 0,04734471821523

wprowadź opis zdjęcia tutaj

Alex Punnen
źródło
0

Można sprawdzić wyniki swoich obliczeń tutaj . Przewiń w dół do sekcji o nazwie „Punkt docelowy na podstawie odległości i namiaru od punktu początkowego”. Na dole jest nawet prosta formuła JavaScript, aby to zaimplementować. Nadal będziesz musiał wygenerować losowe łożysko $ \ theta $ w radianach (mierzone zgodnie z ruchem wskazówek zegara od północy), choć powinno to być dość proste. Wzory te zakładają kulistą ziemię (chociaż jest elipsoidalna), co jest wystarczająco dobre, ponieważ powoduje błędy do 0,3%.

Dimitriy V. Masterov
źródło
0

Wdrożenie dla Swift

Pobieranie lat i lng z geoencodera i przekazywanie go do tej funkcji

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

W powyższym przykładzie otrzymuję szerokość i długość geograficzną z geograficznego kodowania nazwy kraju, ponieważ za każdym razem nazwa kraju podaje tę samą szerokość i długość geograficzną, tak samo jak w środku kraju, więc potrzebowałem losowości.

Pulkit
źródło
-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
źródło
5
Czy mógłbyś nieco rozwinąć sposób, w jaki rozwiązuje to problemy z OP, i szybko wyjaśnić swój kod?
Martin