Hacker News Reader

Comment by egorfine | Hacker News Reader

Please forgive me my naivete, but won't generating two random polar coordinates do? I'm bad at math, so I might as well be very very wrong here, but I'd like to know.

Edit: see @srean's excellent explanation why that won't do.

View on HN

If you want uniformly random on the spherical surface then uniformly at random in polar coordinates will not cut it.

To appreciate why, consider strips along two constant latitudes. One along the Equator and the other very close to the pole. The uniformly random polar coordinates method will assign roughly the same number points to both. However the equatorial strip is spread over a large area but the polar strip over a tiny area. So the points will not be uniformly distributed over the surface.

What one needs to keep track of is the ratio between the infinitesimal volume in polar coordinates dphi * dtheta to the infinitesimal of the surface area. In other words the amount of dilation or contraction. Then one has apply the reciprocal to even it out.

This tracking is done by the determinant of the Jacobian.

Looking at Jacobians is the general method but one can rely on an interesting property: not only is the surface area of a sphere equal to the surface area of a cylinder tightly enclosing it (not counting end caps), but if you take a slice of this cylinder-with-sphere-inside, the surface area of the part of the sphere will be equal to the surface area of the shorter cylinder that results from the cutting.

This gives an algorithm for sampling from a sphere: choose randomly from a cylinder and then project onto a sphere. In polar coordinates:

  sample theta uniformly in (0,2pi)
  sample y uniformly in (-1,1)
  project phi = arcsin(y) in (-pi,pi)
  polar coordinates (theta, phi) define describe random point on sphere

Potentially this is slower than the method in the OP depending on the relative speeds of sqrt and arcsin.

That's a neat approach! So basically something like this: https://editor.p5js.org/spyrja/sketches/eYt7H36Ka

This seems more like a random point on a spiral on the sphere. There was a thing on hn about spirals on a sphere few days ago.

Ah, good catch. I forgot to scale the point properly! How does the updated sketch look?

EDIT: Plotting it out as a point cloud seems to confirm your suspicion.

Without scaling: https://editor.p5js.org/spyrja/sketches/7IK_RssLI

Scaling fixed: https://editor.p5js.org/spyrja/sketches/kMxQMG0dj

Ah neat ! It never occurred to me -- the connection with Archimdedes' result. He certainly considered it to be his best.

This is now crystal clear and obvious to me, thank you very much for the great explanation!

Happy to help.

I think this 2D version shows the issue clearly

https://mathworld.wolfram.com/DiskPointPicking.html

I think it can be done that way yeah but in order to yield a uniform-density of points on the surface of the sphere there's some pre-correction (maybe a sqrt or something? I can't remember) that's needed before feeding the 'uv' values to the trig functions to make 3D positions. Otherwise points will 'bunch up' and be more dense at the poles I think.

Indeed.

One way to fix the problem is to sample uniformly not on the latitude x longitude rectangle but the sin (latitude) x longitude rectangle.

The reason this works is because the area of a infinitesimal lat long patch on the sphere is dlong x lat x cosine (lat). Now, if we sample on the long x sin(lat) rectangle, an infinitesimal rectangle also has area dlong x dlat x d/dlat sin(lat) = dlong x dlat cos (lat).

Unfortunately, these simple fixes do not generalize to arbitrary dimensions. For that those that exploit rotational symmetry of L2 norm works best.

Yes, see https://news.ycombinator.com/item?id=45001593

Generating two random 1..360 numbers and converting them to xyz would bunch up at the poles?

Yeah @srean gives the example of the different areas of strips at different lattitude, that's a good one - and I think if you imagine wrapping the unit square (2 values randomly between 0 and 1) to a sphere in a lat-long way, the whole top and bottom edges of the square get contracted to single points at the top and bottom latitude locations (respectively) on the sphere.. so if the point density was uniform going into that then it surely won't be afterwards ;)

See @srean's explanation above.

Yes, that does work basically. See https://news.ycombinator.com/item?id=45001593

i feel somehow three rotations should be able to do it, 3 rands between 0 and 2pi.

Reply on news.ycombinator.com