La distribution la plus uniforme des points sur la sphère est une tâche incroyablement importante en mathématiques, en sciences et en systèmes informatiques, et l'application d'une grille de Fibonacci à la surface d'une sphère en utilisant la même projection est une méthode d'approximation extrêmement rapide et efficace pour la résoudre. Je vais montrer comment, avec des modifications mineures, cela peut être encore amélioré.

Il y a quelque temps, ce message est apparu sur la page d'accueil de Hacker News. Sa discussion peut être lue ici .

Présentation

Le problème de la distribution uniforme des points sur une sphère a une très longue histoire. C'est l'un des problèmes les plus étudiés de la littérature mathématique sur la géométrie sphérique. Il est d'une importance critique dans de nombreux domaines des mathématiques, de la physique, de la chimie, y compris les méthodes de calcul, la théorie de l'approximation, la théorie du codage, la cristallographie, l'électrostatique, l'infographie, la morphologie des virus et bien d'autres.

Malheureusement, à l'exception de quelques cas particuliers (à savoir les solides platoniciens), il est impossible de répartir parfaitement les points sur une sphère. De plus, la solution du problème dépend fortement du critère utilisé pour évaluer l'uniformité. En pratique, de nombreux critères sont utilisés, notamment:

Emballage et revêtement
Coques convexes, cellules de Voronoi et triangles de Delaunay
Noyaux $s$ Énergie du riz
Cubature et qualificatifs

Il est très important de clarifier cet aspect: il n'y a généralement pas de solution optimale unique à ce problème, car une solution optimale basée sur un critère n'est souvent pas une distribution optimale de points pour les autres. Par exemple, nous découvrirons également que l'optimisation de l'emballage ne crée pas nécessairement une coque convexe optimale et vice versa.

Par souci de brièveté, dans cet article, nous ne considérerons que deux critères: la distance minimale d'emballage et le maillage coque convexe / Delaunay (volume et surface).

Dans la section 1, nous montrons comment vous pouvez changer la grille canonique de Fibonacci pour construire une distribution améliorée de l'emballage . Dans la section 2, nous montrons comment vous pouvez modifier la grille canonique de Fibonacci pour construire des paramètres améliorés pour les coques convexes (volume et surface).

Section 1. Optimisation de la distance d'emballage

Souvent, ce problème est appelé la tâche du Tamm en l'honneur du botaniste Tems, qui a cherché une explication de la structure de surface des grains de pollen. Le critère d'emballage nous oblige à maximiser la plus petite distance entre voisins pour

$N$ des points. C’est

$d_N = \ min_ {i \ neq j} | x_i - x_j |$

Cette valeur diminue avec la vitesse.

$~ 1 / \ sqrt {N}$ , par conséquent, il sera utile de déterminer la distance normalisée, ainsi que la limite asymptotique de la distance normalisée, comme

$d ^ * _ N = \ sqrt {N} d_N, \ quad \ quad d ^ * = \ lim_ {N \ rightarrow \ infty} d ^ * _ N$

Grille de Fibonacci

Une solution très élégante modélise les nœuds trouvés dans la nature, par exemple, la distribution des graines dans un tournesol ou une pomme de pin. Ce phénomène est appelé phyllotaxie spirale. Coxeter a montré que ces structures ont un lien fondamental avec la série de Fibonacci,

F_k = \ {1, 1, 2, 3, 5, 8, 13, ... \}

$F_k = \ {1, 1, 2, 3, 5, 8, 13, ... \}$ et le nombre d'or

$\ phi = (1+ \ sqrt {5}) / 2$ .

Dans la littérature, on trouve deux définitions similaires de l'ensemble des points d'une grille sphérique de Fibonacci. La source est définie strictement pour

$N$ égal à l'un des membres de la série Fibonacci,

$F_m$ , et bien étudié en théorie des nombres.

$t_i = \ left (\ frac {i} {F_m}, \ frac {i F_ {m-1}} {F_m} \ right) \ quad \ textrm {for} \; 0 \ leq i \ leq N-1$

La deuxième définition généralise la formule à un montant arbitraire

$N$ et est utilisé plus souvent dans les calculs:

$t_i = \ left (\ frac {i} {N}, \ frac {i} {\ phi} \ right) \ quad \ textrm {for} \; 0 \ leq i \ leq N \ tag {1}$

où

$\ phi = \ frac {1+ \ sqrt {5}} {2} = \ lim_ {n \ rightarrow \ infty} \ left (\ frac {F_ {n + 1}} {F_n} \ right)$

Voici un exemple des mêmes grilles de Fibonacci. Par transformation, vous pouvez transformer ces ensembles de points en spirales de Fibonacci que nous connaissons bien.

$(r, \ theta) = (\ sqrt {x_1}, 2 \ pi x_2)$

De même, ces ensembles de points peuvent être transférés du carré unitaire

$[0, 1] ^ 2$ sur une sphère à l'aide d'une projection isométrique cylindrique:

$(x, y) \ rightarrow (\ theta, \ phi): \ quad \ left (\ cos ^ {- 1} (2x-1) - \ pi / 2, 2 \ pi y \ right)$

$(\ theta, \ phi) \ rightarrow (x, y, z): \ quad \ left (\ cos \ theta \ cos \ phi, \ cos \ theta \ sin \ phi, \ sin \ theta \ right)$

De nombreuses versions différentes du code Python peuvent être trouvées sur stackoverflow: répartir uniformément les points sur une sphère .

Même en dépit du fait que les ensembles sphériques de Fibonacci ne sont pas globalement la meilleure distribution d'échantillons sur une sphère (car leurs solutions ne coïncident pas avec les solutions de solides platoniciens pour

$inline$ ), ils ont d'excellentes propriétés d'échantillonnage et sont très faciles à construire par rapport à d'autres schémas d'échantillonnage sphériques plus complexes.

Étant donné que le transfert du carré unitaire à la surface de la sphère est effectué par une projection avec préservation de la zone, on peut s'attendre à ce que si les points de départ sont uniformément répartis, ils seront également assez bien répartis à la surface de la sphère. Cependant, cela ne signifie pas que la distribution sera prouvée optimale.

Ce transfert souffre de deux problèmes différents mais liés.

Tout d'abord, cette superposition est effectuée tout en maintenant la zone, pas la distance. Étant donné que dans notre cas, la condition est de maximiser la distance minimale par paire entre les points, de telles conditions et relations ne seront pas nécessairement satisfaites après la projection.

Le deuxième problème est le plus difficile à résoudre d'un point de vue pratique: la superposition a deux points dégénérés à chaque pôle. Considérons deux points très proches du pôle, mais différant de 180 degrés en longitude. Sur un seul carré (et sur une projection cylindrique) ils correspondront à deux points très éloignés l'un de l'autre, cependant, superposés à la surface d'une sphère, ils pourront être reliés par un très petit arc passant par le pôle nord. En raison de ce problème particulier, de nombreux superpositions en spirale ne sont pas suffisamment optimales.

L'hélice sphérique de Fibonacci obtenue à partir de l'équation 1 donne la valeur

$d_N ^ *$ pour tous

$N$ c'est

$d ^ * = 2$ .

Maille 1

Une version plus courante (en particulier sur les systèmes informatiques) qui crée une meilleure valeur

$d ^ * = 3,09$ a la forme:

$t_i = \ left (\ frac {i + 1/2} {N}, \ frac {i} {\ phi} \ right) \ quad \ textrm {for} \; 0 \ leq i \ leq N-1 \ tag {2}$

Il place les points au milieu des intervalles (selon la règle du milieu de la formule quadratique de Gauss), donc, pour

$n = 100$ , les valeurs de la première coordonnée seront les suivantes:

$\ {\ frac {0.5} {100}, \ frac {1.5} {100}, \ frac {2.5} {100}, \ ldots, \ frac {97.5} {100}, \ frac {98.5} {100} , \ frac {99.5} {100} \}$

Grille 2.

La clé pour améliorer encore l'équation 2 est la prise de conscience que

$d ^ * _ N$ correspond toujours à la distance entre les points

$t_0$ et

$t_3$ qui sont aux pôles. Autrement dit, pour améliorer

$d_N$ les points proches des pôles doivent être encore plus espacés.

Si nous définissons la distribution suivante:

$t_i (\ varepsilon) = \ left (\ frac {i + 1/2 + \ varepsilon} {N + 2 \ varepsilon}, \ frac {i} {\ phi} \ right) \ quad \ textrm {for} \ ; 0 \ leq i \ leq N-1$

$d ^ * _ N$ - courbes pour différentes valeurs.

$\ varepsilon = 0$ (bleu);

$\ varepsilon = \ frac {1} {2}$ (orange);

$\ varepsilon = \ frac {3} {2}$ (vert); et

$\ varepsilon = \ frac {5} {2}$ (rouge). Vous voyez

$\ varepsilon = \ frac {5} {2}$ donne des résultats plus proches des résultats asymptotiques. Autrement dit, avec

$N> 20$ L'expression simple suivante génère des résultats nettement meilleurs.

$d ^ * = 3,29$ par rapport à la grille sphérique canonique de Fibonacci:

$t_i = \ left (\ frac {i + 3} {N + 5}, \ frac {i} {\ phi} \ right) \ quad \ textrm {for} \; 0 \ leq i \ leq N-1 \ tag {3}$

Autrement dit, avec

$N = 100$ les valeurs de la première coordonnée seront égales à:

$\ {\ frac {3} {105}, \ frac {4} {105}, \ frac {5} {105}, \ ldots, \ frac {100} {105}, \ frac {101} {105} , \ frac {102} {105} \}$

Figure 1. Différentes valeurs

$d_N ^ *$ à différentes valeurs

$\ epsilon$ . Plus la valeur est élevée, plus la configuration est optimale. On voit que

$\ epsilon \ simeq 2.5$ fournit une solution quasi optimale.

Maille 3.

Comme mentionné ci-dessus, l'un des problèmes les plus graves de la distribution uniforme des points sur une sphère est que l'optimalité de la distribution dépend de manière critique de la fonction objective utilisée. Cela s'avère. que des quantités locales comme

$d_N ^ *$ parfois, ils «ne pardonnent presque pas» - un seul point dans une position insuffisamment optimale peut réduire de façon catastrophique l'évaluation de la distribution entière des points.

Dans notre cas, quelle que soit l'ampleur

$N$ valeur

$D_N ^ *$ généralement défini par les quatre points les plus proches de chacun des pôles, en particulier

$t_0$ et

$t_3$ . Cependant, on sait également à propos de cette grille que le plus grand polygone de Voronoï est au pôle. Donc, essayer de maximiser

$d_N$ en divisant les points polaires d'origine dans une rangée, nous augmentons encore plus le vide au pôle! Par conséquent, nous avons présenté une alternative à la grille 2, qui est généralement préférable car elle ne montre pas un si grand vide près des pôles.

Il est presque identique à la grille 2, mais présente deux différences. Tout d'abord, elle utilise

$\ varepsilon = 11/2$ à

$1 \ leq i \ leq N-2$ . Deuxièmement, outre ces

$N-2$ Le premier et le dernier point sont situés à chacun des pôles.

Soit:

$t_0 = (0,0); \; t_n = (1,0); \ quad t_i = \ left (\ frac {i + 6} {N + 11}, \ frac {i} {\ phi} \ right) \ quad \ textrm {for} \; 1 \ leq i \ leq N-2 \ tag {4}$

Une propriété étonnante de cette méthode de construction est que, malgré le fait que sa création ait été motivée par le désir de minimiser les vides aux pôles, elle a en fait la meilleure valeur parmi toutes les méthodes

$d_N$ et

$d ^ *$ avec

$d ^ * = 3,31$ !

Autrement dit, avec

$N = 100$ les valeurs de la première coordonnée seront les suivantes:

$\ {0; \; \ frac {7} {111}, \ frac {8} {111}, \ frac {9} {1111}, \ ldots, \ frac {102} {111}, \ frac {103} {111}, \ frac {104} {111}; \; 1 \}$

Figure 2. Différentes configurations de grille. La grille canonique de Fibonacci à gauche. Notez que même si la grille du milieu

$d_N ^ *$ amélioré, au pôle, elle a un vide notable. La grille 3 n'a pas de vide au pôle et a la meilleure valeur

$d_N ^ *$ .

Comparaison

Pour les grandes valeurs

$N$ cette valeur

$d ^ *$ extrêmement bien comparable à d'autres méthodes, par exemple, les dômes géodésiques, qui sont basés sur des projections triangulées des faces des solides platoniciens sur la surface d'une sphère. Il n'est pas surprenant que les dômes géodésiques de la plus haute qualité soient construits sur la base de l'icosaèdre ou du dodécaèdre.

Dômes géodésiques à base d'icosaèdres à différentes valeurs

$N$ .

$\ begin {array} {| c | cccccccccc |} \ hline N & 12 & 42 & 92 & 162 & 252 & 362 & 492 & 642 & 812 & 1002 \\ \ hline d ^ * & 3.64 & 3.54 & 3.34 & 3.22 & 3.15 & 3.09 & 3.06 & 3.03 & 3.00 & 2.99 \\ \ hline \ end {array}$

Dômes géodésiques à base de dodécaèdre pour différentes valeurs

$N$ .

$\ begin {array} {| c | ccccccc |} \ hline N & 20 & 32 & 122 & 272 & 482 & 752 & 1082 \\ \ hline d ^ * & 3.19 & 3.63 & 3.16 & 2.99 & 2.90 & 2.84 & 2,81 \\ \ hline \ end {array}$

De plus, un icosaèdre tronqué correspondant à la forme du fullerène

$C_ {60}$ a seulement

$d ^ * = 3,125$ .

Autrement dit, avec

$N> 100$ le maillage basé sur l'équation 3 est meilleur que n'importe quel polyèdre géodésique.

Selon les données de la première source dans la liste de références ci-dessous, certaines des méthodes modernes, qui sont généralement complexes et nécessitent une programmation récursive et / ou dynamique, ont les indicateurs suivants.

$\ begin {array} {| lr |} \ hline \ text {Lattice 1} & 3.09 \\ \ hline \ text {Max Determinant} & 3.19 \\ \ hline \ text {Lattice 2} & 3.28 \\ \ hline \ text {Lattice 3} & 3.31 \\ \ hline \ text {Zonal Equal Area} & 3.32 \\ \ hline \ text {Coulomb} & 3.37 \\ \ hline \ text {Log Energy} & 3.37 \\ \ hline \ end { tableau}$

Conclusion de la section 1

La grille 3, créée par l'équation 3, est une modification de la grille canonique de Fibonacci, qui offre un bien meilleur emballage pour la distribution des points. C’est

$t_0 = (0,0); \; \; t_i = \ left (\ frac {i + 6} {N + 11}, \ frac {i} {\ phi} \ right); \; \; t_ {N-1} = (0,1); \ quad \ textrm {for} \; 1 \ leq i \ leq N-2$

Section 2. Optimisation de la coque convexe (maille Delaunay)

Dans la section précédente, nous avons optimisé la distribution en

$d ^ * _ N$ Cependant, ces modifications aggravent d'autres indicateurs, par exemple le volume d'une coque convexe (maille Delaunay). Cette section décrit comment répartir uniformément les points sur une sphère de manière à optimiser (maximiser) un indicateur plus global comme le volume d'une coque convexe.

Nous dénotons

$C_N$ comme une coque convexe

$N$ des points

$\ epsilon_N = N \ left (\ frac {4 \ pi} {3} \; - \ textrm {Vol} (C_N) \ right)$

facteur de normalisation inclus

$N$ , car l'écart absolu diminue avec la vitesse

$~ 1 / N$ .

Comportement

$\ epsilon_N$ à divers

$N$ peut être vu sur la figure 3 (ligne bleue).

Pour réduire l'inadéquation des volumes, il convient de noter que malgré l'utilisation de

$\ phi$ , de la logique de la section d'or à

$N \ rightarrow \ infty$ il ne s'ensuit pas nécessairement que c'est la meilleure valeur pour la finale

$N$ . Parlant scientifiquement, nous pouvons dire que nous devons prendre en compte l'influence de la correction des membres.

Résumons l'équation 1 comme suit:

$t_i = \ left (\ frac {i + 1/2} {N}, \ frac {i} {g (N)} \ right) \ quad \ textrm {for} \; 0 \ leq i \ leq N-1 \ tag {4}$

où nous définissons

$g (n)$ comment

$g (n) = \ begin {cases} 3- \ phi, & \ text {si $ k $ est pair} \\ \ phi, & \ text {si $ k $ est impair} \ end {cases} \ tag {5}$

où

$k = \ left \ lfloor \ textrm {log} _ {\ phi} (\ frac {n} {1.5}) \ right \ rfloor = \ left \ lfloor \ frac {\ ln (n / 1.5)} {\ ln \ phi} \ right \ rfloor$

où

$\ lfloor x \ rfloor$ - la fonction d'arrondi à l'entier inférieur le plus proche.

La figure 3 montre la différence de volume qui est optimisée pour la moitié des valeurs.

$N$ .

La raison en est un fait peu connu: tous les chiffres

$x$ satisfaisant la transformation spéciale de Mobius, à partir de l'irrationalité, sont équivalentes

$\ phi$ .

$x = \ frac {a \ phi + b} {c \ phi + d}, \ quad \ textrm {pour tous les entiers} \; \; a, b, c, d \; \ textrm {tel que} | ad-bc | = 1$

Par conséquent, la raison pour laquelle

$\ phi$ et

$3- \ phi$ s'emboîtent si bien, c'est que

$\ frac {1} {\ phi} = \ frac {\ phi + 1} {2 \ phi + 1}, \ quad \ quad \ frac {1} {3- \ phi} = \ frac {2 \ phi + 1} {1 \ phi + 1}$

Figure 3. Inadéquation entre le volume de la coque de points convexe et le volume de la sphère unitaire. Gardez à l'esprit que plus il est petit, mieux c'est. La figure montre que le modèle hybride (ligne orange) basé sur

$\ phi$ et

$3- \ phi$ , fournit une meilleure distribution des points que la grille canonique de Fibonacci (ligne bleue).

Pour la moitié restante, nous définissons d'abord une série auxiliaire

$A_N$ étant une variation de la série Fibonacci

$A_1 = 1, \; A_2 = 4; \; A_ {n + 2} = A_ {n + 1} + A_n \; \ textrm {for} n = 1,2,3, ...$

C’est

$A_N = 1,4,5,9,14,23,37,60,97,157,254,411, ...$

Toutes les fractions de cette série ont des fractions continues élégantes et, à la limite, convergent vers

$\ phi$ . Par exemple

$t _5 / t_4 = 1+ \ cfrac {1} {1+ \ cfrac {1} {1+ \ cfrac {1} {1+ \ cfrac {1} {4}}}}$

Maintenant, nous pouvons pleinement généraliser

$g (n)$ comme suit:

$g (N) = \ begin {cases} 3- \ phi, & \ text {si $ k $ est pair} \\ A_ {j + 1} / A_j, & \ text {si $ k $ est impair, où $ j = (k + 7) / 2 $} \ end {cases} \ tag {6}$

Le tableau ci-dessous montre les valeurs

$g (N)$ pour divers

$N$ .

$\ begin {array} {| c | c | c | c | c | c | c | c | c |} \ hline N & 4-6 & 7-10 & 11-16 & 17-26 & 27-43 & 44- 70 & 71-114 & 115-184 & 185-300 \\ \ hline g (n) & 3- \ phi & \ frac {23} {14} & 3- \ phi & \ frac {37} {23} & 3- \ phi & \ frac {60} {37} & 3- \ phi & \ frac {97} {60} & 3- \ phi \\ \ hline \ end {array}$

La figure 4 montre que par rapport au volume de la coque convexe, cette nouvelle distribution est meilleure que la grille canonique pour toutes les valeurs

$n$

Figure 4. Décalage entre le volume de la coque convexe et le volume de la sphère unitaire. Plus la valeur est basse, mieux c'est. Cela nous indique que la nouvelle méthode proposée (ligne verte) fournit constamment une meilleure distribution que la grille canonique de Fibonacci (ligne bleue).

Figure 5. Comparaison visuelle du maillage canonique (à gauche) avec le nouveau maillage modifié (à droite) avec n = 35 et n = 150. Visuellement, les différences sont presque imperceptibles. Cependant, dans des conditions nécessitant une efficacité maximale, la version modifiée (à droite) apporte une amélioration modeste mais quantifiable du volume et de la surface de la coque convexe.

Curieusement, cette distribution est également insignifiante, mais réduit progressivement l'inadéquation entre la surface de la coque convexe et la surface d'une seule sphère. Ceci est illustré à la figure 6.

Figure 5. Inadéquation normalisée des zones entre la surface d'une coque convexe (maillage Delaunay) et la surface d'une seule sphère. Plus la valeur est basse, mieux c'est. Cela montre que la nouvelle modification proposée (points verts) démontre une diminution faible mais constante de la différence de surfaces par rapport à la grille canonique de Fibonacci (points bleus)

Conclusion de la section 2

La grille correspondant à l'équation 6 est une modification de la grille canonique de Fibonacci, créant une meilleure répartition des points en fonction du volume et de la surface de la coque convexe (grille de Delaunay).

Les sources

Répartition uniforme des points sur une sphère

Présentation

Section 1. Optimisation de la distance d'emballage

Section 2. Optimisation de la coque convexe (maille Delaunay)

More articles: