0

I have some points that are located in the same place, with WGS84 latlngs, and I want to 'jitter' them randomly so that they don't overlap.

Right now I'm using this crude method, which jitters them within a square:

r['latitude'] = float(r['latitude']) + random.uniform(-0.0005, 0.0005)
r['longitude'] = float(r['longitude']) + random.uniform(-0.0005, 0.0005)

How could I adapt this to jitter them randomly within a circle?

I guess I want a product x*y = 0.001 where x and y are random values. But I have absolutely no idea how to generate this!

(I realise that really I should use something like this to account for the curvature of the earth's surface, but in practice a simple circle is probably fine :) )

Community
  • 1
  • 1
Richard
  • 62,943
  • 126
  • 334
  • 542
  • See [Generate a random point within a circle (uniformly)](http://stackoverflow.com/a/5838055/2291710). – Delgan Aug 28 '15 at 18:04
  • 2
    possible duplicate of [Generate a random point within a circle (uniformly)](http://stackoverflow.com/questions/5837572/generate-a-random-point-within-a-circle-uniformly) – tzaman Aug 28 '15 at 18:05
  • Yes, it is a duplicate! Thanks for the link! – Richard Aug 28 '15 at 19:08
  • Are you sure you want a uniform distribution as requested in the duplicate? In your case a weighting towards the center might make more sense. – Mark Ransom Aug 28 '15 at 21:23

3 Answers3

1

The basic idea is, you generate a vector with x = radius of circle y = 0. You then rotate the vector by a random angle between 0 and 360, or 0 to 2 pi radians.

You then apply this displacement vector and you have your random jitter in a circle.

An example from one of my scripts:

    def get_randrad(pos, radius):
        radius = random() * radius
        angle = random() * 2 * pi
        return (int(pos[0] + radius * cos(angle)),
                int(pos[1] + radius * sin(angle)))

pos beeing the target location and radius beeing the "jitter" range.

As pjs pointed out, add 

radius *= math.sqrt(random())

for uniform distribution

Berserker
  • 1,112
  • 10
  • 26
  • 1
    It won't work if one wants the points to be distributed uniformly over the circle area. With this method the points density will be higher towards the center. – Eugene Sh. Aug 28 '15 at 18:05
  • Not uniform though, this will be more dense towards the center of the circle. – tzaman Aug 28 '15 at 18:06
  • use random.betavariate on the radius to balance it out? Should work, just weight it by the square. Also the original question does not ask for uniform distribution. – Berserker Aug 28 '15 at 18:08
  • Use `radius *= math.sqrt(random())` to get results uniformly distributed over the circle. – pjs Aug 28 '15 at 20:27
1

One simple way to generate random samples within a circle is to just generate square samples as you are, and then reject the ones that fall outside the circle.

tzaman
  • 46,925
  • 11
  • 90
  • 115
  • Actually yes, it will. – Eugene Sh. Aug 28 '15 at 18:09
  • That's a nice simple solution! – Richard Aug 28 '15 at 19:07
  • 1
    This is uniformly distributed, and is actually faster than going to polar coordinates and back because you avoid the transcendental functions. – pjs Aug 28 '15 at 20:30
  • You can run into thousands of repetitions of not hitting inside the circle. The chance is low, but I've seen rarer things happen. – Berserker Aug 29 '15 at 01:33
  • 1
    @Berserker Thousands? Don't be ridiculous. Each trial has about a 4/5th chance of being inside; the chance of missing even a dozen times in a row is under a millionth of a percent. – tzaman Aug 31 '15 at 14:58
0

Merely culling results that fall outside your circle will be sufficient.

If you don't want to throw out some percentage of random results, you could choose a random angle and distance, to ensure all your values fall within the radius of your circle. It's important to note, with this solution, that the precision of the methods you use to extrapolate an angle into a vector will skew your distribution to be more concentrated in the center.

If you make a vector out of your x,y values, and then do something like randomize the length of said vector to fall within your circle, your distribution will no longer be uniform, so I would steer clear of that approach, if uniformity is your biggest concern.

The culling approach is the most evenly distributed, of the three I mentioned, although the random angle/length approach is usually fine, except in cases involving very fine precision and granularity.

MMc
  • 46
  • 5
  • Culling results that fall outside the circle is definitely not sufficient! Or do you mean writing a function and calling it recursively until I get a satisfactory result? – Richard Aug 28 '15 at 19:07