Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Dispersing n points uniformly on a sphere

I am trying to disperse n points on a sphere such that each point has the "same" area "around" it. Basically, I'm trying to integrate a function over a sphere by evaluating at n points and assuming that each area element is the same (and equal to 4pi r^2/n).

My question is very related to this one, but I can't seem to agree that the code presented in the "accepted" answer works as desired (see attached photo, generated by choosing R = 1000, nx = ny = 40). Clearly, my points are much more concentrated at the poles and very un-concentrated along the equator.

Any suggestions?

EDIT: For reference, I did find some software that generates a mesh such that each point has equal "area" around it (scroll down to see uniform area distribution on a sphere), but rather than implement their code I went with a less-time consuming approach: I simply iterated over the azimuthal and polar angles ([0,2pi] and [0,pi]) and computed the ''infinitesimal'' area of each patch (da = r^2 sin theta dtheta dphi). This is basically all I need for integration over the sphere, I was just hoping that uniform-area distribution wouldn't be so hard to implement.

like image 207
alexvas Avatar asked Feb 11 '13 03:02

alexvas


People also ask

How many points is a sphere?

A sphere is uniquely determined by four points that are not coplanar. More generally, a sphere is uniquely determined by four conditions such as passing through a point, being tangent to a plane, etc.

What is the maximum number of points in space that can be equidistant from each other?

geometry - Maximum number of mutually equidistant points in an n-dimensional Euclidean space is (n+1).


3 Answers

Background information:

There are 4 pi steradians in a sphere, that's the total 'degrees' in a sphere, but I use the term only in the relative sense because steradians are very different from regular radians in a circle, for one, they are 3 dimensional and therefore are solid. Just consider them as ice cream shaped angles in a sphere. enter image description here

http://en.wikipedia.org/wiki/Steradian provides a great example of them.

They have a direct relationship to the radius, like radians in a circle. 1 steradian = 1 unit of radius squared.

So, first find out how many items need to be plotted on the sphere. Let that number be n. sr = steradians (unit of measure) = r^2 (radius squared)

4 pi / n sr = x

x is how many steradians are allocated to each point.

let's say for 4 points.

4 pi / 4 sr = x

pi sr = x So each point will get an allocated space of pi sr.

Now consider this... since you are plotting points, we will consider that each point will be placed in the middle of the allocated space... that is to say, in the middle of the conal shaped area which is what sr is. Now you need to consider something for a moment, is it possible to fill an area completely with circles? Seriously, think about this... it's not is it? Solid circles will always leave room in between in certain spots. Think about a soccer ball for a moment. It is constructed from shapes that can come together to provide even distribution. The point of this thought is to get you to realize that all dots cannot be exactly a certain distance apart--like how a circle has a radius. Yet, the center of the soccer ball squares comes very close and is uniform.

What I would do if I were you, would be to try and write an algorithm to identify the most efficient 'shape' to put each of these 'chunks' of allocated spherical space in... like the soccer ball. Otherwise, I think this might be the best answer you're going to get... 4 pi / n sr = x... , there's no way for each point to be plotted so it exactly the same distance from each other, (except in certain configurations, i.e. it would be possible with special number of points), there may an algorithm out there to find all the special cases.

I am editing this answer to elaborate on the special cases, a little extra information would be good here I think. The special cases for the points to be equidistance apart are that they may form the vertices of platonic solids. There are only 5 basic platonic solid shapes, all others are made by these.

Read this page for more information and proof of this https://www.uwgb.edu/dutchs/symmetry/platonic.htm

Now I can't take credit, I did some quick research and found a similar post https://math.stackexchange.com/questions/279544/return-an-array-of-evenly-distributed-points-on-a-sphere-give-radius-and-origin

Using Euler's polyhedron formula http://plus.maths.org/content/eulers-polyhedron-formula

and the fact that only three basic shapes exist on polyhedrons, 'triangles, squares, and hexagons' you can create an algorithm to round the number of points you want to plot, to the nearest polyhedron shape and plot each one evenly.

enter image description here

Oh, and take a look at this great article, it explains steradians and 3-dimensional 'degrees' much better than I. http://mathforum.org/library/drmath/view/55358.html

like image 52
Klik Avatar answered Oct 01 '22 12:10

Klik


Here's an example algorithm I just whipped up in python:

from numpy import random, cos, sin, sqrt, pi
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt

def rand_sphere(n):
  """n points distributed evenly on the surface of a unit sphere""" 
  z = 2 * random.rand(n) - 1   # uniform in -1, 1
  t = 2 * pi * random.rand(n)   # uniform in 0, 2*pi
  x = sqrt(1 - z**2) * cos(t)
  y = sqrt(1 - z**2) * sin(t)
  return x, y, z

x, y, z = rand_sphere(200)
fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
ax.scatter(x, y, z)
plt.show()

enter image description here

Again with 10000 points:

enter image description here

like image 29
wim Avatar answered Oct 01 '22 12:10

wim


Could be wrong, but if

  1. setup interactions between two points as I(a,b) = (a-b) / (|a-b|)^3, a,b are threatened as vectors in 3D space
  2. for the first iterations place points as usual (at equal angle distances, how it has been mentioned in the wim post)
  3. at each step of algorithm you will move each point against gradient of summ of I (from 1.) where I is calculated only on direct neighbours
  4. repeat 3 until gradient at each point will become 0.

the algorithm will converge to the configuration what you need. It is time consumpting, but you could cache results for various number of points.

like image 45
distantTransformer Avatar answered Oct 01 '22 13:10

distantTransformer