Generating random locations nearby?

Question

I am trying to create random locations nearby my location. What i want is to create random latitude/longitude pairs inside a 200 meters circle surrounding my location.

This is the formula i came up with (with the help of people at StackOverFlow): (Random number between -1 and 1)*radius + (old longitude) = new longitude within radius of old longitude

(Random number between -1 and 1)*radius + (old latitude) = new latitude within radius of old latitude

The thing is that something weird is happening with my implementation because all the random locations are too near of my location center, it seems that the formula does not cover the whole radius.

Any idea of what could be wrong with my formula?

Edited to show the current java implementation:

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

I am not sure what i am doing wrong, because the new locations are created in the middle of the sea.

Any idea?

Answer 1

This is tricky for two reasons: first, limiting the points to a circle instead of a square; second, accounting for distortions in the distance calculations.

Many GISes include capabilities that automatically and transparently handle both complications. However, the tags here suggest that a GIS-independent description of an algorithm may be desirable.

1. To generate points uniformly, randomly, and independently within a circle of radius r around a location (x0, y0), start by generating two independent uniform random values u and v in the interval [0, 1). (This is what almost every random number generator provides you.) Compute

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

   The desired random point is at location (x+x0, y+y0).

2. When using geographic (lat,lon) coordinates, then x0 (longitude) and y0 (latitude) will be in degrees but r will most likely be in meters (or feet or miles or some other linear measurement). First, convert the radius r into degrees as if you were located near the equator. Here, there are about 111,300 meters in a degree.

   Second, after generating x and y as in step (1), adjust the x-coordinate for the shrinking of the east-west distances:

   x' = x / cos(y0)
   

   The desired random point is at location (x'+x0, y+y0). This is an approximate procedure. For small radii (less than a few hundred kilometers) that do not extend over either pole of the earth, it will usually be so accurate you cannot detect any error even when generating tens of thousands of random points around each center (x0,y0).

Answer 2

The correct implementation is:

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

I removed the dependency on external libraries to make it more accessible.

Answer 3

Implemented for 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

Answer 4

Accepted answer and derivatives didn't work for me. Results were very inaccurate.

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

Full gist here

In the accepted answer - I found that points are distributed in an ellipse with its width 1.5 times its height (in Panama) and 8 times its height (in the north of Sweden). If I removed the x coord adjustment from @whuber's answer the ellipse is distorted the other way, 8 times higher than its width.

The code in my answer was based on algorithms from here

Below you can see two jsfiddles that show the problem with the stretching ellipse

Correct algorithm

Distorted algorithm

Answer 5

Implementation for Swift

Getting the lat and lng from geoencoder and passing it to this function

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 my example above I get the latitude and longitudes from geoencoding the name of the country, as each time, the country name gives same latitude and longitudes, that too in the middle of the country, so I needed randomness.

Answer 6

In Python

# Testing simlation of generating random points 
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.axes_grid1 import host_subplot
import mpl_toolkits.axisartist as AA
from math import radians

def haversine(lat1, lon1, lat2, lon2):

  R = 6372.8 # Earth radius in kilometers

  dLat = radians(lat2 - lat1)
  dLon = radians(lon2 - lon1)
  lat1 = radians(lat1)
  lat2 = radians(lat2)

  a = np.sin(dLat/2)**2 + np.cos(lat1)*np.cos(lat2)*np.sin(dLon/2)**2
  c = 2*np.arcsin(np.sqrt(a))

  return R * c

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 (f"Distance between points is  {dist}")    # a value approximately less than 500 meters   
 
    
plt.show()

Output

Distance between points is  0.288044147914
Distance between points is  0.409557451806
Distance between points is  0.368260305716
Distance between points is  0.340720560546
Distance between points is  0.453773334731
Distance between points is  0.460608754561
Distance between points is  0.497188825576
Distance between points is  0.603178188859
Distance between points is  0.628898384307
Distance between points is  0.416297587754
Distance between points is  0.503691568896
Distance between points is  0.175153349209
Distance between points is  0.195149463735
Distance between points is  0.424094009858
Distance between points is  0.286807741494
Distance between points is  0.558049206307
Distance between points is  0.498612171417
Distance between points is  0.047344718215
Distance between points is  0.484232497086

Answer 7

You can check the results of your calculations here. Scroll down to the section called "Destination point given distance and bearing from start point". There's even a simple JavaScript formula at the bottom to implement this. You will still need to generate a random bearing $\theta$ in radians (measured clockwise from north), though that should be pretty straight forward. These formulas assume a spherical earth (though it is ellipsoidal), which is good enough as it produces errors of up to 0.3%.

Answer 8

PHP implementation

function randomNearByCoord(array $coord, int $radiusKm, int $precision = 4): array
{
    $radiusRad = $radiusKm/111.3;
    $y0 = $coord['lat'];
    $x0 = $coord['lon'];
    $u = \lcg_value();
    $v = \lcg_value();
    $w = $radiusRad * \sqrt($u);
    $t = 2 * M_PI * $v;
    $x = $w * \cos($t);
    $y1 = $w * \sin($t);
    $x1 = $x / \cos(\deg2rad($y0));
    $newY = \round($y0 + $y1, $precision);
    $newX = \round($x0 + $x1, $precision);

    return ['lat' => $newY, 'lon' => $newX];
}

$center = ['lat' => 51.5146, 'lon' => -0.1361];
$newCoord = randomNearByCoord($center, 5);
var_dump($newCoord);

Answer 9

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