Répartir uniformément n points sur une sphère

Question

J'ai besoin d'un algorithme qui peut me donner des positions autour d'une sphère pour N points (moins de 20, probablement) qui les répartit vaguement. Il n'y a pas besoin de "perfection", mais j'ai juste besoin que aucun d'entre eux ne soit regroupé.

• Cette question a fourni un bon code, mais je n'ai pas trouvé un moyen de le rendre uniforme, car cela semblait être à 100% aléatoire.
• Cet article de blog recommandait deux façons permettant de saisir le nombre de points sur la sphère, mais l'algorithme de Saff et Kuijlaars est exactement en pseudo-code que je pourrais transcrire, et l'exemple de code que j'ai trouvé contenait "node[k]", ce que je n'ai pas vu expliqué et a ruiné cette possibilité. Le deuxième exemple de blog était la Spirale de la Section Dorée, qui m'a donné des résultats étranges et regroupés, sans moyen clair de définir un rayon constant.
• Cet algorithme de cette question semble pouvoir fonctionner, mais je ne peux pas assembler ce qui se trouve sur cette page en pseudo-code ou quoi que ce soit d'autre.

Quelques autres fils de discussion auxquels j'ai participé ont parlé de distribution uniforme aléatoire, ce qui ajoute un niveau de complexité qui ne me préoccupe pas. Je m'excuse que ce soit une question si stupide, mais je voulais montrer que j'avais vraiment cherché intensément et n'avais toujours pas trouvé.

Donc, ce que je cherche, c'est un simple pseudo-code pour distribuer de manière uniforme N points autour d'une sphère unité, renvoyant soit des coordonnées sphériques soit cartésiennes. Encore mieux s'il peut distribuer uniformément avec un peu de randomisation (pensez aux planètes autour d'une étoile, assez espacées, mais avec de la marge de manœuvre).

Answer 1

L'algorithme de la sphère Fibonacci est excellent pour cela. Il est rapide et donne des résultats qui, en un coup d'œil, tromperont facilement l'œil humain. Vous pouvez voir un exemple réalisé avec processing qui montrera le résultat au fil du temps au fur et à mesure que des points sont ajoutés. Voici un autre excellent exemple interactif réalisé par @gman. Et voici une implémentation simple en python.

import math

def fibonacci_sphere(samples=1000):

    points = []
    phi = math.pi * (math.sqrt(5.) - 1.)  # golden angle en radians

    for i in range(samples):
        y = 1 - (i / float(samples - 1)) * 2  # y va de 1 à -1
        radius = math.sqrt(1 - y * y)  # rayon à y

        theta = phi * i  # incrément d'angle d'or

        x = math.cos(theta) * radius
        z = math.sin(theta) * radius

        points.append((x, y, z))

    return points

1000 échantillons vous donnent ceci :

Answer 2

Ceci est connu comme l'emballage de points sur une sphère, et il n'existe pas de solution générale et parfaite (connue). Cependant, il existe de nombreuses solutions imparfaites. Les trois plus populaires semblent être:

1. Créer une simulation. Traitez chaque point comme un électron contraint à une sphère, puis lancez une simulation pour un certain nombre d'étapes. La répulsion des électrons tendra naturellement le système vers un état plus stable, où les points sont à peu près aussi éloignés les uns des autres que possible.
2. Rejet de l'hypercube. Cette méthode au nom fantaisiste est en réalité très simple : vous choisissez uniformément des points (beaucoup plus que n d'entre eux) à l'intérieur du cube entourant la sphère, puis rejetez les points à l'extérieur de la sphère. Traitez les points restants comme des vecteurs et normalisez-les. Ce sont vos "échantillons" - choisissez n d'entre eux en utilisant une méthode quelconque (au hasard, cupide, etc.).
3. Approximations en spirale. Vous tracez une spirale autour d'une sphère et distribuez uniformément les points autour de la spirale. En raison des mathématiques impliquées, ces méthodes sont plus complexes à comprendre que la simulation, mais beaucoup plus rapides (et probablement nécessitant moins de code). La plus populaire semble être celle de Saff, et al.

Beaucoup plus d'informations sur ce problème peuvent être trouvées ici

Answer 3

Dans ce code d'exemple, node[k] est simplement le noeud k. Vous générez un tableau de N points et node[k] est le k-ième (de 0 à N-1). Si c'est tout ce qui vous déroute, vous devriez pouvoir l'utiliser maintenant.

(en d'autres termes, k est un tableau de taille N qui est défini avant le début du fragment de code, et qui contient une liste de points).

Alternativement, en s'appuyant sur l'autre réponse ici (et en utilisant Python) :

> cat ll.py
from math import asin
nx = 4; ny = 5
for x in range(nx):
    lon = 360 * ((x+0.5) / nx)
    for y in range(ny):                                                         
        midpt = (y+0.5) / ny                                                    
        lat = 180 * asin(2*((y+0.5)/ny-0.5))                                    
        print lon,lat                                                           
> python2.7 ll.py                                                      
45.0 -166.91313924                                                              
45.0 -74.0730322921                                                             
45.0 0.0                                                                        
45.0 74.0730322921                                                              
45.0 166.91313924                                                               
135.0 -166.91313924                                                             
135.0 -74.0730322921                                                            
135.0 0.0                                                                       
135.0 74.0730322921                                                             
135.0 166.91313924                                                              
225.0 -166.91313924                                                             
225.0 -74.0730322921                                                            
225.0 0.0                                                                       
225.0 74.0730322921                                                             
225.0 166.91313924
315.0 -166.91313924
315.0 -74.0730322921
315.0 0.0
315.0 74.0730322921
315.0 166.91313924

Si vous tracez cela, vous verrez que l'espacement vertical est plus important près des pôles, de sorte que chaque point est situé dans à peu près la même surface d'espace (près des pôles, il y a moins d'espace "horizontalement", donc cela donne plus "verticalement").

Ce n'est pas la même chose que tous les points ayant à peu près la même distance avec leurs voisins (ce dont je pense que vos liens parlent), mais cela peut être suffisant pour ce que vous voulez et améliore simplement la création d'une grille lat/lon uniforme.

Answer 4

Essayer :

function sphere ( N:float,k:int):Vector3 {
    var inc =  Mathf.PI  * (3 - Mathf.Sqrt(5));
    var off = 2 / N;
    var y = k * off - 1 + (off / 2);
    var r = Mathf.Sqrt(1 - y*y);
    var phi = k * inc;
    return Vector3((Mathf.Cos(phi)*r), y, Mathf.Sin(phi)*r); 
};

La fonction ci-dessus devrait fonctionner en boucle avec un total de N boucles et une itération actuelle k.

Elle est basée sur un motif de graines de tournesol, sauf que les graines de tournesol sont courbées autour d'un demi-dôme, puis encore en une sphère.

Voici une image, sauf que j'ai placé la caméra à mi-chemin à l'intérieur de la sphère.

Answer 5

Prenez les deux plus grands facteurs de votre N, si N==20 alors les deux plus grands facteurs sont {5,4}, ou, plus généralement {a,b}. Calculer

dlat  = 180/(a+1)
dlong = 360/(b+1})

Placez votre premier point à {90-dlat/2,(dlong/2)-180}, votre deuxième à {90-dlat/2,(3*dlong/2)-180}, votre 3ème à {90-dlat/2,(5*dlong/2)-180}, jusqu'à ce que vous ayez fait le tour du monde une fois, à ce moment-là vous devriez être à environ {75,150} quand vous allez ensuite à {90-3*dlat/2,(dlong/2)-180}.

Évidemment, je travaille en degrés sur la surface de la terre sphérique, avec les conventions habituelles pour traduire +/- en N/S ou E/O. Et évidemment, cela vous donne une distribution complètement non aléatoire, mais elle est uniforme et les points ne sont pas regroupés.

Pour ajouter un certain degré de hasard, vous pourriez générer 2 valeurs distribuées normalement (avec une moyenne de 0 et un écart type de {dlat/3, dlong/3} selon le cas) et les ajouter à vos points distribués uniformément.