Die gleichmäßigste Verteilung von Punkten auf der Kugel ist eine unglaublich wichtige Aufgabe in Mathematik, Naturwissenschaften und Computersystemen, und das Anwenden eines Fibonacci-Gitters auf die Oberfläche einer Kugel unter Verwendung derselben Projektion ist eine extrem schnelle und effiziente Näherungsmethode, um sie zu lösen. Ich werde zeigen, wie es mit geringfügigen Änderungen noch besser gemacht werden kann.

Vor einiger Zeit erschien dieser Beitrag auf der Hacker News Homepage. Die Diskussion kann hier gelesen werden .

Einführung

Das Problem der gleichmäßigen Verteilung von Punkten auf einer Kugel hat eine sehr lange Geschichte. Dies ist eines der am besten untersuchten Probleme in der mathematischen Literatur zur sphärischen Geometrie. Es ist von entscheidender Bedeutung in vielen Bereichen der Mathematik, Physik und Chemie, einschließlich Berechnungsmethoden, Approximationstheorie, Codierungstheorie, Kristallographie, Elektrostatik, Computergrafik, Virusmorphologie und vielen anderen.

Leider ist es mit Ausnahme einiger Sonderfälle (nämlich platonischer Körper) unmöglich, Punkte auf einer Kugel perfekt zu verteilen. Darüber hinaus hängt die Lösung des Problems stark von dem Kriterium ab, anhand dessen die Einheitlichkeit bewertet wird. In der Praxis werden viele Kriterien verwendet, darunter:

Verpackung und Beschichtung
Konvexe Rümpfe, Voronoi-Zellen und Delaunay-Dreiecke
Kernel $s$ Reis Energie
Kubatur und Qualifikation

Es ist sehr wichtig, diesen Aspekt zu klären: Normalerweise gibt es keine einzige optimale Lösung für dieses Problem, da eine optimale Lösung, die auf einem Kriterium basiert, oft keine optimale Punkteverteilung für andere ist. Zum Beispiel werden wir auch herausfinden, dass die Verpackungsoptimierung nicht unbedingt eine optimale konvexe Hülle erzeugt und umgekehrt.

Der Kürze halber werden in diesem Beitrag nur zwei Kriterien betrachtet: der minimale Packungsabstand und das konvexe Rumpf / Delaunay-Netz (Volumen und Fläche).

In Abschnitt 1 zeigen wir, wie Sie das kanonische Fibonacci-Raster ändern können, um eine verbesserte Verteilung der Verpackungen zu erreichen . In Abschnitt 2 zeigen wir, wie Sie das kanonische Fibonacci-Gitter ändern können, um verbesserte Parameter für konvexe Hüllen (Volumen und Oberfläche) zu erstellen.

Abschnitt 1. Optimierung des Verpackungsabstands

Dieses Problem wird oft als Tamms-Aufgabe zu Ehren des Botanikers Tamms bezeichnet, der nach einer Erklärung der Oberflächenstruktur von Pollenkörnern suchte. Das Verpackungskriterium erfordert, dass wir den kleinsten Abstand zwischen den Nachbarn für maximieren

$N$ Punkte. Also

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

Dieser Wert nimmt mit der Geschwindigkeit ab.

$~ 1 / \ sqrt {N}$ Daher ist es nützlich, den normalisierten Abstand sowie die asymptotische Grenze des normalisierten Abstands als zu bestimmen

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

Fibonacci-Gitter

Eine sehr elegante Lösung modelliert die in der Natur vorkommenden Knoten, beispielsweise die Verteilung von Samen in einem Sonnenblumen- oder Tannenzapfen. Dieses Phänomen nennt man spiralförmige Phyllotaxis . Coxeter zeigte, dass solche Strukturen einen fundamentalen Zusammenhang mit der Fibonacci-Reihe haben,

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

$F_k = \ {1, 1, 2, 3, 5, 8, 13, ... \}$ und der goldene Schnitt

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

In der Literatur finden sich zwei ähnliche Definitionen der Punktmenge eines sphärischen Fibonacci-Gitters. Die Quelle ist streng für definiert

$N$ gleich einem der Mitglieder der Fibonacci-Reihe,

$F_m$ und gut in der Zahlentheorie studiert.

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

Die zweite Definition verallgemeinert die Formel auf einen beliebigen Betrag

$N$ und wird häufiger in Berechnungen verwendet:

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

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

Unten sehen Sie ein Beispiel für dieselben Fibonacci-Gitter. Durch Transformation können Sie diese Punktmengen in Fibonacci-Spiralen verwandeln, die uns bekannt sind.

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

In ähnlicher Weise können diese Punktmengen vom Einheitsquadrat übertragen werden

$[0, 1] ^ 2$ auf einer Kugel mit einer zylindrischen isometrischen Projektion:

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

$(\ theta, \ phi) \ rechter Pfeil (x, y, z): \ quad \ left (\ cos \ theta \ cos \ phi, \ cos \ theta \ sin \ phi, \ sin \ theta \ rechts)$

Viele verschiedene Versionen von Python-Code dafür finden Sie im Stackoverflow: Gleichmäßige Verteilung von Punkten auf einer Kugel .

Selbst trotz der Tatsache, dass sphärische Fibonacci-Mengen global nicht die beste Verteilung von Proben auf einer Kugel sind (weil ihre Lösungen nicht mit den Lösungen für platonische Körper für übereinstimmen

$n = $ 4,6,8,12,2$ ) haben sie ausgezeichnete Probenahmeeigenschaften und sind im Vergleich zu anderen, komplexeren sphärischen Probenahmeschemata sehr einfach aufzubauen.

Da die Übertragung vom Einheitsquadrat auf die Oberfläche der Kugel durch eine Projektion unter Erhaltung der Fläche erfolgt, ist zu erwarten, dass die Startpunkte bei gleichmäßiger Verteilung auch ziemlich gut auf der Oberfläche der Kugel verteilt sind. Dies bedeutet jedoch nicht, dass die Verteilung nachweislich optimal ist.

Diese Übertragung leidet unter zwei verschiedenen, aber miteinander verbundenen Problemen.

Erstens wird diese Überlagerung durchgeführt, während der Bereich und nicht der Abstand beibehalten werden. Da in unserem Fall die Bedingung darin besteht, den minimalen paarweisen Abstand zwischen Punkten zu maximieren, werden solche Bedingungen und Beziehungen nach der Projektion nicht unbedingt erfüllt sein.

Das zweite Problem ist aus praktischer Sicht am schwierigsten zu lösen: Die Überlagerung weist an jedem Pol zwei entartete Punkte auf. Betrachten Sie zwei Punkte, die sehr nahe am Pol liegen, sich jedoch in der Länge um 180 Grad unterscheiden. Auf einem einzelnen Quadrat (und auf einer zylindrischen Projektion) entsprechen sie zwei sehr weit voneinander entfernten Punkten. Wenn sie jedoch auf die Oberfläche einer Kugel gelegt werden, können sie durch einen sehr kleinen Bogen verbunden werden, der durch den Nordpol verläuft. Aufgrund dieses speziellen Problems sind viele Spiralüberlagerungen nicht optimal genug.

Die aus Gleichung 1 erhaltene sphärische Fibonacci-Helix gibt den Wert an

$d_N ^ *$ für alle

$N$ , also

$d ^ * = 2$ .

Mesh 1

Eine häufigere Version (insbesondere auf Computersystemen), die einen besseren Wert schafft

$d ^ * = 3,09$ hat die Form:

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

Es platziert die Punkte an den Mittelpunkten der Intervalle (gemäß der Mittelpunktsregel in der quadratischen Gauß-Formel), z

$n = 100$ Die Werte der ersten Koordinate sind wie folgt:

$\ {\ 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} \}$

Gitter 2.

Der Schlüssel zur weiteren Verbesserung von Gleichung 2 ist die Erkenntnis, dass

$d ^ * _ N$ entspricht immer dem Abstand zwischen Punkten

$t_0$ und

$t_3$ das sind an den Polen. Das heißt, sich zu verbessern

$d_N$ Punkte in der Nähe der Pole sollten noch weiter voneinander entfernt sein.

Wenn wir folgende Verteilung definieren:

$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$ - Kurven für verschiedene Werte.

$\ varepsilon = 0$ (blau);

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

$\ varepsilon = \ frac {3} {2}$ (grün); und

$\ varepsilon = \ frac {5} {2}$ (rot). Sie können das sehen

$\ varepsilon = \ frac {5} {2}$ gibt Ergebnisse näher an asymptotischen Ergebnissen. Das heißt, mit

$N> 20$ Der folgende einfache Ausdruck erzeugt signifikant bessere Ergebnisse.

$d ^ * = 3,29$ im Vergleich zum kanonischen sphärischen Fibonacci-Gitter:

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

Das heißt, mit

$N = 100$ Die Werte der ersten Koordinate sind gleich:

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

Abbildung 1. Unterschiedliche Werte

$d_N ^ *$ bei verschiedenen Werten

$\ epsilon$ . Je höher der Wert, desto optimaler die Konfiguration. Wir sehen das

$\ epsilon \ simeq 2.5$ bietet eine nahezu optimale Lösung.

Mesh 3.

Wie oben erwähnt, besteht eines der schwerwiegendsten Probleme der gleichmäßigen Verteilung von Punkten auf einer Kugel darin, dass die Optimalität der Verteilung entscheidend von der verwendeten Zielfunktion abhängt. Es stellt sich heraus. dass lokale Mengen mögen

$d_N ^ *$ manchmal „vergeben sie Fehler fast nicht“ - ein einzelner Punkt in einer unzureichend optimalen Position kann die Bewertung der gesamten Punkteverteilung katastrophal reduzieren.

In unserem Fall unabhängig von der Größe

$N$ Wert

$D_N ^ *$ normalerweise definiert durch die vier Punkte, die jedem der Pole am nächsten liegen, insbesondere

$t_0$ und

$t_3$ . Über dieses Gitter ist jedoch auch bekannt, dass sich das größte Voronoi-Polygon am Pol befindet. Also versuchen zu maximieren

$d_N$ Indem wir die ursprünglichen Polarpunkte in einer Reihe teilen, vergrößern wir den Hohlraum am Pol sogar noch mehr! Daher haben wir eine Alternative zu Gitter 2 vorgestellt, die im Allgemeinen vorzuziehen ist, da sie in der Nähe der Pole keinen so großen Hohlraum aufweist.

Es ist fast identisch mit Gitter 2, weist jedoch zwei Unterschiede auf. Erstens benutzt sie

$\ varepsilon = 11/2$ bei

$1 \ leq i \ leq N-2$ . Zweitens daneben

$N-2$ Der erste und der letzte Punkt befinden sich an jedem der Pole.

Also:

$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}$

Eine erstaunliche Eigenschaft dieser Bauweise ist, dass sie trotz der Tatsache, dass ihre Entstehung durch den Wunsch motiviert war, Hohlräume an den Polen zu minimieren, tatsächlich den besten Wert unter allen Methoden aufweist

$d_N$ und

$d ^ *$ mit

$d ^ * = 3,31$ !

Das heißt, mit

$N = 100$ Die Werte der ersten Koordinate lauten wie folgt:

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

Abbildung 2. Verschiedene Gitterkonfigurationen. Das kanonische Fibonacci-Gitter links. Beachten Sie, dass obwohl das mittlere Gitter

$d_N ^ *$ verbessert, an der Stange hat sie eine spürbare Leere. Gitter 3 hat keine Lücke an der Stange und hat den besten Wert

$d_N ^ *$ .

Vergleich

Für große Werte

$N$ dieser Wert

$d ^ *$ Sehr gut vergleichbar mit anderen Methoden, zum Beispiel geodätischen Kuppeln, die auf triangulierten Projektionen von den Flächen platonischer Körper auf die Oberfläche einer Kugel basieren. Es ist nicht überraschend, dass die geodätischen Kuppeln von höchster Qualität auf der Basis des Ikosaeders oder Dodekaeders gebaut werden.

Geodätische Kuppeln auf Ikosaederbasis bei verschiedenen Werten

$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}$

Geodätische Kuppeln auf Dodekaederbasis für verschiedene Werte

$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}$

Zusätzlich ein abgeschnittenes Ikosaeder, das der Form von Fulleren entspricht

$C_ {60}$ hat nur

$d ^ * = 3.125$ .

Das heißt, mit

$N> 100$ Das auf Gleichung 3 basierende Netz ist besser als jedes geodätische Polyeder.

Gemäß den Daten aus der ersten Quelle in der nachstehenden Referenzliste weisen einige der modernen Methoden, die normalerweise komplex sind und eine rekursive und / oder dynamische Programmierung erfordern, die folgenden Indikatoren auf.

$\ begin {array} {| lr |} \ hline \ text {Gitter 1} & 3.09 \\ \ hline \ text {Maximale Determinante} & 3.19 \\ \ hline \ text {Gitter 2} & 3.28 \\ \ hline \ text {Gitter 3} & 3.31 \\ \ hline \ text {Zonale gleiche Fläche} & 3.32 \\ \ hline \ text {Coulomb} & 3.37 \\ \ hline \ text {Log Energy} & 3.37 \\ \ hline \ end { Array}$

Schlussfolgerung aus Abschnitt 1

Das durch Gleichung 3 erstellte Gitter 3 ist eine Modifikation des kanonischen Fibonacci-Gitters, das eine viel bessere Verpackung für die Verteilung von Punkten bietet. Also

$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$

Abschnitt 2. Optimierung der konvexen Hülle (Delaunay-Netz)

Im vorherigen Abschnitt haben wir die Verteilung um optimiert

$d ^ * _ N$ Diese Modifikationen verschlechtern jedoch andere Indikatoren, beispielsweise das Volumen einer konvexen Hülle (Delaunay-Netz). In diesem Abschnitt wird beschrieben, wie Sie Punkte auf einer Kugel gleichmäßig verteilen, um einen globaleren Indikator wie das Volumen einer konvexen Hülle zu optimieren (zu maximieren).

Wir bezeichnen

$C_N$ wie eine konvexe Hülle

$N$ Punkte

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

Normalisierungsfaktor enthalten

$N$ , weil die absolute Diskrepanz mit der Geschwindigkeit abnimmt

$~ 1 / N$ .

Verhalten

$\ epsilon_N$ bei verschiedenen

$N$ ist in Abbildung 3 (blaue Linie) zu sehen.

Um die Nichtübereinstimmung der Volumina zu verringern, sollte beachtet werden, dass trotz der Verwendung von

$\ phi$ , aus der Logik des Goldenen Schnitts bei

$N \ rightarrow \ infty$ Daraus folgt nicht unbedingt, dass es der beste Wert für das Finale ist

$N$ . Wissenschaftlich gesehen können wir sagen, dass wir den Einfluss der Korrektur von Gliedmaßen berücksichtigen müssen.

Fassen wir Gleichung 1 wie folgt zusammen:

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

wo wir definieren

$g (n)$ wie

$g (n) = \ begin {Fälle} 3- \ phi, & \ text {wenn $ k $ gerade ist} \\ \ phi, & \ text {wenn $ k $ ungerade ist} \ end {Fälle} \ tag {5}$

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

$\ lfloor x \ rfloor$ - die Funktion des Abrundens auf die nächste ganze Zahl.

Abbildung 3 zeigt, wie stark die Volumenfehlanpassung für die Hälfte der Werte optimiert ist.

$N$ .

Der Grund dafür ist eine wenig bekannte Tatsache: alle Zahlen

$x$ Die Befriedigung der speziellen Mobius-Transformation, ausgehend von Irrationalität, ist gleichwertig

$\ phi$ .

$x = \ frac {a \ phi + b} {c \ phi + d}, \ quad \ textrm {für alle ganzen Zahlen} \; \; a, b, c, d \; \ textrm {so dass} | ad-bc | = 1$

Daher der Grund dafür

$\ phi$ und

$3- \ phi$ so gut zusammenpassen, ist das

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

Abbildung 3. Die Nichtübereinstimmung zwischen dem Volumen der konvexen Hülle von Punkten und dem Volumen der Einheitskugel. Denken Sie daran, je kleiner es ist, desto besser. Die Abbildung zeigt, dass das Hybridmodell (orange Linie) auf basiert

$\ phi$ und

$3- \ phi$ bietet eine bessere Punkteverteilung als das kanonische Fibonacci-Gitter (blaue Linie).

Für die verbleibende Hälfte definieren wir zunächst eine Hilfsreihe

$A_N$ eine Variation der Fibonacci-Serie

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

Also

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

Alle Brüche dieser Reihe haben elegante kontinuierliche Brüche und konvergieren im Grenzfall zu

$\ phi$ . Zum Beispiel

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

Jetzt können wir vollständig verallgemeinern

$g (n)$ wie folgt:

$g (N) = \ begin {Fälle} 3- \ phi, & \ text {wenn $ k $ gerade ist} \\ A_ {j + 1} / A_j, & \ text {wenn $ k $ ungerade ist, wo $ j = (k + 7) / 2 $} \ end {case} \ tag {6}$

Die folgende Tabelle zeigt die Werte

$g (N)$ für verschiedene

$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}$

Abbildung 4 zeigt, dass diese neue Verteilung in Bezug auf das Volumen der konvexen Hülle für alle Werte besser ist als das kanonische Gitter

$n$

Abbildung 4. Die Nichtübereinstimmung zwischen dem Volumen der konvexen Hülle und dem Volumen der Einheitskugel. Je niedriger der Wert, desto besser. Dies zeigt uns, dass die vorgeschlagene neue Methode (grüne Linie) ständig eine bessere Verteilung liefert als das kanonische Fibonacci-Gitter (blaue Linie).

Abbildung 5. Visueller Vergleich des kanonischen Netzes (links) mit dem neuen modifizierten Netz (rechts) mit n = 35 und n = 150. Optisch sind die Unterschiede kaum wahrnehmbar. Unter Bedingungen, die maximale Effizienz erfordern, bietet die modifizierte Version (rechts) eine kleine, aber quantifizierbare Verbesserung sowohl des Volumens als auch der Oberfläche der konvexen Hülle.

Seltsamerweise ist diese Verteilung ebenfalls unbedeutend, verringert jedoch stetig die Fehlanpassung zwischen der Oberfläche der konvexen Hülle und der Oberfläche einer einzelnen Kugel. Dies ist in Abbildung 6 dargestellt.

Abbildung 5. Normalisierte Nichtübereinstimmung von Bereichen zwischen der Oberfläche einer konvexen Hülle (Delaunay-Netz) und der Oberfläche einer einzelnen Kugel. Je niedriger der Wert, desto besser. Dies zeigt, dass die vorgeschlagene neue Modifikation (grüne Punkte) eine kleine, aber konstante Abnahme des Oberflächenunterschieds im Vergleich zum kanonischen Fibonacci-Gitter (blaue Punkte) zeigt.

Schlussfolgerung aus Abschnitt 2

Das Gitter, das Gleichung 6 entspricht, ist eine Modifikation des kanonischen Fibonacci-Gitters, wodurch eine viel bessere Verteilung der Punkte basierend auf dem Volumen und der Oberfläche der konvexen Hülle (Delaunay-Gitter) erzeugt wird.

Quellen

Gleichmäßige Verteilung der Punkte auf einer Kugel

Einführung

Abschnitt 1. Optimierung des Verpackungsabstands

Abschnitt 2. Optimierung der konvexen Hülle (Delaunay-Netz)

More articles: