Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to generate random geo-coordinates within a given radius

jordinl.com

Post reply on HN
Print view View original

51–57 of 57 posts

Re: How to generate random geo-coordinates within a given radius

#51

Post by MaxBarraclough »

maxander wrote: post #42
MRD85 wrote: post #34

Why can't you simply generate two random numbers with one between 0 and 2pi, and the second between the min and max of distance? Now you've got polar coordinates. I'm not sure if I'm missing something or if this is overengineered. If people are interested I've included a link on how Tinder keeps your location private. It's really interesting. https://robertheaton.com/2018/07/09/how-tinder-keeps-your-lo...

As others have noted, this doesn’t result in a uniform distribution. But what you can do, instead, is generate a uniform distribution over a square centered on the point of interest, and simply re-do points that land outside of the circle. For most software engineers, this is probably simpler to understand and harder to screw up than implementing the Haversine formula. :)

Which has the unfortunate property that it isn't assured to terminate. Although I believe that discard-and-reattempt strategy is used in real-life RNG libraries if you ask for a random integer in an awkward interval.

Re: How to generate random geo-coordinates within a given radius

#52

Post by MaxBarraclough »

marcinzm wrote: post #30
iknowordidthat wrote: post #16

Over engineered much? > On a previous project we needed to show markers on a map to indicate there was a property, but for privacy reasons we wanted to show the marker on the map close to the property but not at the exact location of the property. So we needed to generate random points within a fixed distance of the original point location. At those distances, you can treat the surface as a plane and calculate points…

I was thinking the same thing. Just generate two random numbers in polar coordinates and then map back to a cartesian offset. Only trickiness is taking the square root of one of the numbers to generate the radius rather than the random number itself.

This is the solution I arrived at, too: explicitly balance out the bias, which seems to be as simple as just taking the square root. Surprised the whole thread isn't full of that idea.

Long rambling version:

The bias in the naive 'solution' is demonstrated in that if we consider a circle of radius 0.5, it has an area of 1/4 that of a circle with radius 1, not half. Which means that as we span our random parameter between 0 and 1, we 'spend too much time' in that small 'inner circle'.

(It's easiest to assume a circle of radius 1, centred about the origin. Nothing interesting arises from additional generality.)

So we don't want the displacement from the origin to rise linearly with the uniform-random parameter. Instead we want the area of our 'inner circle' to rise linearly. Which means that the displacement from the origin should be the square root of the random parameter. (The random parameter's interval will have to be adjusted appropriately of course.)

Our 'theta' has no bias trouble. Transforming from number (angle) into vector/coordinate form, is just routine trig. Nothing interesting to worry about there.

All that's left is to be careful that our theta span the interval [0, 2 * pi) (carefully excluding 2pi), whereas our area should span [0, pi * r^2] (inclusive, assuming that our 'circle' is meant to be an 'open ball' rather than a closed one).

Either we're missing something, or this Haversine business is a needlessly complex answer here.

I considered that another approach might be to define a spiral that 'winds through' all points in the circle, but I'm pretty sure that's not possible. If it were possible, it would give an injective space-filling curve, which is known not to exist. (If it were not injective, it would presumably be biased and so be a non-answer to our question.) Put another way, if your answer involves accepting just one random number, and not two, then your answer is necessarily wrong. (I think I'm getting all this right.) [0]

Another thought: the naive solution is biased despite being injective. Interesting. That seems to be the root of the failure of intuition that leads us to the naive (biased) 'solution'.

[0] https://en.wikipedia.org/w/index.php?title=Space-filling_cur...

Re: How to generate random geo-coordinates within a given radius

#53

Post by MaxBarraclough »

NamTaf wrote: post #48
GhostVII wrote: post #45

In practice, would it be easier to just randomly generate points within the bounding box of the radius, and then throw out any points that fall outside of the circle? Wouldn't work too well for the cases where you want points from some radius away, to some radius away, but would probably work well when you just want a random point inside of a given radius since only 1/4 of the points will have to be thrown out.

As far as I can tell, all the complexity comes about from the Haversine formula, which maps a circle to a spherical surface. If you were to treat that as a flat plane, I don't see why you couldn't just generate a radial angle and radial distance, then convert to an offset from your centre. That's trivial to perform. rand(0,2*pi) for angle, rand(d1,d2) for distance, and then convert from polar coordinates to Cartesian…

A couple of us (marcinzm got there first) stumbled onto what might be a much simpler solution, where we just counterbalance that bias. Perhaps we're missing something, but if so... well, then I missed it :-P

https://news.ycombinator.com/item?id=19193622

Re: How to generate random geo-coordinates within a given radius

#54

Post by NamTaf »

MaxBarraclough wrote: post #53
NamTaf wrote: post #48

Earlier quoted context omitted.

As far as I can tell, all the complexity comes about from the Haversine formula, which maps a circle to a spherical surface. If you were to treat that as a flat plane, I don't see why you couldn't just generate a radial angle and radial distance, then convert to an offset from your centre. That's trivial to perform. rand(0,2*pi) for angle, rand(d1,d2) for distance, and then convert from polar coordinates to Cartesian…

A couple of us (marcinzm got there first) stumbled onto what might be a much simpler solution, where we just counterbalance that bias. Perhaps we're missing something, but if so... well, then I missed it :-P https://news.ycombinator.com/item?id=19193622

That’s an elegant way to balance the issue, I like it. I guess it all really depends if you want an even distribution on area or in radial distance from the centre, so I can think of valid reasons to use both.

Re: How to generate random geo-coordinates within a given radius

#55

Post by MaxBarraclough »

NamTaf wrote: post #54
MaxBarraclough wrote: post #53

Earlier quoted context omitted.

A couple of us (marcinzm got there first) stumbled onto what might be a much simpler solution, where we just counterbalance that bias. Perhaps we're missing something, but if so... well, then I missed it :-P https://news.ycombinator.com/item?id=19193622

That’s an elegant way to balance the issue, I like it. I guess it all really depends if you want an even distribution on area or in radial distance from the centre, so I can think of valid reasons to use both.

Glad you like it. I really think we're on the right track with it - I was surprised the linked article didn't come up with the same idea.

I don't see much point in an even distribution in radial distance from the centre. If you want to model something like the distance from the bullseye to an archer's arrows, you're presumably going to want a normal distribution on radial distance from centre, which is of course very different (though at a glance they might look similar).

Re: How to generate random geo-coordinates within a given radius

#56

Post by Misdicorl »

MRD85 wrote: post #50
Misdicorl wrote: post #37

Earlier quoted context omitted.

This will give you a random distribution, but not a uniform one. Concrete description why: you're just as likely to end up 3 units from the center as 6 units from the center. However, there is twice as much space that is 6 units from the center than 3 units from the center.

I thought about this for a little bit, I might actually code up a demo. If you take a random number between the square of min and the square of max, then you make your polar r equal to square root of your random number.

Yup, this works in 2d.

Re: How to generate random geo-coordinates within a given radius

#57

Post by MaxBarraclough »

MaxBarraclough wrote: post #52
marcinzm wrote: post #30

Earlier quoted context omitted.

I was thinking the same thing. Just generate two random numbers in polar coordinates and then map back to a cartesian offset. Only trickiness is taking the square root of one of the numbers to generate the radius rather than the random number itself.

This is the solution I arrived at, too: explicitly balance out the bias, which seems to be as simple as just taking the square root. Surprised the whole thread isn't full of that idea. Long rambling version: The bias in the naive 'solution' is demonstrated in that if we consider a circle of radius 0.5, it has an area of 1/4 that of a circle with radius 1, not half. Which means that as we span our random parameter bet…

Ah. I now see the blog post is about spheres, not 2D space. It could have been more clear about what problem it was setting out to solve.
Post reply on HN