Répartir uniformément n points sur une sphère
J'ai besoin d'un algorithme qui peut me donner les positions autour d'une sphère de N points (moins de 20, sans doute) que vaguement se répand au dehors. Il n'y a pas besoin de "perfection", mais j'ai juste besoin de sorte qu'aucun d'entre eux sont regroupés ensemble.
- Cette question fourni du bon code, mais je ne pouvais pas trouver un moyen de faire de cet uniforme, comme cela semblait 100% aléatoire.
- Ce blog recommandé deux façons, permettant de saisir le nombre de points sur la sphère, mais la Saff et Kuijlaars algorithme est exactement dans psuedocode j'ai pu transcrire, et la exemple de code j'ai trouvé les "nœud[k]", que je ne pouvais pas voir expliqué et ruiné cette possibilité. Le deuxième blog de citer l'exemple de la Section d'Or en Spirale, ce qui m'a donné étrange, enchevêtre les résultats, avec aucun moyen de définir un rayon constant.
- Cet algorithme de cette question semble comme il pourrait éventuellement fonctionner, mais je ne peux pas rassembler ce qui est sur que page en psuedocode ou quoi que ce soit.
Quelques autres question threads, je suis tombé sur parlé de randomisée distribution uniforme, ce qui ajoute un niveau de complexité que je ne suis pas inquiète. Je m'excuse que c'est une question idiote, mais je voulais montrer que j'ai vraiment bien cherché et encore trouver à court.
Donc, ce que je cherche est simple pseudocode pour distribuer uniformément la N de points autour d'une sphère unité, qui renvoie soit sphériques ou des coordonnées Cartésiennes. Encore mieux si il peut même distribuer avec un peu de randomisation (pensez planètes autour d'une étoile, décemment dispersés, mais avec de la place pour une marge de manœuvre).
- Qu'entendez-vous "avec un peu de randomisation"? Voulez-vous dire des perturbations dans un certain sens?
- L'OP est confus. Ce qu'il cherche est de mettre n points sur une sphère, de sorte que la distance minimale entre deux points est la plus grande possible. donner les points de l'apparence de l'être "uniformément répartie sur l'ensemble de la sphère. C'est complètement étranger à la création d'une distribution aléatoire uniforme sur une sphère, qui est ce que beaucoup de ces liens sont au sujet, et ce que beaucoup de réponses ci-dessous sont en train de parler.
- 20 n'est pas beaucoup de points à placer sur une sphère si vous ne voulez pas à regarder tout simplement au hasard.
- Voici un moyen de le faire (on a des exemples de code): pdfs.semanticscholar.org/97a6/... (dirait qu'il utilise la force de répulsion des calculs)
- Bien sûr, pour des valeurs de N dans {4, 6, 8, 12, 20} il existe des solutions exactes de la distance de chaque point de (chaque), il est plus proche des voisins est une constante pour tous les points et tous les voisins les plus proches.
Vous devez vous connecter pour publier un commentaire.
Dans cet exemple de code
node[k]
est juste la kième nœud. Vous êtes de la génération d'une matrice de N points etnode[k]
est le kth (de 0 à N-1). Si c'est tout ce qui est déroutant vous, j'espère que vous pouvez l'utiliser maintenant.(en d'autres termes,
k
est un tableau de taille N qui est défini avant le fragment de code commence, et qui contient une liste des points).Sinon, en s'appuyant sur la réponse à faire ici (et à l'aide de Python):
Si vous intrigue, vous verrez que l'espacement vertical est plus près des pôles, de sorte que chaque point est situé à environ le même nombre de zone de l'espace (près des pôles, il y a moins d'espace "à l'horizontale", de sorte qu'il donne plus de "verticale").
Ce n'est pas le même que tous les points ayant la même distance à leurs voisins (qui est ce que je pense de vos liens parle), mais il peut être suffisant pour ce que vous voulez et améliore simplement faire un uniforme grille de latitude/longitude.
Fibonacci de la sphère de l'algorithme est excellent pour cela. C'est rapide et donne des résultats en un coup d'oeil facilement tromper l'œil humain. Vous pouvez voir un exemple fait avec le traitement qui affichera le résultat de plus de temps que les points sont ajoutés. Voici un autre excellent exemple interactive faite par @gman. Et voici une version de python avec une simple option de randomisation:
1000 échantillons vous donne ceci:
y
totalement aléatoire? Actuellementy
est indifférent à la graine aléatoireCeci est connu comme emballage des points sur une sphère, et il n'est pas (connu), général, de solution parfaite. Cependant, il ya beaucoup de solutions imparfaites. Les trois les plus populaires semblent être:
n
d'entre eux) à l'intérieur du cube entourant la sphère, puis rejeter les points situés à l'extérieur de la sphère. Traiter les points restants en tant que vecteurs, et de les normaliser. Ce sont des "échantillons" - choisirn
à l'aide d'une méthode (au hasard, gourmand, etc).Un beaucoup plus d'informations à propos de ce problème peut être trouvée ici
L'or spirale méthode
Vous avez dit que vous ne pouvait pas obtenir l'or de la spirale de la méthode à travailler, et c'est une honte parce que c'est vraiment, vraiment bon. Je tiens à vous donner une compréhension complète de sorte que vous pouvez peut-être comprendre comment garder cette loin d'être "retroussé."
Voici donc un rapide, non-façon aléatoire pour créer un treillis qui est d'environ correcte, comme indiqué ci-dessus, pas de treillis sera parfait, mais cela peut être "assez bon". Il est comparé à d'autres méthodes, par exemple, à BendWavy.org mais il a juste un gentil et joli look ainsi que d'une garantie sur le même espacement dans la limite.
Primer: tournesol spirales sur le disque unité
Pour comprendre cet algorithme, j'ai d'abord vous invitons à regarder la 2D de tournesol spirale de l'algorithme. Ceci est basé sur le fait que la plupart des nombre irrationnel est le nombre d'or
(1 + sqrt(5))/2
et si on émet des points par l'approche "debout au centre, tourner un golden ratio de l'ensemble des tours, puis émettre un autre point dans la direction de," un naturellement construit une spirale qui, comme vous obtenez plus élevé et un plus grand nombre de points, néanmoins refuse d'avoir bien défini "les barres" que les points de la ligne sur.(Remarque 1.)L'algorithme pour le même espacement sur un disque,
et elle produit des résultats qui ressemblent (n=100 et n=1000):
L'espacement des points radialement
La clé est étrange, c'est la formule
r = sqrt(indices /num_pts)
; comment ai-je venir à celui-ci? (Note 2.)Bien, je suis en utilisant la racine carrée ici parce que je veux ces ont même pas de la zone espacement autour de la sphère. C'est la même chose que de dire que dans la limite des grandes N je veux un peu d'région R ∈ (r, r + dr), Θ ∈ (θ, θ + dθ) pour contenir un nombre de points proportionnel à sa surface, qui est r dr dθ. Maintenant, si nous prétendons que nous parlons d'une variable aléatoire ici, c'est une simple interprétation que de dire que la densité de probabilité d' (R, Θ) est juste c r pour certains constante c. La normalisation sur l'unité de disque puis forces c = 1/π.
Maintenant laissez-moi vous présenter une astuce. Il s'agit de la théorie des probabilités, où il est connu comme l'échantillonnage de l'inverse de la CDF: supposons que vous vouliez générer une variable aléatoire avec une densité de probabilité f(z) et vous avez une variable aléatoire U ~ Uniforme(0, 1), comme vient de
random()
dans la plupart des langages de programmation. Comment faites-vous cela?Maintenant le golden ratio spirale truc espaces, les points de dans une bien même modèle pour θ donc, nous allons l'intégrer; pour le cercle unité, nous sommes à gauche avec F(r) = r2. De sorte que la fonction inverse est F-1(u) = u1/2, et par conséquent, nous générons des points sur la sphère en coordonnées polaires avec
r = sqrt(random()); theta = 2 * pi * random()
.Maintenant, au lieu de au hasard d'échantillonnage de cette fonction inverse nous sommes uniformément d'échantillonnage, et la bonne chose à propos de l'uniforme de l'échantillonnage, c'est que nos résultats sur la façon dont les points sont répartis dans la limite de grande N va se comporter comme si nous avions un échantillon aléatoire il. Cette combinaison est le truc. Au lieu de
random()
nous utilisons(arange(0, num_pts, dtype=float) + 0.5)/num_pts
, de sorte que, par exemple, si nous voulons un échantillon de 10 points, ils sontr = 0.05, 0.15, 0.25, ... 0.95
. Nous uniformément échantillon r pour obtenir l'égalité de la zone espacement, et nous utilisons le tournesol incrément pour éviter les affreux "barres" de points dans la sortie.Maintenant le tournesol sur une sphère
Les changements que nous devons apporter à la dot de la sphère des points simplement impliquer commutation de l'coordonnées polaires pour les coordonnées sphériques. La coordonnée radiale bien sûr, ne veut pas entrer dans ce parce que nous sommes sur une sphère unité. Pour garder les choses un peu plus consistant ici, même si j'ai été formé en tant que physicien, je vais utiliser mathématiciens coordonnées de l'endroit où 0 ≤ φ ≤ π est la latitude à venir vers le bas de la perche et 0 ≤ θ ≤ 2π est de la longitude. Donc, la différence est que nous sommes tout simplement en remplaçant la variable r avec φ.
Notre région élément, qui a été r dr dθ, devient maintenant pas beaucoup plus compliqué sin(φ) dφ dθ. Donc, notre commune densité pour un espacement uniforme est un péché(φ)/4π. L'intégration hors θ, nous trouvons f(φ) = sin(φ)/2, donc F(φ) = (1 − cos(φ))/2. L'inversion de cela, nous pouvons voir qu'une variable aléatoire uniforme ressemblerait acos(1 - 2 u), mais nous l'échantillon uniformément plutôt que de façon aléatoire, de sorte que nous au lieu d'utiliser φk = acos(1 − 2 (k + 0.5)/N). Et le reste de l'algorithme est simplement la projection de ce sur x, y et z les coordonnées:
De nouveau pour n=100 et n=1000 les résultats ressemblent à:
Notes
Ces "barres" sont formées par des approximations rationnelles pour un certain nombre, et les meilleures approximations rationnelles à un certain nombre de ses fraction continue d'expression,
z + 1/(n_1 + 1/(n_2 + 1/(n_3 + ...)))
oùz
est un entier etn_1, n_2, n_3, ...
est soit fini ou infini de la séquence de nombres entiers positifs:Puisque la fraction de la partie
1/(...)
est toujours entre zéro et un, un grand nombre entier en fraction continue permet notamment une bonne approximation rationnelle: "l'un divisé par quelque chose entre 100 et 101" est mieux que "l'un divisé par quelque chose entre 1 et 2." La plupart de nombre irrationnel est donc celui qui est1 + 1/(1 + 1/(1 + ...))
et n'a pas particulièrement bonnes approximations rationnelles; on peut résoudre φ = 1 + 1/φ en multipliant par φ pour avoir la formule pour le nombre d'or.Pour les gens qui ne sont pas familiers avec NumPy-toutes les fonctions sont "vectorisé", de sorte que
sqrt(array)
est la même chose que ce que d'autres langues pourrait écriremap(sqrt, array)
. C'est donc un composant par composantsqrt
application. La même chose vaut aussi pour la division par un scalaire ou plus avec des scalaires -- celles qui s'appliquent à tous les composants en parallèle.La preuve en est simple, une fois que vous savez que c'est le résultat. Si vous demandez quelle est la probabilité que z < Z < z + dz, c'est la même chose que de demander quelle est la probabilité que z < F-1(U) < z + dz, appliquer F à tous les trois expressions de noter que c'est une fonction monotone croissante, donc F(z) < U < F(z + dz), développez le côté droit de la trouver F(z) + f(z) dz, et depuis U est uniforme cette probabilité est juste f(z) dz comme promis.
Ce que vous cherchez est appelé un sphérique couvrant. L'sphérique couvrant problème est très dur et les solutions sont inconnus, sauf pour un petit nombre de points. Une chose qui est certain, c'est que étant donné n points sur une sphère, il existe toujours deux points de distance
d = (4-csc^2(\pi n/6(n-2)))^(1/2)
ou plus près.Si vous voulez une méthode probabiliste pour générer des points uniformément répartis sur une sphère, c'est simple: générer des points dans l'espace de manière uniforme par la distribution Gaussienne (il est intégré dans Java, pas dur à trouver le code pour les autres langues). Donc dans un espace à 3 dimensions, vous besoin de quelque chose comme
Ensuite le projet le point sur la sphère en normalisant sa distance par rapport à l'origine
La distribution Gaussienne à n dimensions est à symétrie sphérique de la projection sur la sphère est uniforme.
Bien sûr, il n'y a aucune garantie que la distance entre deux points dans une collection de manière uniforme généré points sera délimitée ci-dessous, de sorte que vous pouvez utiliser de rejet à l'application de ces conditions que vous pourriez avoir: sans doute il est préférable de générer l'ensemble de la collection et de rejeter l'ensemble de la collection, si nécessaire. (Ou utilisez le "rejet précoce" pour rejeter l'ensemble de la collection que vous avez généré à ce jour; il suffit de ne pas garder certains points et de les déposer à d'autres). Vous pouvez utiliser la formule pour
d
donné ci-dessus, diminué d'un peu de mou, pour déterminer le minimum de la distance entre les points ci-dessous qui vous permettra de rejeter un ensemble de points. Vous aurez à calculer n en choisir 2 distances, et la probabilité de rejet dépendra de la slack, c'est difficile de dire comment, exécuter une simulation pour obtenir une sensation pour les statistiques pertinentes.Cette réponse est fondée sur le même "théorie", qui est présentée par cette réponse
Je suis en ajoutant que cette réponse:
- Aucun des autres options d'ajustement de l'uniformité "besoin" spot-on " (ou pas d'évidence de façon claire). (Notons, pour obtenir de la planète comme la distribution à la recherche de comportement particurally voulu dans la demande initiale, vous venez de rejeter à partir de la liste restreinte de la k uniformément les points créés au hasard (random wrt l'index de comptage dans les k éléments de retour).)
--Le plus proche de l'autre impl forcé de vous décider, le " N " par "angulaire de l'axe', contre seulement 'une valeur de N' à travers les deux angulaire de l'axe des valeurs ( qui, à faibles valeurs de N est très difficile de savoir ce qui peut ou ne peut pas d'importance (par exemple, vous voulez '5' points, plaisir ) )
--De plus, il est très difficile à "analyser" comment différencier entre les autres options, sans images, voici ce que cette option ressemble (ci-dessous), et le prêt-à-l'application qui va avec.
avec N à 20:
et puis N à 80:
voici le ready-to-run python3 code, où l'émulation est de la même source: "http://web.archive.org/web/20120421191837/http://www.cgafaq.info/wiki/Evenly_distributed_points_on_sphere " trouvé par d'autres personnes. ( Le tracé que j'ai compris, que les incendies lors de l'exécuter en tant que "principal", est tiré de: http://www.scipy.org/Cookbook/Matplotlib/mplot3D )
testés au faible nombre N dans 2, 5, 7, 13, etc) et cela semble fonctionner "gentil"
Essayer:
La fonction ci-dessus devrait fonctionner en boucle avec la N de la boucle de total et k de la boucle d'itération en cours.
Il est basé sur un graines de tournesol motif, sauf les graines de tournesol sont courbé autour d'une demi-coupole, et encore dans une sphère.
Voici une image, sauf que je mets la caméra à moitié chemin à l'intérieur de la sphère, de sorte qu'il semble 2d au lieu de la 3d parce que la caméra est à la même distance de tous les points.
http://3.bp.blogspot.com/-9lbPHLccQHA/USXf88_bvVI/AAAAAAAAADY/j7qhQsSZsA8/s640/sphere.jpg
Healpix résout un problème étroitement lié (pixelating de la sphère de l'égalité de la zone de pixels):
http://healpix.sourceforge.net/
C'est probablement excessif, mais peut-être après l'avoir regardé vous vous rendrez compte que certains de ses autres propriétés sont intéressantes pour vous. C'est plus que juste une fonction qui génère un nuage de points.
J'ai atterri ici pour essayer de trouver de nouveau; le nom de "healpix" ne correspond pas exactement à évoquer les sphères...
avec de petits nombres de points que vous pourriez exécuter une simulation:
Prendre les deux plus grands facteurs de votre
N
, siN==20
puis les deux principaux facteurs sont{5,4}
, ou, plus généralement{a,b}
. CalculerMettre 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 avez déclenché le tour du monde à la fois, par laquelle vous avez appris à propos de{75,150}
quand vous allez à côté de{90-3*dlat/2,(dlong/2)-180}
.Évidemment, je suis le travail en degrés sur la surface de la terre sphérique, avec les conventions habituelles pour la traduction de +/- N/S et E/W. Et évidemment, cela vous donne entièrement non-aléatoire de la distribution, mais il est uniforme et les points ne sont pas regroupés ensemble.
Pour ajouter un certain degré de hasard, vous pouvez générer des 2 normalement distribué (avec une moyenne de 0 et std dev de {dlat/3, dlong/3}) et de les ajouter à votre uniformément répartie points.
edit: Cela ne répond pas à la question de l'OP voulais dire, la laissant ici dans le cas de gens trouvent qu'il est utile en quelque sorte.
Nous utilisons la règle de multiplication de la probabilité, combiné avec infinitessimals. Ce résultats en 2 lignes de code pour atteindre le résultat souhaité:
(défini dans l'exemple suivant le système de coordonnées:)
Votre langue a en général un nombre aléatoire uniforme primitive. Par exemple en python, vous pouvez utiliser
random.random()
pour renvoyer un nombre dans la plage de[0,1)
. Vous pouvez multiplier ce nombre par k pour obtenir un nombre aléatoire dans l'intervalle[0,k)
. Ainsi, en python,uniform([0,2pi))
signifieraitrandom.random()*2*math.pi
.Preuve
Maintenant nous ne pouvons pas attribuer θ uniformément, sinon nous aurions une agglutination dans les pôles. Nous souhaitons attribuer des probabilités proportionnelles à la surface de la sphère wedge (l'θ dans ce diagramme est en fait φ):
Un déplacement angulaire dφ à l'équateur entraînera un déplacement de dφ*r. Quel sera l'effet de déplacement être à l'arbitraire d'un azimut θ? Ainsi, le rayon de l'axe des z est
r*sin(θ)
, de sorte que le arclength de "latitude" coupant le coin estdφ * r*sin(θ)
. Ainsi, nous calculons le distribution cumulée de la zone à échantillonner à partir d'elle, par l'intégration de la zone de la tranche du pôle sud vers le pôle nord.(où des choses=
dφ*r
)Nous allons maintenant tenter d'obtenir l'inverse de la fonction de répartition de l'échantillon à partir d'elle: http://en.wikipedia.org/wiki/Inverse_transform_sampling
Nous avons d'abord normaliser en divisant notre presque-CDF par sa valeur maximale. Cela a pour effet de bord de l'annulation de la dφ et r.
Ainsi:
OU... à la place de 20 points, calculer les centres de la icosahedronal visages. Pour 12 points, trouver les sommets de l'icosaèdre. Pour 30 points, le point milieu de la bords de l'icosaèdre. vous pouvez faire la même chose avec le tétraèdre, le cube, le dodécaèdre et octahedrons: un ensemble de points est sur les sommets, l'autre sur le centre de la face et de l'autre sur le centre de la bords de. Ils ne peuvent pas être mélangées, cependant.
Cela fonctionne et c'est mortel simple. Autant de points que vous le souhaitez: