3 ms·

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 th

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 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 ago
I 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 ago
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.
- MaxBarraclough 8y ago
  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_curve&oldid=881535925#Properties https://en.wikipedia.org/w/index.php?title=Space-filling_cur...
  - MaxBarraclough 8y ago
    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.
ummonk 8y ago
Yeah, and it doesn't even need to be within a certain radius - just make it within a certain latitude / longitude.
X6S1x6Okd1st 8y ago
Seems like another option is to generate points inside a bounding square and throw them away if they are outside of the circle.
MertsA 8y ago
>calculate points on a circle This is a bad idea. If you don't randomly distribute points within the entire radius then you've just narrowed the search space for the real location from the entire area in the radius to just a circle around the point you give back.

chaoticmass 8y ago

I 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 ago

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.

MaxBarraclough 8y ago
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_curve&oldid=881535925#Properties https://en.wikipedia.org/w/index.php?title=Space-filling_cur...
- MaxBarraclough 8y ago
  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.

ummonk 8y ago

Yeah, and it doesn't even need to be within a certain radius - just make it within a certain latitude / longitude.

X6S1x6Okd1st 8y ago

Seems like another option is to generate points inside a bounding square and throw them away if they are outside of the circle.

MertsA 8y ago

>calculate points on a circle This is a bad idea. If you don't randomly distribute points within the entire radius then you've just narrowed the search space for the real location from the entire area in the radius to just a circle around the point you give back.