Gleichmäßige Verteilung von n Punkten auf einer Kugel

120

Ich brauche einen Algorithmus, der mir Positionen um eine Kugel für N Punkte (wahrscheinlich weniger als 20) geben kann, die sie vage ausbreiten. Es gibt keine Notwendigkeit für "Perfektion", aber ich brauche es nur, damit keiner von ihnen zusammengeballt ist.

  • Diese Frage lieferte guten Code, aber ich konnte keinen Weg finden, diese Uniform zu erstellen, da dies zu 100% zufällig schien.
  • Dieser empfohlene Blog-Beitrag hatte zwei Möglichkeiten, die Eingabe der Anzahl der Punkte auf der Kugel zu ermöglichen, aber der Saff- und Kuijlaars- Algorithmus befindet sich genau im Pseudocode, den ich transkribieren konnte, und das Codebeispiel, das ich gefunden habe, enthielt "node [k]", was ich nicht konnte siehe erklärt und ruiniert diese Möglichkeit. Das zweite Blog-Beispiel war die Golden Section Spiral, die mir seltsame, gebündelte Ergebnisse lieferte, ohne dass eine eindeutige Möglichkeit zur Definition eines konstanten Radius bestand.
  • Dieser Algorithmus aus dieser Frage scheint möglicherweise zu funktionieren, aber ich kann nicht zusammenfassen, was auf dieser Seite in Pseudocode oder so etwas enthalten ist.

Einige andere Fragethreads, auf die ich gestoßen bin, sprachen von einer zufälligen gleichmäßigen Verteilung, was zu einer Komplexität führt, über die ich mir keine Sorgen mache. Ich entschuldige mich, dass dies eine so dumme Frage ist, aber ich wollte zeigen, dass ich wirklich hart ausgesehen habe und trotzdem zu kurz gekommen bin.

Was ich also suche, ist ein einfacher Pseudocode, um N Punkte gleichmäßig um eine Einheitskugel zu verteilen, die entweder in sphärischen oder kartesischen Koordinaten zurückkehrt. Noch besser, wenn es sich sogar mit ein wenig Randomisierung verteilen kann (denken Sie an Planeten um einen Stern, anständig verteilt, aber mit Raum für Spielraum).

Widerfahren
quelle
Was meinst du mit "ein bisschen Randomisierung"? Meinen Sie Störungen in gewissem Sinne?
Ninjagecko
32
OP ist verwirrt. Was er sucht, ist, n-Punkte auf eine Kugel zu setzen, damit der Mindestabstand zwischen zwei beliebigen Punkten so groß wie möglich ist. Dies gibt den Punkten den Anschein, "gleichmäßig" über die gesamte Kugel verteilt zu sein. Dies hat nichts mit der Schaffung einer gleichmäßigen Zufallsverteilung auf einer Kugel zu tun. Darum geht es bei vielen dieser Links und bei vielen der folgenden Antworten.
BlueRaja - Danny Pflughoeft
1
20 sind nicht viele Punkte, die auf einer Kugel platziert werden müssen, wenn Sie nicht möchten, dass sie nur zufällig aussehen.
John Alexiou
2
Hier ist eine Möglichkeit, dies zu tun (es gibt Codebeispiele): pdfs.semanticscholar.org/97a6/… (sieht aus, als würde es Abstoßungskraftberechnungen verwenden)
trusktr
1
Natürlich gibt es für Werte auf N in {4, 6, 8, 12, 20} exakte Lösungen, bei denen der Abstand von jedem Punkt zu (jedem) seiner nächsten Nachbarn eine Konstante für alle Punkte und alle nächsten Nachbarn ist.
dmckee --- Ex-Moderator Kätzchen

Antworten:

13

In diesem Beispiel ist Code node[k] nur der k-te Knoten. Sie generieren ein Array mit N Punkten und node[k]ist das k-te (von 0 bis N-1). Wenn das alles ist, was Sie verwirrt, können Sie das hoffentlich jetzt verwenden.

(Mit anderen Worten, es khandelt sich um ein Array der Größe N, das vor dem Start des Codefragments definiert wird und eine Liste der Punkte enthält.)

Alternativ können Sie hier auf der anderen Antwort aufbauen (und Python verwenden):

> 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

Wenn Sie das zeichnen, werden Sie feststellen, dass der vertikale Abstand in der Nähe der Pole größer ist, sodass sich jeder Punkt auf ungefähr derselben Gesamtfläche befindet (in der Nähe der Pole gibt es "horizontal" weniger Platz, sodass mehr "vertikal" entsteht. ).

Dies ist nicht dasselbe wie alle Punkte, die ungefähr den gleichen Abstand zu ihren Nachbarn haben (worüber ich denke, dass Ihre Links sprechen), aber es kann für das, was Sie wollen, ausreichen und verbessert, einfach ein einheitliches Lat / Lon-Gitter zu erstellen .

Andrew Cooke
quelle
Schön, es ist gut, eine mathematische Lösung zu sehen. Ich dachte daran, eine Helix- und Bogenlängentrennung zu verwenden. Ich bin mir immer noch nicht sicher, wie ich die optimale Lösung finden kann, was ein interessantes Problem ist.
Robert King
Hast du gesehen, dass ich meine Antwort so bearbeitet habe, dass sie oben eine Erklärung für Knoten [k] enthält? Ich denke, das kann alles sein, was Sie brauchen ...
Andrew Cooke
Wunderbar, danke für die Erklärung. Ich werde es später ausprobieren, da ich momentan keine Zeit habe, aber vielen Dank, dass Sie mir geholfen haben. Ich werde Sie wissen lassen, wie es für meine Zwecke funktioniert. ^^
Befall
Die Verwendung der Spiralmethode passt perfekt zu meinen Bedürfnissen, vielen Dank für die Hilfe und Klarstellung. :)
Befall
13
Der Link scheint tot zu sein.
Scheintod
139

Der Fibonacci-Kugelalgorithmus ist dafür großartig. Es ist schnell und liefert Ergebnisse, die auf einen Blick das menschliche Auge leicht täuschen. Sie können ein Beispiel für die Verarbeitung sehen, das das Ergebnis im Laufe der Zeit anzeigt, wenn Punkte hinzugefügt werden. Hier ist ein weiteres großartiges interaktives Beispiel von @gman. Und hier ist eine einfache Implementierung in Python.

import math


def fibonacci_sphere(samples=1):

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

    for i in range(samples):
        y = 1 - (i / float(samples - 1)) * 2  # y goes from 1 to -1
        radius = math.sqrt(1 - y * y)  # radius at y

        theta = phi * i  # golden angle increment

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

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

    return points

1000 Proben geben Ihnen Folgendes:

Geben Sie hier die Bildbeschreibung ein

Fnord
quelle
Bei der Definition von phi wird eine Variable n aufgerufen: phi = ((i + rnd)% n) * Inkrement. Ist n = Proben?
Andrew Staroscik
@ AndrewStaroscik ja! Als ich den Code zum ersten Mal schrieb, benutzte ich "n" als Variable und änderte den Namen später, führte aber keine Due Diligence durch. Danke, dass du das verstanden hast!
Fnord
4
@Xarbrough Der Code gibt Ihnen Punkte um eine Einheitskugel, also multiplizieren Sie einfach jeden Punkt mit dem Skalar, den Sie für den Radius wünschen.
Fnord
2
@Fnord: Können wir das für höhere Dimensionen tun?
Pikachuchameleon
107

Die goldene Spiralmethode

Sie sagten, Sie könnten die Methode der goldenen Spirale nicht zum Laufen bringen, und das ist eine Schande, weil sie wirklich sehr, sehr gut ist. Ich möchte Ihnen ein umfassendes Verständnis davon geben, damit Sie vielleicht verstehen, wie Sie verhindern können, dass dies „zusammengeballt“ wird.

Hier ist eine schnelle, nicht zufällige Methode, um ein Gitter zu erstellen, das ungefähr korrekt ist. Wie oben diskutiert, ist kein Gitter perfekt, aber dies kann gut genug sein. Es wird mit anderen Methoden verglichen, z. B. bei BendWavy.org, aber es hat nur ein schönes und hübsches Aussehen sowie eine Garantie für gleichmäßige Abstände im Limit.

Grundierung: Sonnenblumenspiralen auf der Gerätescheibe

Um diesen Algorithmus zu verstehen, lade ich Sie zunächst ein, sich den 2D-Sonnenblumen-Spiral-Algorithmus anzusehen. Dies basiert auf der Tatsache, dass die irrationalste Zahl der goldene Schnitt ist. (1 + sqrt(5))/2Wenn man Punkte durch den Ansatz "in der Mitte stehen, einen goldenen Schnitt ganzer Umdrehungen drehen und dann einen anderen Punkt in diese Richtung emittieren" ausgibt, konstruiert man natürlich a Spirale, die, wenn Sie zu einer immer höheren Anzahl von Punkten gelangen, sich dennoch weigert, genau definierte „Balken“ zu haben, auf denen die Punkte ausgerichtet sind. (Anmerkung 1.)

Der Algorithmus für einen gleichmäßigen Abstand auf einer Platte lautet:

from numpy import pi, cos, sin, sqrt, arange
import matplotlib.pyplot as pp

num_pts = 100
indices = arange(0, num_pts, dtype=float) + 0.5

r = sqrt(indices/num_pts)
theta = pi * (1 + 5**0.5) * indices

pp.scatter(r*cos(theta), r*sin(theta))
pp.show()

und es erzeugt Ergebnisse, die wie folgt aussehen (n = 100 und n = 1000):

Geben Sie hier die Bildbeschreibung ein

Abstand der Punkte radial

Der Schlüssel seltsam ist die Formel r = sqrt(indices / num_pts); Wie bin ich zu diesem gekommen? (Anmerkung 2.)

Nun, ich verwende hier die Quadratwurzel, weil ich möchte, dass diese einen gleichmäßigen Flächenabstand um die Platte haben. Das ist das gleiche wie zu sagen, dass in der Grenze von großem N ich möchte, dass ein kleiner Bereich R ∈ ( r , r + d r ), Θ ∈ ( θ , θ + d θ ) eine Anzahl von Punkten enthält, die proportional zu seiner Fläche sind, das ist r d r d θ . Wenn wir nun so tun, als würden wir hier von einer Zufallsvariablen sprechen, hat dies eine einfache Interpretation, die besagt, dass die gemeinsame Wahrscheinlichkeitsdichte für ( R , Θ ) nur cr istfür eine Konstante c . Eine Normalisierung auf der Einheitsscheibe würde dann c = 1 / π erzwingen .

Lassen Sie mich nun einen Trick vorstellen. Es stammt aus der Wahrscheinlichkeitstheorie, in der es als Abtastung der inversen CDF bekannt ist : Angenommen, Sie wollten eine Zufallsvariable mit einer Wahrscheinlichkeitsdichte f ( z ) erzeugen und haben eine Zufallsvariable U ~ Uniform (0, 1), genau wie aus in den meisten Programmiersprachen. Wie machst Du das?random()

  1. Verwandeln Sie Ihre Dichte zunächst in eine kumulative Verteilungsfunktion oder CDF, die wir F ( z ) nennen. Denken Sie daran, dass eine CDF mit der Ableitung f ( z ) monoton von 0 auf 1 ansteigt .
  2. Berechnen Sie dann die Umkehrfunktion der CDF F -1 ( z ).
  3. Sie werden feststellen, dass Z = F -1 ( U ) entsprechend der Zieldichte verteilt ist. (Notiz 3).

Jetzt räumt der Spiraltrick mit dem goldenen Schnitt die Punkte in einem schön gleichmäßigen Muster für θ auf, also integrieren wir das heraus; für die Einheitsscheibe bleibt F ( r ) = r 2 übrig . Die Umkehrfunktion ist also F -1 ( u ) = u 1/2 , und daher würden wir zufällige Punkte auf der Scheibe in Polarkoordinaten mit erzeugen r = sqrt(random()); theta = 2 * pi * random().

Anstatt diese Umkehrfunktion zufällig abzutasten, werden sie nun einheitlich abgetastet, und das Schöne an der gleichmäßigen Abtastung ist, dass sich unsere Ergebnisse darüber, wie Punkte in der Grenze von großem N verteilt sind, so verhalten, als hätten wir sie zufällig abgetastet. Diese Kombination ist der Trick. Anstelle von verwenden random()wir (arange(0, num_pts, dtype=float) + 0.5)/num_pts, so dass zum Beispiel, wenn wir 10 Punkte abtasten wollen, sie sind r = 0.05, 0.15, 0.25, ... 0.95. Wir probieren r gleichmäßig ab , um einen gleichmäßigen Abstand zu erhalten, und wir verwenden das Sonnenblumeninkrement, um schreckliche „Balken“ von Punkten in der Ausgabe zu vermeiden.

Jetzt mache ich die Sonnenblume auf einer Kugel

Die Änderungen, die wir vornehmen müssen, um die Kugel mit Punkten zu versehen, umfassen lediglich das Vertauschen der Polarkoordinaten gegen Kugelkoordinaten. Die Radialkoordinate geht natürlich nicht ein, weil wir uns auf einer Einheitskugel befinden. Um die Dinge hier ein wenig konsistenter zu halten, verwende ich, obwohl ich als Physiker ausgebildet wurde, die Koordinaten von Mathematikern, wobei 0 ≤ φ ≤ π der vom Pol herabfallende Breitengrad und 0 ≤ θ ≤ 2π der Längengrad ist. So ist der Unterschied von oben ist , dass wir im Prinzip die Variable ersetzen r mit φ .

Unser Flächenelement, das r d r d θ war , wird nun zur nicht viel komplizierteren sin ( φ ) d φ d θ . Unsere Gelenkdichte für einen gleichmäßigen Abstand ist also sin ( φ ) / 4π. Die Integration aus θ finden wir f ( φ ) = sin ( φ ) / 2, so dass F ( φ -) = (cos (1 φ / 2)). Wenn wir dies umkehren, können wir sehen, dass eine einheitliche Zufallsvariable wie acos (1 - 2 u ) aussehen würde , aber wir probieren einheitlich statt zufällig, also verwenden wir stattdessen φ k = acos (1 - 2 ( k)+ 0,5) / N ). Und der Rest des Algorithmus projiziert dies nur auf die x-, y- und z-Koordinaten:

from numpy import pi, cos, sin, arccos, arange
import mpl_toolkits.mplot3d
import matplotlib.pyplot as pp

num_pts = 1000
indices = arange(0, num_pts, dtype=float) + 0.5

phi = arccos(1 - 2*indices/num_pts)
theta = pi * (1 + 5**0.5) * indices

x, y, z = cos(theta) * sin(phi), sin(theta) * sin(phi), cos(phi);

pp.figure().add_subplot(111, projection='3d').scatter(x, y, z);
pp.show()

Wiederum für n = 100 und n = 1000 sehen die Ergebnisse so aus: Geben Sie hier die Bildbeschreibung ein Geben Sie hier die Bildbeschreibung ein

Weitere Nachforschungen

Ich wollte Martin Roberts Blog einen Gruß aussprechen. Beachten Sie, dass ich oben einen Versatz meiner Indizes erstellt habe, indem ich jedem Index 0,5 hinzugefügt habe. Dies war nur optisch ansprechend für mich, aber es stellt sich heraus, dass die Wahl des Versatzes sehr wichtig ist und über das Intervall nicht konstant ist und bei richtiger Wahl eine um bis zu 8% bessere Genauigkeit beim Verpacken bedeuten kann. Es sollte auch eine Möglichkeit geben, seine R 2 -Sequenz dazu zu bringen, eine Kugel abzudecken, und es wäre interessant zu sehen, ob dies auch eine schöne gleichmäßige Abdeckung hervorbrachte, vielleicht so wie sie ist, aber vielleicht nur von der Hälfte genommen werden muss Das Einheitsquadrat schnitt diagonal oder so und streckte sich, um einen Kreis zu erhalten.

Anmerkungen

  1. Diese „Balken“ werden durch rationale Annäherungen an eine Zahl gebildet, und die besten rationalen Annäherungen an eine Zahl ergeben sich aus ihrem fortgesetzten Bruchausdruck, z + 1/(n_1 + 1/(n_2 + 1/(n_3 + ...)))wobei zes sich um eine Ganzzahl handelt und n_1, n_2, n_3, ...es sich entweder um eine endliche oder eine unendliche Folge positiver Ganzzahlen handelt:

    def continued_fraction(r):
        while r != 0:
            n = floor(r)
            yield n
            r = 1/(r - n)

    Da der Bruchteil 1/(...)immer zwischen Null und Eins liegt, ermöglicht eine große Ganzzahl im fortgesetzten Bruch eine besonders gute rationale Annäherung: "Eins geteilt durch etwas zwischen 100 und 101" ist besser als "Eins geteilt durch etwas zwischen 1 und 2." Die irrationalste Zahl ist daher diejenige, die 1 + 1/(1 + 1/(1 + ...))keine besonders guten rationalen Annäherungen hat und hat; man kann lösen φ = 1 + 1 / φ indem man mit φ multipliziert , um die Formel für den Goldenen Schnitt zu erhalten.

  2. Für Leute, die mit NumPy nicht so vertraut sind - alle Funktionen sind "vektorisiert", so dass dies sqrt(array)das gleiche ist, was andere Sprachen schreiben könnten map(sqrt, array). Dies ist also eine komponentenweise sqrtAnwendung. Gleiches gilt auch für die Division durch einen Skalar oder die Addition mit Skalaren - diese gelten für alle Komponenten parallel.

  3. Der Beweis ist einfach, sobald Sie wissen, dass dies das Ergebnis ist. Wenn Sie fragen, wie hoch die Wahrscheinlichkeit ist, dass z < Z < z + d z ist , entspricht dies der Wahrscheinlichkeit, dass z < F -1 ( U ) < z + d z ist , und wenden Sie F auf alle drei Ausdrücke an Eine monoton ansteigende Funktion, also F ( z ) < U < F ( z + d z ), erweitert die rechte Seite nach außen, um F ( z ) + f zu finden( z ) d z , und da Uist einheitlich diese Wahrscheinlichkeit ist nur f ( z ) d z wie versprochen.

CR Drost
quelle
4
Ich bin mir nicht sicher, warum dies so weit unten liegt. Dies ist bei weitem die beste schnelle Methode, um dies zu tun.
Am
2
@snb danke für die freundlichen Worte! es ist zum Teil so weit unten, weil es viel, viel jünger ist als alle anderen Antworten hier. Ich bin überrascht, dass es sogar so gut läuft wie bisher.
CR Drost
Eine Frage, die mir noch bleibt, ist: Wie viele Punkte n muss ich für einen bestimmten maximalen Abstand zwischen zwei beliebigen Punkten verteilen?
Felix D.
1
@ FelixD. Das klingt nach einer Frage, die sehr schnell sehr kompliziert werden kann, insbesondere wenn Sie beispielsweise Großkreisentfernungen anstelle von euklidischen Entfernungen verwenden. Aber vielleicht kann ich eine einfache Frage beantworten: Wenn man die Punkte auf der Kugel in ihr Voronoi-Diagramm umwandelt, kann man jede Voronoi-Zelle mit einer Fläche von ungefähr 4π / N beschreiben und dies in einen charakteristischen Abstand umwandeln, indem man vorgibt, es sei eher ein Kreis als eine Raute ist πr² = 4π / N. Dann ist r = 2 / √ (N).
CR Drost
2
Die Verwendung des Abtasttheorems mit tatsächlich einheitlicher statt zufällig einheitlicher Eingabe ist eines der Dinge, die mich dazu bringen zu sagen: "Nun, warum die # $% & habe ich nicht daran gedacht?" . Nett.
dmckee --- Ex-Moderator Kätzchen
86

Dies wird als Packungspunkte auf einer Kugel bezeichnet, und es gibt keine (bekannte) allgemeine, perfekte Lösung. Es gibt jedoch viele unvollständige Lösungen. Die drei beliebtesten scheinen zu sein:

  1. Erstellen Sie eine Simulation . Behandeln Sie jeden Punkt als ein auf eine Kugel beschränktes Elektron und führen Sie dann eine Simulation für eine bestimmte Anzahl von Schritten durch. Die Abstoßung der Elektronen führt das System natürlich zu einem stabileren Zustand, in dem die Punkte so weit wie möglich voneinander entfernt sind.
  2. Hypercube-Ablehnung . Diese ausgefallene Methode ist eigentlich ganz einfach: Sie wählen einheitlich (viel mehr alsn Punkte ) innerhalb des die Kugel umgebenden Würfels aus und lehnen dann die Punkte außerhalb der Kugel ab. Behandle die verbleibenden Punkte als Vektoren und normalisiere sie. Dies sind Ihre "Samples" - wählen Sie nsie mit einer Methode aus (zufällig, gierig usw.).
  3. Spiralnäherungen . Sie zeichnen eine Spirale um eine Kugel und verteilen die Punkte gleichmäßig um die Spirale. Aufgrund der Mathematik sind diese komplizierter zu verstehen als die Simulation, aber viel schneller (und wahrscheinlich mit weniger Code). Das beliebteste scheint von Saff et al .

Eine viel mehr Informationen zu diesem Problem finden sich hier

BlueRaja - Danny Pflughoeft
quelle
Ich werde mich mit der Spiraltaktik befassen, die Andrew Cooke unten veröffentlicht hat. Könnten Sie bitte den Unterschied zwischen dem, was ich will, und der "gleichmäßigen Zufallsverteilung" klären? Ist das nur eine 100% zufällige Platzierung von Punkten auf einer Kugel, so dass sie gleichmäßig platziert werden? Danke für die Hilfe. :)
Befall
4
@Befall: "gleichmäßige Zufallsverteilung" bezieht sich auf die gleichmäßige Wahrscheinlichkeitsverteilung - dies bedeutet, dass bei der Auswahl eines zufälligen Punkts auf der Kugel jeder Punkt die gleiche Wahrscheinlichkeit hat, ausgewählt zu werden. Es hat nichts mit der endgültigen räumlichen Verteilung der Punkte zu tun und hat daher nichts mit Ihrer Frage zu tun.
BlueRaja - Danny Pflughoeft
Ahhh, okay, vielen Dank. Die Suche nach meiner Frage führte zu einer Menge Antworten für beide, und ich konnte nicht wirklich verstehen, was für mich sinnlos war.
Befall
Um klar zu sein, hat jeder Punkt eine Wahrscheinlichkeit von Null, ausgewählt zu werden. Das Verhältnis der Wahrscheinlichkeiten, dass der Punkt zu zwei beliebigen Bereichen auf der Oberfläche der Kugel gehört, ist gleich dem Verhältnis der Oberflächen.
AturSams
2
Der letzte Link ist jetzt tot
Felix D.
10

Was Sie suchen, wird als sphärische Abdeckung bezeichnet . Das Problem der sphärischen Abdeckung ist sehr schwierig und Lösungen sind bis auf eine geringe Anzahl von Punkten unbekannt. Eine Sache, die sicher bekannt ist, ist, dass bei n Punkten auf einer Kugel immer zwei Punkte der Entfernung d = (4-csc^2(\pi n/6(n-2)))^(1/2)oder näher existieren.

Wenn Sie eine probabilistische Methode zum Generieren von Punkten wünschen, die gleichmäßig auf einer Kugel verteilt sind, ist dies einfach: Generieren Sie Punkte im Raum gleichmäßig durch Gaußsche Verteilung (sie ist in Java integriert, nicht schwer, den Code für andere Sprachen zu finden). Im dreidimensionalen Raum braucht man also so etwas

Random r = new Random();
double[] p = { r.nextGaussian(), r.nextGaussian(), r.nextGaussian() };

Projizieren Sie dann den Punkt auf die Kugel, indem Sie den Abstand zum Ursprung normalisieren

double norm = Math.sqrt( (p[0])^2 + (p[1])^2 + (p[2])^2 ); 
double[] sphereRandomPoint = { p[0]/norm, p[1]/norm, p[2]/norm };

Die Gaußsche Verteilung in n Dimensionen ist sphärisch symmetrisch, so dass die Projektion auf die Kugel gleichmäßig ist.

Natürlich gibt es keine Garantie dafür, dass der Abstand zwischen zwei Punkten in einer Sammlung einheitlich generierter Punkte unten begrenzt wird. Sie können also die Ablehnung verwenden, um solche Bedingungen durchzusetzen, die Sie möglicherweise haben: Wahrscheinlich ist es am besten, die gesamte Sammlung zu generieren und dann lehnen Sie gegebenenfalls die gesamte Sammlung ab. (Oder verwenden Sie "vorzeitige Ablehnung", um die gesamte Sammlung abzulehnen, die Sie bisher generiert haben. Behalten Sie nur einige Punkte nicht bei und lassen Sie andere fallen.) Sie können die doben angegebene Formel abzüglich eines gewissen Durchhangs verwenden, um den Mindestabstand zwischen zu bestimmen Punkte, unter denen Sie eine Reihe von Punkten ablehnen. Sie müssen n Entfernungen berechnen und wählen, und die Wahrscheinlichkeit der Ablehnung hängt vom Durchhang ab. Es ist schwer zu sagen, wie. Führen Sie daher eine Simulation durch, um ein Gefühl für die relevanten Statistiken zu bekommen.

Edward Doolittle
quelle
Upvoted für die minimalen maximalen Abstandsausdrücke. Nützlich, um die Anzahl der Punkte, die Sie verwenden möchten, zu begrenzen. Ein Verweis auf eine maßgebliche Quelle dafür wäre allerdings schön.
dmckee --- Ex-Moderator Kätzchen
6

Diese Antwort basiert auf der gleichen "Theorie", die in dieser Antwort gut umrissen ist

Ich füge diese Antwort wie folgt hinzu:
- Keine der anderen Optionen entspricht der Anforderung der „Einheitlichkeit“, „genau richtig“ zu sein (oder nicht offensichtlich - eindeutig). (Um den Planeten wie ein verteilungsähnliches Verhalten zu erhalten, das in der ursprünglichen Frage besonders erwünscht ist, lehnen Sie es einfach aus der endlichen Liste der k einheitlich erstellten Punkte nach dem Zufallsprinzip ab (zufällig anhand der Indexanzahl in den k Elementen zurück).) -
Das nächste Ein anderes Gerät hat Sie gezwungen, das 'N' anhand der 'Winkelachse' zu bestimmen, gegenüber nur 'einem Wert von N' über beide Winkelachsenwerte (was bei niedrigen Zählwerten von N sehr schwierig ist zu wissen, was wichtig sein kann oder nicht). zB willst du '5' Punkte - viel Spaß))
- Darüber hinaus ist es sehr schwierig zu verstehen, wie zwischen den anderen Optionen ohne Bildmaterial unterschieden werden kann. So sieht diese Option aus (siehe unten) und die dazugehörige sofort einsatzbereite Implementierung.

mit N bei 20:

Geben Sie hier die Bildbeschreibung ein
und dann N bei 80: Geben Sie hier die Bildbeschreibung ein


Hier ist der sofort einsatzbereite Python3-Code, bei dem die Emulation dieselbe Quelle ist: " http://web.archive.org/web/20120421191837/http://www.cgafaq.info/wiki/Evenly_distributed_points_on_sphere ", die von anderen gefunden wurde . (Die von mir beigefügte Darstellung, die ausgelöst wird, wenn sie als "Haupt" ausgeführt wird, stammt von: http://www.scipy.org/Cookbook/Matplotlib/mplot3D )

from math import cos, sin, pi, sqrt

def GetPointsEquiAngularlyDistancedOnSphere(numberOfPoints=45):
    """ each point you get will be of form 'x, y, z'; in cartesian coordinates
        eg. the 'l2 distance' from the origion [0., 0., 0.] for each point will be 1.0 
        ------------
        converted from:  http://web.archive.org/web/20120421191837/http://www.cgafaq.info/wiki/Evenly_distributed_points_on_sphere ) 
    """
    dlong = pi*(3.0-sqrt(5.0))  # ~2.39996323 
    dz   =  2.0/numberOfPoints
    long =  0.0
    z    =  1.0 - dz/2.0
    ptsOnSphere =[]
    for k in range( 0, numberOfPoints): 
        r    = sqrt(1.0-z*z)
        ptNew = (cos(long)*r, sin(long)*r, z)
        ptsOnSphere.append( ptNew )
        z    = z - dz
        long = long + dlong
    return ptsOnSphere

if __name__ == '__main__':                
    ptsOnSphere = GetPointsEquiAngularlyDistancedOnSphere( 80)    

    #toggle True/False to print them
    if( True ):    
        for pt in ptsOnSphere:  print( pt)

    #toggle True/False to plot them
    if(True):
        from numpy import *
        import pylab as p
        import mpl_toolkits.mplot3d.axes3d as p3

        fig=p.figure()
        ax = p3.Axes3D(fig)

        x_s=[];y_s=[]; z_s=[]

        for pt in ptsOnSphere:
            x_s.append( pt[0]); y_s.append( pt[1]); z_s.append( pt[2])

        ax.scatter3D( array( x_s), array( y_s), array( z_s) )                
        ax.set_xlabel('X'); ax.set_ylabel('Y'); ax.set_zlabel('Z')
        p.show()
        #end

bei niedrigen Zählwerten getestet (N in 2, 5, 7, 13 usw.) und scheint "gut" zu funktionieren.

Matt S.
quelle
5

Versuchen:

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); 
};

Die obige Funktion sollte in einer Schleife mit N Schleifengesamt- und k Schleifenstromiteration ausgeführt werden.

Es basiert auf einem Sonnenblumenkernmuster, außer dass die Sonnenblumenkerne zu einer halben Kuppel und wieder zu einer Kugel gebogen sind.

Hier ist ein Bild, außer dass ich die Kamera in der Mitte der Kugel platziert habe, sodass sie 2d statt 3d aussieht, da die Kamera von allen Punkten den gleichen Abstand hat. http://3.bp.blogspot.com/-9lbPHLccQHA/USXf88_bvVI/AAAAAAAAADY/j7qhQsSZsA8/s640/sphere.jpg

verständlich
quelle
2

Healpix löst ein eng verwandtes Problem (Pixelierung der Kugel mit Pixeln gleicher Fläche):

http://healpix.sourceforge.net/

Es ist wahrscheinlich übertrieben, aber vielleicht werden Sie nach dem Betrachten feststellen, dass einige der anderen schönen Eigenschaften für Sie interessant sind. Es ist weit mehr als nur eine Funktion, die eine Punktwolke ausgibt.

Ich bin hier gelandet und habe versucht, es wieder zu finden. Der Name "Healpix" ruft nicht gerade Sphären hervor ...

Andrew Wagner
quelle
1

Mit einer kleinen Anzahl von Punkten können Sie eine Simulation ausführen:

from random import random,randint
r = 10
n = 20
best_closest_d = 0
best_points = []
points = [(r,0,0) for i in range(n)]
for simulation in range(10000):
    x = random()*r
    y = random()*r
    z = r-(x**2+y**2)**0.5
    if randint(0,1):
        x = -x
    if randint(0,1):
        y = -y
    if randint(0,1):
        z = -z
    closest_dist = (2*r)**2
    closest_index = None
    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            p1,p2 = points[i],points[j]
            x1,y1,z1 = p1
            x2,y2,z2 = p2
            d = (x1-x2)**2+(y1-y2)**2+(z1-z2)**2
            if d < closest_dist:
                closest_dist = d
                closest_index = i
    if simulation % 100 == 0:
        print simulation,closest_dist
    if closest_dist > best_closest_d:
        best_closest_d = closest_dist
        best_points = points[:]
    points[closest_index]=(x,y,z)


print best_points
>>> best_points
[(9.921692138442777, -9.930808529773849, 4.037839326088124),
 (5.141893371460546, 1.7274947332807744, -4.575674650522637),
 (-4.917695758662436, -1.090127967097737, -4.9629263893193745),
 (3.6164803265540666, 7.004158551438312, -2.1172868271109184),
 (-9.550655088997003, -9.580386054762917, 3.5277052594769422),
 (-0.062238110294250415, 6.803105171979587, 3.1966101417463655),
 (-9.600996012203195, 9.488067284474834, -3.498242301168819),
 (-8.601522086624803, 4.519484132245867, -0.2834204048792728),
 (-1.1198210500791472, -2.2916581379035694, 7.44937337008726),
 (7.981831370440529, 8.539378431788634, 1.6889099589074377),
 (0.513546008372332, -2.974333486904779, -6.981657873262494),
 (-4.13615438946178, -6.707488383678717, 2.1197605651446807),
 (2.2859494919024326, -8.14336582650039, 1.5418694699275672),
 (-7.241410895247996, 9.907335206038226, 2.271647103735541),
 (-9.433349952523232, -7.999106443463781, -2.3682575660694347),
 (3.704772125650199, 1.0526567864085812, 6.148581714099761),
 (-3.5710511242327048, 5.512552040316693, -3.4318468250897647),
 (-7.483466337225052, -1.506434920354559, 2.36641535124918),
 (7.73363824231576, -8.460241422163824, -1.4623228616326003),
 (10, 0, 0)]
Robert King
quelle
meine Antwort zu verbessern , sollten Sie closest_index ändern = i closest_index = randchoice (i, j)
Robert King
1

Nehmen Sie die zwei größten Faktoren von Ihnen N, wenn N==20dann die zwei größten Faktoren sind {5,4}oder allgemeiner {a,b}. Berechnung

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

Setzen Sie Ihren ersten Punkt auf {90-dlat/2,(dlong/2)-180}, Ihren zweiten auf {90-dlat/2,(3*dlong/2)-180}, Ihren dritten auf {90-dlat/2,(5*dlong/2)-180}, bis Sie einmal um die Welt gestolpert sind. Zu diesem Zeitpunkt müssen Sie ungefähr, {75,150}wann Sie nebenan gehen {90-3*dlat/2,(dlong/2)-180}.

Offensichtlich arbeite ich dies in Grad auf der Oberfläche der kugelförmigen Erde mit den üblichen Konventionen für die Übersetzung von +/- in N / S oder E / W. Und dies ergibt natürlich eine völlig nicht zufällige Verteilung, aber sie ist gleichmäßig und die Punkte sind nicht gebündelt.

Um ein gewisses Maß an Zufälligkeit hinzuzufügen, können Sie 2 normalverteilte Punkte (mit dem Mittelwert 0 und dem Standardabweichungswert von {dlat / 3, dlong / 3}) generieren und diese zu Ihren gleichmäßig verteilten Punkten hinzufügen.

Hochleistungsmarke
quelle
5
das würde viel besser aussehen, wenn du eher in sin (lat) als in lat arbeiten würdest. So wie es ist, werden Sie in der Nähe der Pole eine Menge Bündel bekommen.
Andrew Cooke
1

edit: Dies beantwortet nicht die Frage, die das OP stellen wollte, und lässt sie hier, falls die Leute sie irgendwie nützlich finden.

Wir verwenden die Multiplikationsregel der Wahrscheinlichkeit, kombiniert mit Infinitessimalen. Dies führt zu 2 Codezeilen, um das gewünschte Ergebnis zu erzielen:

longitude: φ = uniform([0,2pi))
azimuth:   θ = -arcsin(1 - 2*uniform([0,1]))

(definiert im folgenden Koordinatensystem :)

Geben Sie hier die Bildbeschreibung ein

Ihre Sprache hat normalerweise ein einheitliches Zufallszahlenprimitiv. In Python können Sie beispielsweise random.random()eine Zahl im Bereich zurückgeben [0,1). Sie können diese Zahl mit k multiplizieren, um eine Zufallszahl im Bereich zu erhalten [0,k). Also in Python uniform([0,2pi))würde bedeuten random.random()*2*math.pi.


Beweis

Jetzt können wir θ nicht einheitlich zuweisen, sonst würden wir an den Polen verklumpen. Wir möchten Wahrscheinlichkeiten proportional zur Oberfläche des Kugelkeils zuweisen (das θ in diesem Diagramm ist tatsächlich φ):

Geben Sie hier die Bildbeschreibung ein

Eine Winkelverschiebung dφ am Äquator führt zu einer Verschiebung von dφ * r. Wie wird diese Verschiebung bei einem beliebigen Azimut θ sein? Nun, der Radius von der z-Achse ist r*sin(θ), so dass die Bogenlänge des „Breite“ sich schneidende, den Keil ist dφ * r*sin(θ). Daher berechnen wir die kumulative Verteilung der zu untersuchenden Fläche, indem wir die Fläche der Scheibe vom Südpol zum Nordpol integrieren.

Geben Sie hier die Bildbeschreibung ein(wo Zeug = dφ*r)

Wir werden nun versuchen, die Umkehrung der CDF zum Abtasten daraus zu machen: http://en.wikipedia.org/wiki/Inverse_transform_sampling

Zuerst normalisieren wir, indem wir unseren Fast-CDF durch seinen Maximalwert dividieren. Dies hat den Nebeneffekt, dass dφ und r aufgehoben werden.

azimuthalCDF: cumProb = (sin(θ)+1)/2 from -pi/2 to pi/2

inverseCDF: θ = -sin^(-1)(1 - 2*cumProb)

So:

let x by a random float in range [0,1]
θ = -arcsin(1-2*x)
Ninjagecko
quelle
Entspricht dies nicht der Option, die er als "100% randomisiert" verworfen hat? Mein Verständnis ist, dass er möchte, dass sie gleichmäßiger verteilt sind als eine gleichmäßige Zufallsverteilung.
Andrew Cooke
@ BlueRaja-DannyPflughoeft: Hmm, fair genug. Ich glaube, ich habe die Frage nicht so sorgfältig gelesen, wie ich es hätte tun sollen. Ich lasse das sowieso hier, falls andere es nützlich finden. Vielen Dank für den Hinweis.
Ninjagecko
1

ODER ... um 20 Punkte zu platzieren, berechnen Sie die Zentren der Ikosaederflächen. Finden Sie für 12 Punkte die Eckpunkte des Ikosaeders. Für 30 Punkte der Mittelpunkt der Kanten des Ikosaeders. Sie können dasselbe mit Tetraedern, Würfeln, Dodekaedern und Oktaedern tun: Ein Satz von Punkten befindet sich auf den Eckpunkten, ein anderer in der Mitte des Gesichts und ein anderer in der Mitte der Kanten. Sie können jedoch nicht gemischt werden.

user19371
quelle
Eine gute Idee, aber sie funktioniert nur für 4, 6, 8, 12, 20, 24 oder 30 Punkte.
Der Kerl mit dem Hut
Wenn Sie betrügen möchten, können Sie die Mitte von Flächen und Scheitelpunkten verwenden. Sie werden nicht gleich beabstandet sein, sondern eine anständige Annäherung. Das ist schön, weil es deterministisch ist.
Schachofnerd
0
# create uniform spiral grid
numOfPoints = varargin[0]
vxyz = zeros((numOfPoints,3),dtype=float)
sq0 = 0.00033333333**2
sq2 = 0.9999998**2
sumsq = 2*sq0 + sq2
vxyz[numOfPoints -1] = array([(sqrt(sq0/sumsq)), 
                              (sqrt(sq0/sumsq)), 
                              (-sqrt(sq2/sumsq))])
vxyz[0] = -vxyz[numOfPoints -1] 
phi2 = sqrt(5)*0.5 + 2.5
rootCnt = sqrt(numOfPoints)
prevLongitude = 0
for index in arange(1, (numOfPoints -1), 1, dtype=float):
  zInc = (2*index)/(numOfPoints) -1
  radius = sqrt(1-zInc**2)

  longitude = phi2/(rootCnt*radius)
  longitude = longitude + prevLongitude
  while (longitude > 2*pi): 
    longitude = longitude - 2*pi

  prevLongitude = longitude
  if (longitude > pi):
    longitude = longitude - 2*pi

  latitude = arccos(zInc) - pi/2
  vxyz[index] = array([ (cos(latitude) * cos(longitude)) ,
                        (cos(latitude) * sin(longitude)), 
                        sin(latitude)])
Schmied
quelle
4
Es wäre hilfreich, wenn Sie einen Text schreiben würden, in dem erklärt wird, was dies tun soll, damit das OP nicht davon ausgehen muss, dass es einfach funktioniert.
Hcarver
0

@ Robert King Es ist eine wirklich schöne Lösung, hat aber einige schlampige Fehler. Ich weiß, dass es mir sehr geholfen hat, also macht mir die Schlamperei nichts aus. :) Hier ist eine aufgeräumte Version ....

from math import pi, asin, sin, degrees
halfpi, twopi = .5 * pi, 2 * pi
sphere_area = lambda R=1.0: 4 * pi * R ** 2

lat_dist = lambda lat, R=1.0: R*(1-sin(lat))

#A = 2*pi*R^2(1-sin(lat))
def sphere_latarea(lat, R=1.0):
    if -halfpi > lat or lat > halfpi:
        raise ValueError("lat must be between -halfpi and halfpi")
    return 2 * pi * R ** 2 * (1-sin(lat))

sphere_lonarea = lambda lon, R=1.0: \
        4 * pi * R ** 2 * lon / twopi

#A = 2*pi*R^2 |sin(lat1)-sin(lat2)| |lon1-lon2|/360
#    = (pi/180)R^2 |sin(lat1)-sin(lat2)| |lon1-lon2|
sphere_rectarea = lambda lat0, lat1, lon0, lon1, R=1.0: \
        (sphere_latarea(lat0, R)-sphere_latarea(lat1, R)) * (lon1-lon0) / twopi


def test_sphere(n_lats=10, n_lons=19, radius=540.0):
    total_area = 0.0
    for i_lons in range(n_lons):
        lon0 = twopi * float(i_lons) / n_lons
        lon1 = twopi * float(i_lons+1) / n_lons
        for i_lats in range(n_lats):
            lat0 = asin(2 * float(i_lats) / n_lats - 1)
            lat1 = asin(2 * float(i_lats+1)/n_lats - 1)
            area = sphere_rectarea(lat0, lat1, lon0, lon1, radius)
            print("{:} {:}: {:9.4f} to  {:9.4f}, {:9.4f} to  {:9.4f} => area {:10.4f}"
                    .format(i_lats, i_lons
                    , degrees(lat0), degrees(lat1)
                    , degrees(lon0), degrees(lon1)
                    , area))
            total_area += area
    print("total_area = {:10.4f} (difference of {:10.4f})"
            .format(total_area, abs(total_area) - sphere_area(radius)))

test_sphere()
Ismael Harun
quelle
-1

Das funktioniert und es ist tödlich einfach. So viele Punkte wie Sie möchten:

    private function moveTweets():void {


        var newScale:Number=Scale(meshes.length,50,500,6,2);
        trace("new scale:"+newScale);


        var l:Number=this.meshes.length;
        var tweetMeshInstance:TweetMesh;
        var destx:Number;
        var desty:Number;
        var destz:Number;
        for (var i:Number=0;i<this.meshes.length;i++){

            tweetMeshInstance=meshes[i];

            var phi:Number = Math.acos( -1 + ( 2 * i ) / l );
            var theta:Number = Math.sqrt( l * Math.PI ) * phi;

            tweetMeshInstance.origX = (sphereRadius+5) * Math.cos( theta ) * Math.sin( phi );
            tweetMeshInstance.origY= (sphereRadius+5) * Math.sin( theta ) * Math.sin( phi );
            tweetMeshInstance.origZ = (sphereRadius+5) * Math.cos( phi );

            destx=sphereRadius * Math.cos( theta ) * Math.sin( phi );
            desty=sphereRadius * Math.sin( theta ) * Math.sin( phi );
            destz=sphereRadius * Math.cos( phi );

            tweetMeshInstance.lookAt(new Vector3D());


            TweenMax.to(tweetMeshInstance, 1, {scaleX:newScale,scaleY:newScale,x:destx,y:desty,z:destz,onUpdate:onLookAtTween, onUpdateParams:[tweetMeshInstance]});

        }

    }
    private function onLookAtTween(theMesh:TweetMesh):void {
        theMesh.lookAt(new Vector3D());
    }
Arthur Flower
quelle