Friday, March 27, 2015

Easy random point in sphere

Often you need a uniform random point in a sphere.   There are good methods for doing that that have deterministic runtime and good stratification and all that, but usually you just want something easy that works, and rejection sampling is usually the way to go.    Usually you take a larger domain than the target one and repeatedly "throw darts" until one hits the target.
First let's do this in 2D with a circle at center c = (xc, yc) and radius R.  Now let's assume we have a random number generator r() that returns floats in [0,1) (like drand48() in most C environments or Math.random() in Java).

do {  // pick random point insquare until it is inside the circle
      x = xc - R + 2*R*r()
      y = yc - R + 2*R*r()
} while (sqr(x - xc) + sqr(y - yc) > sqr(R))

For 3D, the extension is just the dimension add:

do {  // pick random point in cube until it is inside the sphere
      x = xc - R + 2*R*r()
      y = yc - R + 2*R*r()
      z = zc - R + 2*R*r()
} while (sqr(x - xc) + sqr(y - yc) + sqr(z- zc) > sqr(R))


1 comment:

Eric Haines said...

Yeah, this is my favorite lame way to get random points in a sphere. It also works for random points on a circle or sphere: take the resulting point and normalize (throw out the extremely rare point that lands at the exact center).