KoalaKoalified KoalaKoalified - 7 months ago 21
Java Question

Randomly generating a latlng within a radius yields a point out of bounds

I'm trying to generate a point within a radius and I'm getting incorrect values. Someone mind taking a look and telling me what I'm doing wrong for the longitude? This was a formulaic approach posted on a different question...

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


I should also say that for some reason the valid points yield a uniform line of coordinates when looking at them.

I think the latitude is processing correctly whereas the longitude is not.

Answer

Your code seems to be more or less based on an idea which is presented at gis.stackexchange.com and discussed some more there in this discussion and in this discussion.

If we take a closer look at it based on those discussions then maybe it makes more sense.

To easily limit the values to a circle it uses the approach of randomizing a direction and a distance. First we get two random double values between 0.0 ... 1.0:

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

As the radius is given in meters and the calculations require degrees, it's converted:

double radiusInDegrees = radiusInMeters / 111000f;

The degrees vs. meters ratio of the equator is used here. (Wikipedia suggests 111320 m.)

To have a more uniform distribution of the random points the distance is compensated with a square root:

w = r * sqrt(u)

Otherwise there would be a statistical bias in the amount of points near the center vs. far from the center. The square root of 1 is 1 and 0 of course 0, so multiplying the root of the random double by the intended max. radius always gives a value between 0 and the radius.

Then the other random double is multiplied by 2 * pi because there are 2 * pi radians in a full circle:

t = 2 * Pi * v

We now have an angle somewhere between 0 ... 2 * pi i.e. 0 ... 360 degrees.

Then the random x and y coordinate deltas are calculated with basic trigonometry using the random distance and random angle:

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

The [x,y] then points some random distance w away from the original coordinates towards the direction t.

Then the varying distance between longitude lines is compensated with trigonometry (y0 being the center's y coordinate):

x' = x / cos(y0)

Above y0 needs to be converted to radians if the cos() expects the angle as radians. In Java it does.

It's then suggested that these delta values are added to the original coordinates. The cos and sin are negative for half of the full circle's angles so just adding is fine. Some of the random points will be to the west from Greenwich and and south from the equator. There's no need to randomize should an addition or subtraction be done.

So the random point would be at (x'+x0, y+y0).

I don't know why your code has:

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

And like said we can ignore shouldAddOrSubtractLat and shouldAddOrSubtractLon.

In my mind x refers to something going from left to right or from west to east. That's how the longitude values grow even though the longitude lines go from south to north. So let's use x as longitude and y as latitude.

So what's left then? Something like:

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