CODEWITHSUNDEEP
mathgraphics3dtrigonometryvector-graphics
Dane Iracleous
Dane Iracleous

Reputation: 1759

How to plot N points on the surface of a D-dimensional sphere roughly equidistant apart?

Let's say I have a D-dimensional sphere with center, [C1, C2, C3, C4, ... CD], and a radius R. Now I want to plot N number of points evenly distributed (equidistant apart from each other) on the surface of the sphere. It doesn't matter where those points are exactly, just that they are ROUGHLY equidistant from each other. I want a function that returns an array of these points, P.

function plotter(D, C[1...D], R, N)
{
   //code to generate the equidistant points on the sphere

   return P[1...N][1...D];
}

3-dimensional sphere with many points

3-dimensional sphere with a few points

Upvotes: 14

Views: 5513

Answers (3)

Arvind
Arvind

Reputation: 151

I don't know if this has been mentioned here yet; but you could, as others have suggested draw points from the uniform distribution on the sphere. After which, flow each point according to columb energy; using a gradient descent method. This particular problem has received a lot of attention. Check out the following paper and this website

Upvotes: 1

nbonneel
nbonneel

Reputation: 3326

Several options :

  • Randomly throw points on the sphere and use a Lloyd relaxation to make them uniformly spread : you iteratively compute their Voronoi diagram and move them toward the center of their Voronoi cell (instead of working on the sphere, you may want to use an euclidean voronoi diagram restricted to the sphere : CGAL can fo that for instance, or refer to my article).

  • If a rough approximation is fine (ie., if a uniformly random distribution is good enough), you can use the formula explained on Wiki : N-Sphere . If not, you can still use this random sampling as the initialization of the method above

  • For a still random but better notion of equidistant samples, you can generate a Poisson-disk distribution. Fast code in high dimension is available at Robert Bridson's homepage . You may need to adapt it for a spherical domain though.

Upvotes: 7

Michael Anderson
Michael Anderson

Reputation: 73490

The only way I can think of that should produce good results is.

  1. Generate N points on the sphere surface. The usual way to do this for high dimensions is to generate the points acording to an D-dimensional normal distribution and normalise back to the sphere. These will not be equally spaced - so we need step two
  2. Next make each point repel other points using some repulsions function and use a small time-step, you adjust the direction of movement to be tangential to the D-Sphere. Move the point and then repoject back to the sphere. Keep doing this until you consider the points even enough.

Upvotes: 0

Related Questions