4

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.

8
  • 1
    Show your input, output and expected output.
    – shmosel
    Apr 28, 2016 at 4:42
  • I should also say that I'm using static values right now but I'm going to keep them adjustable and reduce the amount of pointers Apr 28, 2016 at 4:44
  • lat lng varies very much in terms of decimal places. So random value that you are generating should differ in 0.000x range if they are bounded in a radius. Apr 28, 2016 at 5:17
  • Currently the latitude does so but the longitude does not do so properly. If I just hold to altering the latitude values, the points are distributed in a straight latitudinal line which is acceptable, but I would prefer the points to be scattered as far as longitude goes. I'm thinking a max/min would do the trick. Apr 28, 2016 at 5:28
  • Can you please specify what Location class is? I assume it is a (latitude, longitude) pair of doubles but I would like to make sure.
    – Julian
    Apr 28, 2016 at 5:49

4 Answers 4

20

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;
}
3
  • 1
    One of the best answers ever given on SOF!
    – Nirmalya
    Feb 6, 2019 at 2:29
  • What is that 'f' means? in this line. // double radiusInDegrees = radiusInMeters / 111320f;
    – Balaji Ks
    Oct 18, 2022 at 7:40
  • It means 111320 is a floating point number. Oct 18, 2022 at 8:17
2

Kotlin version of Markus Kauppinen answer

fun Location.getRandomLocation(radius: Double): Location {
    val x0: Double = longitude
    val y0: Double = latitude

    // Convert radius from meters to degrees.

    // Convert radius from meters to degrees.
    val radiusInDegrees: Double = radius / 111320f

    // Get a random distance and a random angle.

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

    // Compensate the x value.

    // Compensate the x value.
    val newX = x / cos(Math.toRadians(y0))

    val foundLatitude: Double
    val foundLongitude: Double

    foundLatitude = y0 + y
    foundLongitude = x0 + newX

    val copy = Location(this)
    copy.latitude = foundLatitude
    copy.longitude = foundLongitude
    return copy
}
1

It is hard for me to provide you with a pure Android solution as I never used those API. However I am sure you could easily adapt this solution to generate a random point within a given radius from an existing point.

The problem is solved in a two dimensions space however it is easy to extend to support altitude as well.

Please have a look at the code below. It provides you with a LocationGeneratoras well as my own Location implementation and an unit test proving that it works.

My solution is based on solving the circle equation (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);
            }
        }

    }
}

NOTE: This is just a generic solution to obtain a random point inside a circle with the center in (a, b) and a radius of r that can be used to solve your problem and not a straight solution that you can use as such. You most likely will need to adapt it to your use case.

I believe this is a natural solution.

Regards

4
  • What unit should I use for the radius? I tried Meters and Kilometers but I'm getting very high distances between my current location and the location that procures. Apr 28, 2016 at 8:36
  • The radius apparently has to be in degrees as it's added to/subtracted from a longitude value that's in degrees. So it would have to converted from meters to degrees to call the function. I wonder what's the implication of the angle/meters ratio changing in north-south direction in these calculations. (Maybe it works just fine. I didn't check.) Apr 28, 2016 at 15:57
  • @KoalaKoalified in my algorithm I did not attached any concept of distance unit., They are just three double values: longitude, latitude, radius. When I implemented it my assumption was that they they are just lengths all expressed with the same unit. Depending on your use case you can express in meters or Km. If your code uses degrees I don't think it will be any problem to convert them in meters or Km depending on your needs Keep in mind that my Location class was just a made up to get the generator work and could be very different than the Location you are using.
    – Julian
    Apr 28, 2016 at 22:54
  • I am sure there are lots of scientific places you can take the right conversion formulas from. Here are just two of them: here or here It seems to be quite complex I would be surprised not to have some java APIs that do this already.
    – Julian
    Apr 29, 2016 at 3:35
0

Longitude and Latitude uses ellipsoidal coordinates so for big radius (hundred meters) the error using this method would become sinificant. A possible trick is to convert to Cartesian coordinates, do the radius randomization and then transform back again to ellipsoidal coordinates for the long-lat. I have tested this up to a couple of kilometers with great success using this java library from ibm. Longer than that might work, but eventually the radius would fall off as the earth shows its spherical nature.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.