Evenly distributed points on sphere

From CGAFaq
Jump to: navigation, search

Evenly distributed is not well defined. In the strictest sense, only the five Platonic solids (and the infinite family of degenerate arrangements with all nodes equally spaced on a great circle) can qualify: each node has the same number of neighbors, at the same distance, equally spaced around itself.

More broadly, the goal is to avoid placing the nodes more densely in one region than in another. This can be put formally in a number of ways, the most common of which are packing (maximizing the smallest distance between nodes), covering (minimizing the greatest distance of any point from the nearest node), and electrostatic repulsion (treating the nodes as charged particles).

Each of these versions of the problem leads into moderately complex mathematics; none has a known general solution. This topic happens to be a FAQ on sci.math as well as on comp.graphics.algorithms; a much more extensive and rigorous discussion written by Dave Rusin can be found at

http://www.math.niu.edu/~rusin/known-math/95/sphere.faq

Contents

Electrostatic repulsion

Of the big three, the easiest to implement is the last, also called the electron problem or the Thomson problem. Starting from an arbitrary distribution, we can use either numerical minimization algorithms or point repulsion, in which all the nodes are considered to repel each other according to a 1/r² force law and dynamics are simulated. The algorithm is run until some convergence criterion is satisfied, and the resulting distribution is our approximation.

Geodesic subdivision

Another approach, which does not require seeking convergence, is repeated subdivision of triangles; the geodesic dome is a familiar example. Beginning with an octahedron (for simplicity) or an icosahedron (for greater evenness) inscribed in a unit sphere, find the midpoint of each edge and normalize its coordinates, "pushing" it out to make a new vertex lying on the unit sphere; this breaks each original triangle into four new smaller triangles. Repeat the process until the desired number of vertices is reached. Caution: because of the projection, edges near the middle of an original triangle will be longer than those near an original vertex, by a factor of up to √(15-6√5) ≈ 1.26 for the icosahedron and √3 ≈ 1.73 for the octahedron.

Adrian Rossiter's Python programs include a very versatile geodesic generator.

Spirals

If you do not need as much symmetry as the above approaches give, a very quick method is to divide the sphere along lines of "latitude" into parallel bands of equal area and place a node at some "longitude" in the middle of each band.

The method of Saff and Kuijlaars arranges the nodes along a spiral in such a way that the distance between nodes along the spiral is approximately equal to the distance between coils of the spiral: 

s  := 3.6/sqrt(N)
dz := 2.0/N
long := 0
z    := 1 - dz/2
for k := 0 .. N-1
    r    := sqrt(1-z*z)
    node[k] := (cos(long)*r, sin(long)*r, z)
    z    := z - dz
    long := long + s/r

A related method chooses successive longitudes according to the "most irrational number" \frac{1}{\tau}=\frac{sqrt{5}-1}{2} (known as the golden section) so that no two nodes in nearby bands come too near each other in longitude. This method obtains a slightly better packing than the above, and is slightly quicker, with one less division in the loop: 

dlong := pi*(3-sqrt(5))  /* ~2.39996323 */
dz    := 2.0/N
long := 0
z    := 1 - dz/2
for k := 0 .. N-1
    r    := sqrt(1-z*z)
    node[k] := (cos(long)*r, sin(long)*r, z)
    z    := z - dz
    long := long + dlong

External links

Code available at http://maven.smith.edu/~orourke/code.html

Overviews

Applications

Algorithmic approximations

Exact optimization

Overviews

Packing

The packing problem, also called the Tammes Problem or Fejes Tóth Problem, is to maximize the minimum distance between nodes. If the set of distances is considered as a set of coordinates in a space of high dimension, the packing problem is to maximize the −∞-norm.

Electrostatic repulsion

Solving the Thomson problem, or finding the Fekete points, is minimizing the sum of distances raised to the power −1.

Covering

Minimize the greatest Voronoi radius.

Equal area

Maximize volume of convex hull

Other criteria

  • Jentje Goslinga: maximize sum of distances (exponent +1)
  • Hardin & Sloane: t-designs
  • Hugo Pfoertner: illumination by light sources at infinity
  • Marek Teichmann seeks to maximize the sphere inscribed in the convex hull of the nodes, specifying that it be concentric with the original sphere; that makes the problem equivalent to covering. But is the condition redundant? Is the maximum inscribed sphere ever not concentric?
Retrieved from "http://www.cgafaq.info/wiki/Evenly_distributed_points_on_sphere"
Personal tools