CODEWITHSUNDEEP
math
Some1Else
Some1Else

Reputation: 795

Distributing points evenly spaced within a sphere

I am looking for an algorithm to distribute a bunch of points (could be anywhere from a few hundred to millions) within a sphere. In this case the sphere is centered at (0,0,0).

For random points a simple method is

repeat
    x:=random*diameter-radius;
    y:=random*diameter-radius;
    z:=random*diameter-radius;
until ((x*x+y*y+z*z)<(radius*radius));

But I want to get the points evenly spaced within the sphere and without bunching at the poles.

Any good tricks/algorithms/formulas/code snippet to accomplish this?

Upvotes: 1

Views: 3476

Answers (3)

Avishek Kumar_IITGN
Avishek Kumar_IITGN

Reputation: 1

Thanks for the explanation by joriki. The above formula has been explained in proof of the formula mentioned. But the formula has some limitations. The cube length can be 2 (-1 to 1 in all directions). From the above concept, mentioned by joriki or proof of the formula mentioned we can generalize for the cube of any length (i.e 2a (-a to a in all directions)). Here 2a is the side length of the cube.

$a^6-(a^2-x^2 )(a^2-y^2)(a^2-z^2)=x^2 a^2 (a^2-\frac{z^2}{2}-\frac{y^2}{2}+\frac{y^2 z^2}{3a^2})+y^2 a^2 (a^2-\frac{z^2}{2}-\frac{x^2}{2}+\frac{x^2 z^2}{3a^2})+z^2 a^2 (a^2-\frac{x^2}{2}-\frac{y^2}{2}+\frac{y^2 x^2}{3a^2})$

$x'=xa \sqrt{a^2-\frac{z^2}{2}-\frac{y^2}{2}+\frac{y^2 z^2}{3a^2}}$,

$y'=ya \sqrt{a^2-\frac{z^2}{2}-\frac{x^2}{2}+\frac{x^2 z^2}{3a^2}}$,

$z'=za \sqrt{a^2-\frac{x^2}{2}-\frac{y^2}{2}+\frac{y^2 x^2}{3a^2}}$,

From the above equation, we can easily separate the (x',y',z') as explained in 1. The above equation will readily find the mapping of the generalized length of the cube to a sphere. I hope this will be helpful.

Form the above equation we can also find the evenly distribution of points within the sphere by varying the grid size of the cube. By discretizing the cube into different grids and simultaneously mapping into the sphere will give the evenly distribution of points within the sphere.

Kindly ignore some typos.

C++ code for evenly distributing points within the sphere:-

for(x=-a;x<=a;x=x+n)
for(y=-a;y<=a;y=y+n)
{
    for(z=-a;z<=a;z=z+n)
    {
        xnew=x*a*(sqrt((a*a)-(y*y)/(2)-(z*z)/(2)+(y*y*z*z)/(3*a*a)));
        ynew=y*a*(sqrt((a*a)-(z*z)/(2)-(x*x)/(2)+(x*x*z*z)/(3*a*a)));
        znew=z*a*(sqrt((a*a)-(x*x)/(2)-(y*y)/(2)+(y*y*x*x)/(3*a*a)));
        cout<<" "<<xnew<<" "<<ynew<<" "<<znew<<endl;
        }
}
    }

Note:- Here in code, n is the grid size of a cube.

Upvotes: 0

MBo
MBo

Reputation: 80325

If you need evenly spaced points - just place them in grid nodes.

Sphere with radius R has volume 

 V=4/3*Pi*R^3

so for placing N points every cell of cubic grid (perhaps you might want to use hexagonal close packing) should have volume 

v=4/3*Pi*R^3/N

and edge length 

l = R * (4*Pi/(3*N))^1/3

Then generate points in coordinates (a*l, b*l, c*l) where a,b,c are integers limited by -R..+R (with appropriate sum of squares).

Proposed approach is quite rough estimation and perhaps some points from N needed ones might run outside of the sphere. In this case one have to diminish cell size or use more exact value - it might be calculated using 3D analog of Gauss circle formula ()

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59368

You could do something like this:

  • Put the center of your sphere at a random position within an infinite volume of evenly-spaced points, like a tetrahedral or cubic lattice.

  • Enumerate points in order of increasing distance from the center until you have the right number.

  • Rescale the selected points around the center so that the distance to the furthest point is equal to the desired radius.

Upvotes: 2

Related Questions