4

How to get Random Geo-points[ lat/long in decimal], placed anywhere inside a 100 meter radius circle? The center of the circle is another reference GeoPoint. Is there any Function/Formulae that implements this?

Basically I am reading the GPS input of my android device and need to generate random Geo-Points around the device [In a circle of radius 100 meters centered at my device].

Please note : There are no Geo-Points pre-stored in Database. I need to create all the Geo-points on the fly as mentioned above.

aswin akhilesh
  • 115
  • 2
  • 7
  • I am a newbie android programmer - I went through some articles regarding Minimum Bounding Rectangle, Geo locations etc.I am able to get the user location through GPS correctly but am stuck with the next step, which is exactly what I have explained above. – aswin akhilesh Mar 28 '12 at 23:48

3 Answers3

6

I just wrote a a Ruby method which extends Random to provide this.

Caveat: The points all lay within a box, not a circle.

class Random
  def location(lat, lng, max_dist_meters)

This is called with Random.new.location(mid_lat, mid_lng, dist). It will return a point which is probably within max_dist_meters of a the mid point.

    max_radius = Math.sqrt((max_dist_meters ** 2) / 2.0)

Without adjusting to max_radius we'd get points inside a square outside the circle (i.e. in the corners), where the distance would be greater than max_dist_meters. This constrains us to a square inside the circle which is probably more what you want.

    lat_offset = rand(10 ** (Math.log10(max_radius / 1.11)-5))
    lng_offset = rand(10 ** (Math.log10(max_radius / 1.11)-5))

The 1.11 and 5 come from here.

    lat += [1,-1].sample * lat_offset
    lng += [1,-1].sample * lng_offset
    lat = [[-90, lat].max, 90].min
    lng = [[-180, lng].max, 180].min

We should probably wrap around here instead of just clamping the value, fixes welcome.

    [lat, lng]
  end
end

Comments / clean up welcome!

Sample output here which you can see nicely if you paste the lat/lngs here.

davetapley
  • 17,000
  • 12
  • 60
  • 86
1

Pick random points on a square (i.e. pairs of uniform random numbers), then discard any that don't lie within a circle inscribed in that square. Given (x,y) pairs, a point is within your circle if:

(x - c_x)^2 + (y - c_y)^2 < r,

where (c_x, c_y) is the centre of your circle and r is its radius.

jimw
  • 2,548
  • 15
  • 12
  • I have a doubt in the first part of your answer. How do I get those points within the square? The co-ordinates are in lat/long right? That is the problem. – aswin akhilesh Mar 29 '12 at 01:25
  • The best way is to pick your random numbers over a convient interval, then translate them to fit your geographic context. So if you want points within 100m of 10lat 10long, start with a square centered at (0,0) with side 200, so you're picking pairs of random numbers between -100 and 100. Then get points within the inscribed circle as above. You now have points within a circle of radius 100, so add (x,y) to (lat,long) to get what you require. – jimw Mar 29 '12 at 22:41
  • adding lat+100,long+100 would not give a point that is roughly, say, 100 m away. It would rather point to a location in some other continent. Based on my experiment, a geo location that is 200 m away has an offset of +- 0.000500 in latitude and +- 0.000750 in longitude. – aswin akhilesh Mar 30 '12 at 02:33
  • well no, you'll have to scale the numbers appropriately. That's not especially easy, as a degree of lat/long isn't the same linear distance everywhere. You also have to decide whether you want distance on the ground or as-the-crow-flies, and what approximation of the Earth's shape is suitable for your application. – jimw Mar 30 '12 at 23:45
  • Righto! I am assuming the user will not leave New Zealand - So have to work out the scaling appropriately. Thanks a bunch for your inputs! – aswin akhilesh Apr 12 '12 at 23:07
0

Start here: Generate a random point within a circle (uniformly). Then figure out how to center that circle at the reference lat/long. Then figure out how to map the randomly generated points to lat/long values. Hint: you want to add the individual components (say, x and y on your circle) to the circle's center.

Community
  • 1
  • 1
Matt Ball
  • 354,903
  • 100
  • 647
  • 710