Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Uniform grid of points on a sphere

  1. Nov 5, 2012 #1
    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.
     
  2. jcsd
  3. Nov 5, 2012 #2
    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.
     
  4. Nov 5, 2012 #3

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  5. Nov 6, 2012 #4
    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.
     
  6. Nov 6, 2012 #5
    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.
     
  7. Nov 7, 2012 #6
    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.
     
  8. Nov 7, 2012 #7
    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 :smile:
     
  9. Mar 4, 2013 #8
    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

     
  10. Mar 4, 2013 #9
    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.
     
  11. Mar 5, 2013 #10
    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
     

    Attached Files:

  12. Mar 5, 2013 #11

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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:
    Code (Text):
    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.
     
  13. Mar 15, 2013 #12
    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
     
  14. May 23, 2016 #13
    // 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];
    }
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted