Evenly distributed points on sphere
From CGAFaq
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. 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
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, the length of the edges will vary 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)
long := 0
dz := 2.0/N
z := 1 - dz/2
for k := 0 .. N-1
r := sqrt(1-z*z)
pt[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" (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:
dlong := pi*(3-sqrt(5))
long := 0
dz := 2.0/N
z := 1 - dz/2
for k := 0 .. N-1
r := sqrt(1-z*z)
pt[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
See also the links collected by Anton Sherwood.
