6 ms·
How to generate random geo-coordinates within a given radius
- chad_thunder 8y agoBuffer your point to create a polygon then use ST_PointOnSurface (or equivalent) in any competent spatially-enabled DBMS to create a point guaranteed to intersect the bounding polygon. Trivial in SQLite, PostGIS, etc.
- Cyph0n 8y agoGIS buffer polygons were magical when I first stumbled upon them.
- chad_thunder 8y agoSomething wrong with them nowadays?
- platz 8y agohow is that generated point random in any way? https://gis.stackexchange.com/questions/76498/how-is-st-pointonsurface-calculated https://gis.stackexchange.com/questions/76498/how-is-st-poin...
- mtmail 8y agoI regularly use this tool (nodejs) for a list of random coordinates inside a country. Or at least inside any country to avoid the oceans. https://github.com/tsamaya/random-points-generator https://github.com/tsamaya/random-points-generator
- femto113 8y agoIf the rationale is privacy this is probably not the algorithm you want to use, especially if it's possible to force the generation of multiple random points (e.g. by refreshing the map). If you're using a circle with a fixed radius just 3 points would be enough to exactly locate the center. A variable radius could take more, but since the distribution is uniform each additional point would significantly improve the precision.
- ape4 8y agoI imagine its for something like AirBnb where the site doesn't want the users to the location the property so they only way to book it is via the site.
- jeromegv 8y agoWhat's funny with Airbnb is that if you are looking at the map in search, it is approximate. However, if you save the property to your favorites and then go to your favorite list and look at the map, you get the exact location.
- jonathanyc 8y agoSome Airbnb engineer just got pinged...
- GranPC 8y agoCould not reproduce. I tested with different properties and while it shows as an exact location in the map, it is still being fuzzed.
- WrtCdEvrydy 8y agoIf you used a fingerprinting library as the seed for random, it would be repeatable per user.
- jordinl 8y agoAs I mentioned in a different comment, we used a slightly modified version of the code in the article. Instead of using random numbers we used pseudo-random numbers so the positions didn't change across requests.
- tzs 8y ago> 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 property location by querying that map a bunch of times and averaging the positions returned? 2. Are there any negative consequences for the people whose property a displaced marker ends up on? For example, if someone is using the map lookup to find the home of a rival gang officer in order to do a drive by attack, and I happen to live down the street, I really don't want that marker showing up on my house. Rather than a displaced marker, maybe divide the map into rectangular or hexagonal regions, and just highlight the region containing the property.
- deleted 8y ago[deleted]
- deleted 8y ago[deleted]
- curiousgal 8y agoAmusingly, this is the first time that I've seen the Law of Large Numbers being treated as a negative thing.
- jordinl 8y agoWe used a slightly modified version of the code in the article. Instead of using random numbers we used pseudo-random numbers so the positions didn't change across requests.
- usrusr 8y agoAny 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/alternative per point so that there cannot be multiple observations. If for some reason the data needs to appear randomized between repeated lookups, you need to store a fixed offset/alternative per point and then apply an additional random offset per lookup. Repeated lookups will only leak the (badly) hidden permanently randomized stored alternative.
- unterbahn 8y agoLeaflet.BlurredLocation https://github.com/publiclab/leaflet-blurred-location https://github.com/publiclab/leaflet-blurred-location
- deleted 8y ago[deleted]
- iknowordidthat 8y agoOver 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 on a circle. Sure, it won’t be accurate for large distances but that is not a requirement. Nor is accuracy for that matter since the whole point is to obfuscate the original point.
- chaoticmass 8y agoI wrote an app where we needed to get a list of properties within a radius of a given property, using lat/long coordinates. Given the search radius would be at most 5 miles, and didn't need to be 100% precise, I just treated the surface as a plane. A trivial solution to a trivial problem-- but it is neat to know the details of the formula for doing it precisely should I ever need it.
- marcinzm 8y agoI 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.
- MaxBarraclough 8y agoThis 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_curve&oldid=881535925#Properties https://en.wikipedia.org/w/index.php?title=Space-filling_cur...
- dang 8y agoThis is a fine submission but can you please not put "Show HN" on blog posts? This is in the rules: https://news.ycombinator.com/showhn.html https://news.ycombinator.com/showhn.html.
- jordinl 8y agoAh, sorry I missed that...
- MRD85 8y agoWhy 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-location-a-bit-private/ https://robertheaton.com/2018/07/09/how-tinder-keeps-your-lo...
- alanbernstein 8y agoThat might work if you then apply a translation to the center point in pixel-space. But what if you need to send latitude and longitude to your front-end, or other display system? How do you translate your 2d polar coordinates to a change in spherical polar coordinates (lat+lon)? For small distances near the equator, it may not matter. Otherwise, it might. The article could have helped answer your question by providing some images to illustrate the flaws with other solutions that the author tried.
- apcragg 8y agoThat doesn't create a uniform distribution over a disk. Heres a quick image (https://imgur.com/a/xHEpVB9 https://imgur.com/a/xHEpVB9) I generated using that method.
- Misdicorl 8y agoThis 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.
- MRD85 8y agoThanks, makes perfect sense and should have been obvious.
- MRD85 8y agoI 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.
- jimsmart 8y agoConverting 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 https://github.com/uber/h3 [2] https://eng.uber.com/h3/ https://eng.uber.com/h3/
- GhostVII 8y agoIn 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.
- NamTaf 8y agoAs 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.
- MaxBarraclough 8y agoA 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 https://news.ycombinator.com/item?id=19193622
- NamTaf 8y agoThat’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.
- 8y ago
- unterbahn 8y agoLeaflet.BlurredLocation https://github.com/publiclab/leaflet-blurred-location 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.
- unterbahn 8y agoThanks folks for the great links and articles related to the question - very helpful!