# How to generate random locations nearby my location?

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? thank you

-
How do you implement this formula? Can you present this part of your code? May be your problem in Pseudorandom number generator ? – Alex Markov May 21 '12 at 16:23
As far as the final question goes, procedures like this encounter such problems because (i) distances are incorrectly converted to degrees of latitude or longitude and (ii) the metric distortion of the coordinate system is not accounted for or is accounted for incorrectly. Using a projected coordinate system instead of a geographic coordinate system usually gets around both these problems. Doing that will expose a fundamental property of your formula, which might or might not be desirable: it generates locations within a rectangle around a location, not within a circle. – whuber May 21 '12 at 18:33
Thanks Alex, the java code is posted at stackoverflow: stackoverflow.com/questions/10682743/… – pindleskin May 22 '12 at 7:05
Re the edited code: (i) random.nextInt(1001)/1000 will return a value greater than 1 about 0.1% of the time. Why aren't you using random.nextDouble or random.nextFloat? (ii) Multiplying x0 and y0 by 1E6 is rather mysterious; it does not seem like it will produce correct results. – whuber May 22 '12 at 15:09
True, i edited the method using nextDouble and got the rid of 1E6. Now, all the random generated locations have the same coordinates that my location. Thanks for the help, it seems that i am going to solve it anytime soon – pindleskin May 22 '12 at 16:01

## 6 Answers

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

-
Great explanation whuber, that is what i needed to know. Now i am going to implement it. Thanks – pindleskin May 22 '12 at 7:06
I edited the question to show some java implementation of the formula – pindleskin May 22 '12 at 8:27
"there are about 111,300 meters in a degree" just for note the comma is used as thousand separator. radiusInDegrees=radius/111300 – RMalke May 7 '14 at 0:51
@eklam Thank you. I apologize for forgetting there are different conventions. It's good to know that the earth is not just 40 kilometers around :-). – whuber May 7 '14 at 13:58
@Alex I don't understand what you mean by "expanding" u, v, w, or t. The factor that governs distance is the radius r. You shouldn't ever generate u or v within any interval other than [0, 1]. – whuber Nov 4 '15 at 12:57

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%.

-

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(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.

-

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

-
Could you expand a bit on how this solves the OPs problems and explain your code breifly? – Martin Aug 22 '14 at 13:38

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

-

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


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

-