How to generate random geo-coordinates within a given radius • Hacker News Board

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

#41

Post by sjwright » Tue, Feb 19, 2019, 1:19 AM UTC

tzs wrote: post #7

> 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 This raises a couple of interesting questions. 1. How do you stop someone from finding the actual pr…

To answer (1), if you seed the randomiser with a known static value—e.g. the co-ordinates, or a database record ID—then repeat queries will return the same mangled result.

Or an even simpler, more trivial solution would be to store mangled values next to the true values. Then all of your APIs and services can pick the appropriate value for the circumstance.

To make it more obvious that the data is imprecise, I would also ensure that the mangled geo co-ordinates returned with a minimum number of decimal places. Three decimal places gives you a precision of 50–100 meters, depending on latitude. Four gives you 5-10 meters, which is the most you'd ever need for an approximate house location.

The concern that comes to my mind is the size of the randomisation and whether they factor in the size of surrounding properties. The level of imprecision required in a dense city will have little to no effect on farmland properties. I would dynamically adjust the random amplitude so that the circle of confusion covered a minimum number of properties. At minimum you'd find a database that listed median property sizes for a given postal code/zip code.

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

#42

Post by maxander » Tue, Feb 19, 2019, 2:13 AM UTC

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. :)

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

#43

Post by unterbahn » Tue, Feb 19, 2019, 2:47 AM UTC

usrusr wrote: post #13

Any random distribution will be leaky when it is centered around the real location and multiple samples can be taken. Quantization to a desired lack of precision is the answer, nobody will be able to tell a point that happens to be rounded to itself from one that happens to be rounded from close to a neighboring cell. If for some reason the data needs to appear random, you have to store a fixed random offset/alternat…

Leaflet.BlurredLocation https://github.com/publiclab/leaflet-blurred-location

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

#44

Post by jimsmart » Tue, Feb 19, 2019, 2:52 AM UTC

Converting lat/longs to Uber's H3 [1][2] system might prove useful here. Because H3 indexes are hierarchical, you can easily truncate them to obtain less precision. And then convert them back into lat/longs after truncation.

[1] https://github.com/uber/h3

[2] https://eng.uber.com/h3/

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

#45

Post by GhostVII » Tue, Feb 19, 2019, 3:03 AM UTC

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.

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

#46

Post by unterbahn » Tue, Feb 19, 2019, 3:06 AM UTC

Leaflet.BlurredLocation https://github.com/publiclab/leaflet-blurred-location - A Leaflet-based HTML interface for selecting a "blurred" or low-resolution location, to preserve privacy.

H3 is similar and cool, but this builds a similar nested grid concept around latitude/longitude, which can map to existing coordinate systems and database storage.

Also note that population density affects how effective a given precision "blur" is for an area; we're also hoping to develop a web service or library to roughly return population density for any given region of the globe.

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

#47

Post by unterbahn » Tue, Feb 19, 2019, 3:07 AM UTC

unterbahn wrote: post #46

Leaflet.BlurredLocation https://github.com/publiclab/leaflet-blurred-location - A Leaflet-based HTML interface for selecting a "blurred" or low-resolution location, to preserve privacy. H3 is similar and cool, but this builds a similar nested grid concept around latitude/longitude, which can map to existing coordinate systems and database storage. Also note that population density affects how effective a given precis…

Thanks folks for the great links and articles related to the question - very helpful!

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

#48

Post by NamTaf » Tue, Feb 19, 2019, 4:36 AM UTC

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.

Maybe I'm missing something fundamental but it seems more complex than need be, especially for small areas where the distortion of showing a sphere on a Mercator projection is minimal.

edit: Never mind, another comment answered why: This generates a random but not uniform (in area) distribution, because there's a larger circumference (and thus more swept area for a given radial angle) the larger the radius moves out.

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

#49

Post by londons_explore » Tue, Feb 19, 2019, 7:43 AM UTC

jordinl wrote: post #27

agwa wrote: post #24

Earlier quoted context omitted.

Is the pseudo-random number generator cryptographically secure?

Every set of coordinates uses a different seed, so I would say yes.

Not if there is more entropy in the coordinates than the seed...

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

#50

Post by MRD85 » Tue, Feb 19, 2019, 7:00 PM UTC

Misdicorl wrote: post #37

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...

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.