4

In a nutshell:

I need an algorithm that can generate points on the surface of a sphere, and the euclidean distance between each point and its neighbors must be the same.

Here is a quick explanation about what I mean about that:

If the sphere was represented as a "geodesic polyhedron" ("geodesic sphere"), each side of all the triangles would have the same length. Note that it doesn't have to be a Geodesic grid or a geodesic polyhedron, it could be something else. I'm open to all suggestions.

The difficulty is that we must be able to specify the distance between the neighbouring points.

If it was a graph I would say that the edges should be the same length, and that the distance between the adjacent nodes / vertices should the same.

What I'm looking for:

  • an existing libray / function or algorithm that already solves this problem (but I doubt that it would be the case because I did a lot of research)
  • an implementation

Constraints of the algorithm:

Output:

  • an array of 3D (x,y,z) coordinates.

Input parameters:

  • 3D (x,y,z) coordinates of the sphere center
  • radius of the sphere
  • distance between neighbouring points (adjacent nodes)

What I've done:

  • I did a lot of research about the subject
  • I've read a lot of papers an articles
  • I implemented some algorithms I found

I found a lot of good papers and resources about related problems, but nothing for this specific case. So after days of research, I ask people that have specialised knowledge of this area some help.

The closest solution I've found is the Deserno algorithm (see link below), but the problem is that its input parameters are the radius and a number of points to generate (we can't sepcify the coordinates of the sphere center an the distance between neighbouring points).

If it helps, here are some related questions and useful resources:

Evenly distributing n points on a sphere

Plotting points on the surface of a sphere in Python's matplotlib

https://en.wikipedia.org/wiki/Geodesic_grid

https://en.wikipedia.org/wiki/Geodesic_polyhedron

https://en.wikipedia.org/wiki/Spherical_polyhedron

Deserno algorithm: https://www.cmu.edu/biolphys/deserno/pdf/sphere_equi.pdf

Some representations to give an idea:

Evenly distributed points: enter image description here

Geodesic grid / geodesic polyhedron: enter image description here

Geodesic polyhedron zoom: Here, each point is at 10 centimeters of distance from its neighbors. enter image description here

Rivers
  • 1,783
  • 1
  • 8
  • 27
  • "The closest solution I've found is the Deserno algorithm (see link below), but the problem is that its input parameters are the radius and a number of points to generate (we can't sepcify the coordinates of the sphere center an the distance between neighbouring points)." Can you try to find a relationship between the number of points, the radius of the sphere, and the distance between neighbouring points? – Stef Mar 09 '21 at 16:37
  • @Stef "see link below"? – Severin Pappadeux Mar 09 '21 at 17:08
  • What I could think about are Poisson disks or similar algorithms. It is used to cover plane with random points at minimum distance, but people extended it to arbitrary surfaces, e.g. see http://archive.ymsc.tsinghua.edu.cn/pacm_download/38/288-2012_SIGABrief_AMPS.pdf – Severin Pappadeux Mar 09 '21 at 17:10
  • 1
    All of the distances *exactly the same*? That is in general impossible. There are provably only a finite number of solutions for which that is true. The Platonic Solids form the basis of those solutions. All of the distance within some tolerance of each other is going to be what is required. – btilly Mar 09 '21 at 18:50
  • @stef: yes I had this idea too but was unable to find this relationship and don't even know if possible from this algorithm. – Rivers Mar 09 '21 at 19:25
  • @Severin Pappadeux: Thanks I'll check that. I've already implemented algorithms that put points randomly and they in general use Poisson statistics (as in the random example in the Deserno article I mentioned too). Do you think that this "minimum distance" could be the "equal distance" I'm looking for? – Rivers Mar 09 '21 at 19:30
  • @btilly: very interesting remark too, thank you! That in fact was a question I was asking to myself. Not sure indeed if it would be possible with any arbitrary value. If not mathematically/geometrically possible, yes some tolerance (in an acceeptable range) could be acceptable for our use case. Do you know how we could find these "finite number of solutions" ? – Rivers Mar 09 '21 at 19:41
  • @Rivers I think with minimum distance being all equal might work out but efficiency would drop. I only used Poisson disks in 2D/3D, never on the surface – Severin Pappadeux Mar 09 '21 at 19:52
  • 2
    see [How to distribute points evenly on the surface of hyperspheres in higher dimensions?](https://stackoverflow.com/a/57240140/2521214) my hyper-spiral approach there is taking distance between screws (which is similar to your avg distance between points) however it is approximation so do not expect it is 100% accurate. As accurate solution is posible only for certain radius and distance configurations leading to number of points that can be placed uniformly. My other answer might be tweaked for your task too as arc step is directly a function of the desired distance between points. – Spektre Mar 10 '21 at 08:14

0 Answers0