# Generating points in a volume element of a sphere

I have a line going off the origin in a direction defined by angles $(\phi,\theta)$, the latter being the azimuthal angle. Around this line, I have a cone, which "heads off" in the same direction as the line, and has a certain opening angle $\alpha$ . The cone is cut up into a certain number of spherical sector layers of constant thickness, and an arbitrary density function describes how many points should be generated in each of these sectors.

Sorry for the long setup. Now, I have a difference of two spherical sectors, which is pointed in a direction $(\phi,\theta)$, whose smaller end is facing the origin, and whose edges form an angle $\alpha$. I want to generate $N$ points uniformly within it.

I first tried the naïve, wrong method, which was uniformly distributing all their coordinates, as in $\phi-\alpha/2<\phi_{point}<\phi+\alpha/2$, repeating the same for $\theta$, and keeping the distance from the origin between the top and bottom ends of the frustrum.

• I don't get if you want to simulate a uniform distribution over a conical frustum or over the difference of two spherical sectors. – Jack D'Aurizio Jul 8 '15 at 14:07
• You have a point. I guess my usage of the term "frustrum" was misguided. I am looking at the difference of two spherical sectors. – toasty Jul 8 '15 at 14:10
• Assuming I understood your problem in the right way, I proved it is enough to manipulate three indipendent random variables, uniformly distributed over $[0,1]$, to simulate a uniform distribution over the difference of two spherical sectors. – Jack D'Aurizio Jul 8 '15 at 15:10

Let $S$ be the set of points on a sphere that are at distance at most $d$ from the north pole, $O$ the centre of the sphere, $R$ its radius. Assume that you want to simulate a uniform distribution over the region given by digging a distance $h$ from $S$ towards $O$. Then it is sufficient to simulate a uniform distribution over $S$, then the radial distribution. About the first task: to simulate a uniform distribution over a disk, it is sufficient to simulate a uniform distribution for the angle, then the radial distribution for such a disk.

If we have a uniform distribution over the unit $2$-dimensional disk, the density function of the distance from the centre is supported on $[0,1]$ and given by $f(x)=2x$. So, if $A,B$ are two independent random variables uniformly distributed over $[0,1]$, $$\sqrt{A}\, e^{2\pi i B}$$ is a random point in the unit disk with respect to the uniform distribution.

Over the unit $3$-dimensional disk, the density function of the distance from the centre is supported on $[0,1]$ and given by $f(x)=3x^2$. That is the density of $\sqrt[3]{C}$, if $C$ is a uniformly distributed random variable over $[0,1]$.

Summarizing, to simulate a uniform distribution over our region we just need three independent random variables $A,B,C$ uniformly distributed over $[0,1],[0,1],[(R-h)^3,R^3]$.
$$d\sqrt{A}e^{2\pi i B}$$ is the point on $S$ from which we start digging, $\sqrt[3]{C}$ is the distance from the centre of the sphere we reach.

• That all seems correct to me. I'll have to try implementing it, and I'll get back to this board with results. Thanks a bunch! – toasty Jul 8 '15 at 15:17

Unless your cone is very flat (cone angle at apex near $\pi$,), then simply surrounding your frustum by a rectangular box, generating random points in the box, and retaining only those points inside the frustum, will work reasonably quickly:

Above I generated points in an upright frustum, which would then be easy to move out to wherever you desire in 3D.
(After OP clarification): Here is a paper on your problem (which I cannot access easily):

Stefanescu, Stefan V. "Generating uniform random points inside a cone." Monte Carlo Methods and Applications 6.2 (2000): 115-130. (Journal link.)

• I guess I have to provide some context. I need to optimize this process as much as possible, since it's within a program which is doing a bunch of other work-heavy stuff (simulating stars in the nearby Milky Way). So I worry a Monte-Carlo approach will not be efficient enough. – toasty Jul 8 '15 at 14:28
• Now that seems helpful. I'll try getting access to it. – toasty Jul 8 '15 at 14:53