Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a sphere of radius $R_{s}$, and I would like to pick random points in its volume with uniform probability. How can I do so while preventing any sort of clustering around poles or the center of the sphere?


Since I'm unable to answer my own question, here's another solution:

Using the strategy suggested by Wolfram MathWorld for picking points on the surface of a sphere: Let $\theta$ be randomly distributed real numbers over the interval $[0,2\pi]$, let $\phi=\arccos(2v−1)$ where $v$ is a random real number over the interval $[0,1]$, and let $r=R_s (\mathrm{rand}(0,1))^\frac13$. Converting from spherical coordinates, a random point in $(x,y,z)$ inside the sphere would therefore be: $((r\cos(\theta)\sin(\phi)),(r\sin(\theta)\sin(\phi)),(r\cos(\phi)))$.

A quick test with a few thousand points in the unit sphere appears to show no clustering. However, I'd appreciate any feedback if someone sees a problem with this approach.

share|improve this question
    
Summary: Nate proposed a transformation method, while Kevin proposed a rejection method. –  J. M. Dec 1 '11 at 3:08
    
I think the solution you took from MathWorld is sound, if a bit slower than the approaches proposed in the answer (evaluating transcendental functions is expensive!). –  J. M. Dec 1 '11 at 3:58
    
I don't know much but, my approach would be something along the lines of choosing a random pole from the surface to the center and then choosing a point on that line where the probability is greater the closer to the surface, to account for the expansion of the sphere. –  Sebastian Garrido Dec 10 '13 at 20:17
add comment

4 Answers

up vote 17 down vote accepted

Let's say your sphere is centered at the origin $(0,0,0)$.

For the distance $D$ from the origin of your random pointpoint, note that you want $P(D \le r) = \left(\frac{r}{R_s}\right)^3$. Thus if $U$ is uniformly distributed between 0 and 1, taking $D = R_s U^{1/3}$ will do the trick.

For the direction, a useful fact is that if $X_1, X_2, X_3$ are independent normal random variables with mean 0 and variance 1, then $$\frac{1}{\sqrt{X_1^2 + X_2^2 + X_3^2}} (X_1, X_2, X_3)$$ is uniformly distributed on (the surface of) the unit sphere. You can generate normal random variables from uniform ones in various ways; the Box-Muller algorithm is a nice simple approach.

So then $$\frac{R_s U^{1/3}}{\sqrt{X_1^2 + X_2^2 + X_3^2}} (X_1, X_2, X_3)$$ would produce a uniformly distributed point inside the ball of radius $R_s$.

share|improve this answer
    
This also generalizes to the $n$-sphere (with $D = R_s U^{1/n}$). –  Michael Lugo Dec 1 '11 at 4:58
add comment

An alternative method in $3$ dimensions:

Step 1: Take $x, y, $ and $z$ each uniform on $[-r_s, r_s]$.

Step 2: If $x^2+y^2+z^2\leq r_s^2$, stop. If not, throw them away and return to step $1$.

Your success probability each time is given by the volume of the sphere over the volume of the cube, which is about $0.52$. So you'll require slightly more than $2$ samples on average.

If you're in higher dimensions, this is not a very efficient process at all, because in a large number of dimensions a random point from the cube is probably not in the sphere (so you'll have to take many points before you get a success). In that case a modified version of Nate's algorithm would be the way to go.

share|improve this answer
add comment

Nate and Kevin already answered the two I knew... Recalling this and this, I think that another way to generate a uniform distribution over the sphere surface would be to generate a uniform distribution over the vertical cylinder enclosing the sphere, and then project horizontally.

That is , generate $z \sim U[-R,R]$, $\theta \sim U[0,2\pi]$, and then $x=\sqrt{R^2-z^2} \cos(\theta)$, $y=\sqrt{R^2-z^2} \sin(\theta)$. This (if I'm not mistaken) gives a uniform distribution over the sphere surface. Then, apply Nate's recipe to get a uniform distribution over the sphere volume.

This method is a little simpler (and more efficient) than the accepted answer, though it's not generalizable to other dimensions.

share|improve this answer
2  
In case it isn't immediately clear to people, this method works because of Archimedes' theorem on slicing cylinders and spheres: mathworld.wolfram.com/ArchimedesHat-BoxTheorem.html –  Michael Lugo Dec 1 '11 at 5:00
    
I believe you need a factor of $\sqrt{R^2 - z^2}$ in the choice of $x$ and $y$, in order to be on the sphere's surface. –  Erik P. Feb 21 '13 at 15:57
    
@ErikP. Of course, you're right, I forgot to do the projection, I'd left the points over the cylinder surface. Fixed, thanks! –  leonbloy Feb 21 '13 at 18:23
add comment

I just want to add a small derivation to leonbloy's answer, which uses calculus instead of geometrical intuition. Changing from cartesian $(x,y,z)$ to spherical $(r,\theta,\phi)$ coordinates, we have for the volume element $$dx dy dz =r^2 \sin \theta ~ dr d\theta d\phi$$ The coordinates $(r,\theta,\phi)$ don't work for a uniform distribution because we still have a non-constant factor in front of $dr d\theta d\phi$. Therefore we introduce $$u=-\cos \theta \Rightarrow du= \sin \theta d\theta$$ $$\lambda=r^3/R^3 \Rightarrow d \lambda=\frac{3}{R^3}r^2dr$$ with which we obtain an expression with a constant pre-factor $$dx dy dz= \frac{R^3}{3} d\lambda du d\phi$$ The range of our variables is $\lambda \in [0,1], ~u \in [-1,1), \phi \in [0, 2\pi) $. Choosing those numbers uniformly we get cartesian coordinates

$$ \begin{align} x&=r \sin(\theta) \cos (\phi) =&R \lambda^{1/3} \sqrt{1-u^2}\cos(\phi)\\ y&=r \sin(\theta) \sin (\phi) =&R \lambda^{1/3} \sqrt{1-u^2}\sin(\phi) \\ z&=r \cos (\theta)=&R \lambda^{1/3} u \end{align} $$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.