Uniform grid of points on a sphere

[untarnished]

How can one create a uniform solid-angular distribution of vectors in 3D space from a common origin, or in other words a grid of points on the surface of a sphere wherein the points are equidistant from each other? Spherical polar coordinates/the latitude-longitude scheme is obviously not the ideal, as there is a higher concentration of grid points near the poles, compared to the equator.

 

[alan2]

I could be wrong but I think that, in general, it can't be done. I think that your problem is related to the existence of regular polyhedra. If you want to uniformly distribute n points on a sphere and there exists an n sided regular polyhedron then it can be done by inscribing the polyhedron in the sphere and projecting from the center of the sphere through the geometric center of each face to the surface of the sphere. If you get a ball and a marker it's pretty easy to convince yourself that it can't be done for n=3 or n=5 but can be done for n=4 or n=6. Maybe someone else is more familiar with this problem.

 

[mfb]

4, 6, 8, 12 and 20 points are easy with platonic solids - some other numbers might be possible with different polyhedra (but less symmetry), for example with archimedean solids.
If you need many (>>20), you could fill the faces of an icosahedron or some other shape with additional points and project them onto the surface of the sphere, this should give some reasonable approximation of a uniform distribution.
If you need something in between, it could be tricky. I wonder how the result of a numerical simulation of n repulsing objects would look like.

 

[untarnished]

Thanks for the responses. In principle I need an almost infinite number of points on my sphere. I just need to discretize it as finely, and as uniformly as possible.

While searching for an answer myself, I stumbled upon geodesic domes, and I realized that what I probably need is an algorithm that generates coordinates for a geodesic dome with a variable number of tiles. I guess I'm off to the library to get a book or two on creating geodesic domes -- but I obviously wouldn't mind if somebody knows an online resource that could help.

 

[cosmik debris]

I looked this up a while ago for a problem in placing cell phone towers and the only algorithm I could find was one using Simulated Annealing.

 

[alan2]

I forgot about this thread. I apologize for answering as if you were solving an exact geometric problem. For your problem I would still use spherical coordinates. To make it easy, suppose your radius is 1. Let θ=polar angle, ∅=azimuthal angle. Your problem in using uniformly generated random numbers is that the area of the infinitesimal "rectangle" on the surface defined by the changes dθ and d∅ is given by dA=sin∅d∅dθ. So if you randomly choose θ and ∅ you end up with concentrations of points inversely proportional to the area and thus more points concentrated near the poles in the "smaller rectangles". So you need to pick random numbers proportional to the size of the rectangles, i.e. generate random numbers proportional to sin∅. The cumulative distribution of sin∅ is F(∅)=1-cos∅. So you choose a random number u from a uniform distribution on [0,1] and find the inverse ∅=arccos(1-u). The resulting ∅ are random numbers distributed like sin∅. These ∅ should be uniformly distibuted on the sphere.

You can work out the details. You have an issue with the bottom half of the sphere because the range of arccos and the range of ∅ are different but you can take care of that easily. Check to make sure the distribution is normalized, etc. Try it, it should work.

 

[meldraft]

One way you could go about it would be to generate a point at an arbitrary point on the sphere, and then define a circle of certain radius around it. You then start generating a fixed number of points along the circle's circumference and generate new points on the circles defined by the new points and so on and so forth. I think that this will give you a reasonably uniform mesh since, by definition, at every neighborhood you would have a fixed number of points at fixed distances from each other. Hope this helps

 

[RMSimons]

Alan2,

I tried your method of modifying a uniform angle distribution according to the "rectangle size", though the results I got some strange results. (see projections onto orthogonal planes - attached)

I'm using Matlab and my code is

for polang=-pi:AngSpace:pi
for u=-1:USpace:1
azang=acos(u);
xmag=sin(polang)*cos(azang);
ymag=sin(polang)*sin(azang);
zmag=cos(polang);
if xmag>0.5
Dist=1000/xmag;
ypos=floor(2000+Dist*ymag);
zpos=floor(2000+Dist*zmag);
Imx(ypos,zpos)=Imx(ypos,zpos)+1;
end
if ymag>0.5
Dist=1000/ymag;
xpos=floor(2000+Dist*xmag);
zpos=floor(2000+Dist*zmag);
Imy(xpos,zpos)=Imy(xpos,zpos)+1;
end
if zmag>0.5
Dist=1000/zmag;
xpos=floor(2000+Dist*xmag);
ypos=floor(2000+Dist*ymag);
Imz(xpos,ypos)=Imz(xpos,ypos)+1;
end
end
end

Thanks

Rich

I forgot about this thread. I apologize for answering as if you were solving an exact geometric problem. For your problem I would still use spherical coordinates. To make it easy, suppose your radius is 1. Let θ=polar angle, ∅=azimuthal angle. Your problem in using uniformly generated random numbers is that the area of the infinitesimal "rectangle" on the surface defined by the changes dθ and d∅ is given by dA=sin∅d∅dθ. So if you randomly choose θ and ∅ you end up with concentrations of points inversely proportional to the area and thus more points concentrated near the poles in the "smaller rectangles". So you need to pick random numbers proportional to the size of the rectangles, i.e. generate random numbers proportional to sin∅. The cumulative distribution of sin∅ is F(∅)=1-cos∅. So you choose a random number u from a uniform distribution on [0,1] and find the inverse ∅=arccos(1-u). The resulting ∅ are random numbers distributed like sin∅. These ∅ should be uniformly distibuted on the sphere.

You can work out the details. You have an issue with the bottom half of the sphere because the range of arccos and the range of ∅ are different but you can take care of that easily. Check to make sure the distribution is normalized, etc. Try it, it should work.

 

[alan2]

Hi Rich,

Really old thread. I think you may have forgotten the attachment. I'm not too familiar with MATLAB and I'm having a hard time seeing how your code solves the problem. Regardless, I googled this problem and found this:

http://mathworld.wolfram.com/SpherePointPicking.html

Notice that the first method is based upon my geometric observation and is essentially the same but more elegant. The next to last method looks very cool to me but I would probably have to read the Cook paper to figure it out. The very last method due to Muller is very interesting in that it uniformly distributes unit normal vectors on the sphere instead of points.

 

[RMSimons]

Hi Alan, apologies for the missing attachments, it said they had uploaded. To be more clear:

Assuming a radius of 1

for theta=-pi:pi/1000:pi %set theta to count from -pi to pi at intervals of pi/1000
for u=-1:1/1000:1 %set U to count from -1 to 1 at intervals of 1/1000
phi=acos(u); % convert uniform U to cos distribution of phi
xmag=sin(theta)*cos(phi); %convert polar co-oridnates to cartesian vectors
ymag=sin(theta)*sin(phi);
zmag=cos(theta);
if xmag>0.5 %limit distribution to projection of 60° around x axis
Dist=1000/xmag; %count out steps to plane at 1000 distance
ypos=floor(2000+Dist*ymag); %calculate y & z positions at x=1000
zpos=floor(2000+Dist*zmag);
Imx(ypos,zpos)=Imx(ypos,zpos)+1; %record y & z positions into matrix for analysis
end
if ymag>0.5 %%Repeat above process for y & z planes
Dist=1000/ymag;
xpos=floor(2000+Dist*xmag);
zpos=floor(2000+Dist*zmag);
Imy(xpos,zpos)=Imy(xpos,zpos)+1;
end
if zmag>0.5
Dist=1000/zmag;
xpos=floor(2000+Dist*xmag);
ypos=floor(2000+Dist*ymag);
Imz(xpos,ypos)=Imz(xpos,ypos)+1;
end
end
end

I am using this as part of a ray tracing program and need to model a uniform point source. My aim is to model a uniform distribution on points on the surface of a sphere and then convert these positions (being a unit distance from the centre) into Cartesian vectors for the ray tracer.

I had looked at the methods suggested on the mathworld page, though none have yielded a sufficiently uniform distribution at my limits (order of 10^7-10^8 rays)

Thanks for your help

 

[mfb]

You get too many points close to the poles in that way.

For a uniform distribution of phi, the theta-density should be proportional to sin(phi).

You could do this:

for phi=0:pi/1000:pi
  for theta=-pi:1/(2000*sin(phi)):pi
    %do stuff

This is not perfectly uniform close to theta=+- pi, but the difference should be small. I think you get a better approximation if you start at -pi+1/(4000*sin(phi)), half the point-spacing away from the coordinate limit. You could even randomize this.

Those parameters should give about 1 million points, it is easy to change it.

 

[RMSimons]

Hi All,

thanks for all the help, I managed to get it working in the end using the method from mfb.

Can finally get on with some work now!

Rich

 

[mmpmpmpmp]

// Bauer R. Distribution of Points on a Sphere with Application to Star Catalogs, Journal of Guidance, Control, and Dynamics (2000)
for (lI = 0; lI < lN; lI++)
{
dH = 1 - (2 * lI + 1) / double(lN);
dAzimuthalAngle[lI] = acos(dH);
dPolarAngle[lI] = sqrt(lN * M_PI) * dAzimuthalAngle[lI];
}