Algorithm for placing points evenly inside sphere

2
votes

If I have a sphere with center (x,y,z) and radius r, do an algorithm exist for placing X number of points (x,y,z) inside the sphere in such as way that the minimal distance to each other point is maximized?

E.g. one points would simply be placed in the middle, two points would be placed on the opposite borders, three points would be placed in a "triangle" formation on the border and so on.

As have been pointed out, an equal distance to each other point cannot be found for every number of points. The requirement is therefore to maximize the minimal distance between the points.

Update:

The following code generates points inside a sphere with radius 1.0, but does not maximize the distance.

function getPoint() {
    var d, x, y, z;
    do {
        x = Math.random() * 2.0 - 1.0;
        y = Math.random() * 2.0 - 1.0;
        z = Math.random() * 2.0 - 1.0;
        d = x*x + y*y + z*z;
    } while(d > 1.0);
    return {x: x, y: y, z: z};
}

I think I need some kind of iteration afterwards. I have tried to apply a force model using the n-body problem as inspiration, and while fun to watch, it didn't really work that well.

4
algorithm3dgeometry
Tetrahedral lattice? - meowgoesthedog
What do you mean by "simultaneously maximizing the number of space occupied"? - coproc
Do you accept a random uniform placement or only a lattice ? - Yves Daoust
Given 4 points the solution is a tetrahedron inscribed into the sphere. But for 5 or more points there is no solution in 3D where all pairs of distinct points have the same distance (like there is no solution for 4 or more points in 2D). Do you want to maximize the minimal distance between distinct points? - coproc
You're right, that's a better explanation. - MortenGR

4 Answers

0
votes

For a random but uniform placement, draw uniform random points in the bounding cube of the sphere and accept those that are inside the sphere. stop when you have enough points.

If you want a regular arrangement, the question is much more difficult.

0
votes

For a random point uniformly distributed inside the unit sphere with cylindrical coordinates (r,phi,z) we have

           int[0,x] 2*r*pi*2*sqrt(1-r^2) dr
P(r < x) = -------------------------------- = 1 - (1-x^2)^(3/2) =: F(x), x in [0,1]
                        4*pi/3

The inverse function F^-1(r) = sqrt(1-(1-r)^(2/3)) transforms a random variable U uniformly distributed in [0,1] into a random variable distributed as r above. Since 1-U has the same distribution as U we can use the simpler function sqrt(1-r^(2/3)).

The other components phi and z of the cylindrical coordinates are uniformly distributed in the respective ranges.

Thus we get Python code for direct generation of points equally distributed inside a sphere like this:

import math, random

def randomUnitSpherePoint():
    # cylindrical coordinates
    rxy = math.sqrt(1 - random.uniform(0, 1)**(2./3.))
    phi = random.uniform(0, 2*math.pi)
    zAbsMax = math.sqrt(1 - rxy*rxy)
    z = random.uniform(-zAbsMax, zAbsMax)
    # cartesian coordinates
    x,y = rxy*math.cos(phi), rxy*math.sin(phi)
    return x,y,z

def randomSpherePoint(center, radius):
    x,y,z = randomUnitSpherePoint()
    return center[0] + r*x, center[1] + r*y, center[2] + r*z

Note: the "standard" solution (generating random points inside the bounding box and selecting points inside the sphere) is usually more efficient, especially when using a pseudo random number generator.

0
votes

The problem is closely related to packing identical spheres into a unit sphere (maybe the two problems are even equivalent): having a solution of a packing of n spheres with radius r into a unit sphere, all sphere centers are inside a sphere with radius 1-r and have a distance of at least 2r. So a solution for packing identical spheres into a unit sphere can easily be transformed to a solution to your problem.

Proven optimal solutions for packing identical spheres into a sphere only exist up to n=12. So I guess you will also have to live with near-optimal solutions, at least for n>12. The currently best known algorithm in terms of optimality seems to be Serial Symmetrical Relocation Algorithm for the Equal Sphere Packing Problem.

0
votes

Just an update because I forgot about this question:

Since the uniform approach was good enough for more than 100 points, and since someone had calculated the points positions on a sphere from 1 to 99 points, the solution was to lookup the position for [1:100] or else generate the points with a evenly distribution.