Sampling uniformly distributed random points inside a spherical volume

Question

I am looking to be able to generate a random uniform sample of particle locations that fall within a spherical volume.

The image below (courtesy of http://nojhan.free.fr/metah/) shows what I am looking for. This is a slice through the sphere, showing a uniform distribution of points:

This is what I am currently getting:

You can see that there is a cluster of points at the center due to the conversion between spherical and Cartesian coordinates.

The code I am using is:

def new_positions_spherical_coordinates(self):
   radius = numpy.random.uniform(0.0,1.0, (self.number_of_particles,1)) 
   theta = numpy.random.uniform(0.,1.,(self.number_of_particles,1))*pi
   phi = numpy.arccos(1-2*numpy.random.uniform(0.0,1.,(self.number_of_particles,1)))
   x = radius * numpy.sin( theta ) * numpy.cos( phi )
   y = radius * numpy.sin( theta ) * numpy.sin( phi )
   z = radius * numpy.cos( theta )
   return (x,y,z)

Below is some MATLAB code that supposedly creates a uniform spherical sample, which is similar to the equation given by http://nojhan.free.fr/metah. I just can't seem to decipher it or understand what they did.

function X = randsphere(m,n,r)

% This function returns an m by n array, X, in which 
% each of the m rows has the n Cartesian coordinates 
% of a random point uniformly-distributed over the 
% interior of an n-dimensional hypersphere with 
% radius r and center at the origin.  The function 
% 'randn' is initially used to generate m sets of n 
% random variables with independent multivariate 
% normal distribution, with mean 0 and variance 1.
% Then the incomplete gamma function, 'gammainc', 
% is used to map these points radially to fit in the 
% hypersphere of finite radius r with a uniform % spatial distribution.
% Roger Stafford - 12/23/05

X = randn(m,n);
s2 = sum(X.^2,2);
X = X.*repmat(r*(gammainc(s2/2,n/2).^(1/n))./sqrt(s2),1,n);

I would greatly appreciate any suggestions on generating a truly uniform sample from a spherical volume in Python.

There seem to be plenty of examples showing how to sample from a uniform spherical shell, but that seems to be easier an easier problem. The issue has to do with the scaling - there should be fewer particles at a radius of 0.1 than at a radius of 1.0 to generate a uniform sample from the volume of the sphere.

Edit: Fixed and removed the fact I asked for normally and I meant uniform.

Answer 1

While I prefer the discarding method for spheres, for completeness I offer the exact solution.

In spherical coordinates, taking advantage of the sampling rule:

phi = random(0,2pi)
costheta = random(-1,1)
u = random(0,1)

theta = arccos( costheta )
r = R * cuberoot( u )

now you have a (r, theta, phi) group which can be transformed to (x, y, z) in the usual way

x = r * sin( theta) * cos( phi )
y = r * sin( theta) * sin( phi )
z = r * cos( theta )

Answer 2

There is a brilliant way to generate uniformly points on sphere in n-dimensional space, and you have pointed this in your question (I mean MATLAB code).

Why does it work? The answer is: let us look at the probability density of n-dimensional normal distribution. It is equal (up to constant)

exp(-x_1*x_1/2) *exp(-x_2*x_2/2)... = exp(-r*r/2), so it doesn't depend on the direction, only on the distance! This means, after you normalize vector, the resulting distribution's density will be constant across the sphere.

This method should be definitely preferred due to it's simplicity, generality and efficiency (and beauty). The code, which generates 1000 events on the sphere in three dimensions:

size = 1000
n = 3 # or any positive integer
x = numpy.random.normal(size=(size, n)) 
x /= numpy.linalg.norm(x, axis=1)[:, numpy.newaxis]

BTW, the good link to look at: http://www-alg.ist.hokudai.ac.jp/~jan/randsphere.pdf

As for having uniform distribution within a sphere, instead of normalizing a vector, you should multiply vercor by some f(r): f(r)*r is distributed with density proportional to r^n on [0,1], which was done in the code you posted

Answer 3

Generate a set of points uniformly distributed within a cube, then discard the ones whose distance from the center exceeds the radius of the desired sphere.

Answer 4

I agree with Alleo. I translated your Matlab code to Python and it can generate thousands of points very fast (a fraction of second in my computer for 2D and 3D). I've even ran it for up to 5D hyperspheres. I found your code so useful that I'm applying it in a study. Tim McJilton, who should I add as reference?

import numpy as np
from scipy.special import gammainc
from matplotlib import pyplot as plt
def sample(center,radius,n_per_sphere):
    r = radius
    ndim = center.size
    x = np.random.normal(size=(n_per_sphere, ndim))
    ssq = np.sum(x**2,axis=1)
    fr = r*gammainc(ndim/2,ssq/2)**(1/ndim)/np.sqrt(ssq)
    frtiled = np.tile(fr.reshape(n_per_sphere,1),(1,ndim))
    p = center + np.multiply(x,frtiled)
    return p

fig1 = plt.figure(1)
ax1 = fig1.gca()
center = np.array([0,0])
radius = 1
p = sample(center,radius,10000)
ax1.scatter(p[:,0],p[:,1],s=0.5)
ax1.add_artist(plt.Circle(center,radius,fill=False,color='0.5'))
ax1.set_xlim(-1.5,1.5)
ax1.set_ylim(-1.5,1.5)
ax1.set_aspect('equal')

Answer 5

Normed gaussian 3d vector is uniformly distributed on sphere, see http://mathworld.wolfram.com/SpherePointPicking.html

For example:

N = 1000
v = numpy.random.uniform(size=(3,N)) 
vn = v / numpy.sqrt(numpy.sum(v**2, 0))

Answer 6

Would this be uniform enough for your purposes?

In []: p= 2* rand(3, 1e4)- 1
In []: p= p[:, sum(p* p, 0)** .5<= 1]
In []: p.shape
Out[]: (3, 5216)

A slice of it

In []: plot(p[0], p[2], '.')

looks like:

Answer 7

import random
R = 2

def sample_circle(center):
    a = random.random() * 2 * np.pi
    r = R * np.sqrt(random.random())
    x = center[0]+ (r * np.cos(a))
    y = center[1] + (r * np.sin(a))
    return x,y

ps = np.array([sample_circle((0,0)) for i in range(100)])

plt.plot(ps[:,0],ps[:,1],'.')
plt.xlim(-3,3)
plt.ylim(-3,3)
plt.show()

Answer 8

Function to Sample Uniformly from a Hypersphere

The function below uniformly samples points from a hypersphere:

import numpy as np
def sample(center, radius, n_samples, seed=None):

    # initial values
    d = center.shape[0]

    # sample n_samples points in d dimensions from a standard normal distribution
    rng = np.random.default_rng(seed)
    samples = rng.normal(size=(n_samples, d))

    # make the samples lie on the surface of the unit hypersphere
    normalize_radii = np.linalg.norm(samples, axis=1)[:, np.newaxis]
    samples /= normalize_radii

    # make the samples lie inside the hypersphere with the correct density
    uniform_points = rng.uniform(size=n_samples)[:, np.newaxis]
    new_radii = np.power(uniform_points, 1/d)
    samples *= new_radii

    # scale the points to have the correct radius and center
    samples = samples * radius + center
    return samples

This code works as follows.

First, it first generates n datapoints in d dimensions from a standard normal distribution. We specifically sample from a normal distribution because normal distributions are isotropic, meaning it is uniform in all orientations. This works great for creating a hypersphere where must be uniform/the same in all orientations.

Second, it computes the radius of each datapoint with np.linalg.norm(). (Note: np.linalg.norm() calls the Euclidean norm which equals the radius because r^2 = x^2 + y^2 in 2D and more generally r^2 = \sum_{i=1}^d x_i^2 which is the equation for Euclidean distance.) It divides each point by its radius to normalize the radius to length 1. This is equivalent to making all the datapoints lie on the surface of the unit hypersphere with radius r=1.

Third, it creates a new radius for each of the n_samples datapoints by generating n_samples points from a uniform distribution and then taking the dth root of each of these points. Why do we do this? Consider the 2D case where we want to sample points uniformly on a circle. If we divide this circle into concentric rings, then the ring right by the circle's center will have few points on it while the ring by the circumference will have many more points on it. More generally, the larger the radius, the more points we will need to generate. More precisely, achieving uniform sampling across radii of varying lengths requires a probability distribution proportional to the D-th power of the radius r. We can express this as F(r) \alpha r^d where F(r) is the number of points radius r away from the origin that give us a uniform distribution. We begin with a uniform distribution of points in uniform_points and can rearrange the equation above as F(r)^{1\d} \alpha r, meaning we must take the dth root of the uniformly distributed radii.

Fourth, this code scales all the points on the surface of the unit hypersphere by this new radius, distributing these points uniformly across the volume of the hypersphere. It then shifts these points over to have the desired center.

Function Performance

My code is much faster than @Daniel's code which relies upon scipy's gammainc function which is quite expensive to evaluate. I benchmark the performance here:

def time_it():

    # initial values
    d = 20
    center, radius = np.full(d, 2), 3
    n_samples_list = np.logspace(3, 6, num=10).astype(int)
    runtime_my_code, runtime_daniel_code = [], []

    for n_samples in n_samples_list:

        # time my code
        start = time.perf_counter()
        sample_hypersphere_uniformly(center, radius, n_samples)
        end = time.perf_counter()
        duration = end - start
        runtime_my_code.append(duration)

        # time Daniel's code
        start = time.perf_counter()
        daniels_code(center, radius, n_samples)
        end = time.perf_counter()
        duration = end - start
        runtime_daniel_code.append(duration)

    # plot the results
    fig, ax = plt.subplots()
    ax.scatter(n_samples_list, runtime_my_code)
    ax.scatter(n_samples_list, runtime_daniel_code)
    ax.plot(n_samples_list, runtime_my_code, label='my code')
    ax.plot(n_samples_list, runtime_daniel_code, label='daniel\'s code')
    ax.set(xlabel='n_samples',
        ylabel='runtime (s)', title='runtime VS n_samples')
    plt.legend()
    fig.savefig('runtime_vs_n_samples.png')

This diagram makes it clear that my code is much more efficient than Daniel's.

Other resources

Check out this helpful guide to sampling from a hypersphere here. It clearly explains why this math works.

Answer 9

import numpy as np
import matplotlib.pyplot as plt





r= 30.*np.sqrt(np.random.rand(1000))
#r= 30.*np.random.rand(1000)
phi = 2. * np.pi * np.random.rand(1000)



x = r * np.cos(phi)
y = r * np.sin(phi)


plt.figure()
plt.plot(x,y,'.')
plt.show()

this is what you want

Answer 10

You can just generate random points in spherical coordinates (assuming that you are working in 3D): S(r, θ, φ ), where r ∈ [0, R), θ ∈ [0, π ], φ ∈ [0, 2π ), where R is the radius of your sphere. This would also allow you directly control how many points are generated (i.e. you don't need to discard any points).

To compensate for the loss of density with the radius, you would generate the radial coordinate following a power law distribution (see dmckee's answer for an explanation on how to do this).

If your code needs (x,y,z) (i.e. cartesian) coordinates, you would then just convert the randomly generated points in spherical to cartesian coordinates as explained here.