Równomierne rozłożenie n punktów na kuli


121

Potrzebuję algorytmu, który może podać mi pozycje wokół kuli dla N punktów (prawdopodobnie mniej niż 20), który rozłoży je niejasno. Nie ma potrzeby „perfekcji”, ale po prostu jej potrzebuję, aby żadne z nich nie były ze sobą połączone.

  • To pytanie zawierało dobry kod, ale nie mogłem znaleźć sposobu na zrobienie tego munduru, ponieważ wydawało się, że jest to w 100% losowe.
  • Ten post na blogu zalecany miał dwa sposoby pozwalające na wprowadzenie liczby punktów na kuli, ale algorytm Saffa i Kuijlaarsa jest dokładnie w psuedokodzie, który mogłem transkrybować, a przykładowy kod, który znalazłem, zawierał „węzeł [k]”, którego nie mogłem zobacz wyjaśnienie i zrujnowało tę możliwość. Drugim przykładem na blogu była spirala złotego przekroju, która dała mi dziwne, zebrane wyniki, bez jasnego sposobu zdefiniowania stałego promienia.
  • Wydaje się, że ten algorytm z tego pytania mógłby prawdopodobnie zadziałać, ale nie mogę poskładać tego, co jest na tej stronie, w psuedokodzie lub cokolwiek.

Kilka innych wątków pytań, na które się natknąłem, dotyczyło losowej dystrybucji jednolitej, która dodaje poziom złożoności, o który się nie martwię. Przepraszam, że to takie głupie pytanie, ale chciałem pokazać, że naprawdę wyglądałem na twardego i nadal nie jestem w stanie.

Tak więc szukam prostego pseudokodu do równomiernego rozłożenia N punktów wokół kuli jednostkowej, która powraca we współrzędnych sferycznych lub kartezjańskich. Jeszcze lepiej, jeśli może nawet rozprowadzać się z odrobiną randomizacji (pomyśl o planetach wokół gwiazdy, przyzwoicie rozłożonych, ale z miejscem na swobodę).


Co masz na myśli „z odrobiną randomizacji”? Czy w jakimś sensie masz na myśli perturbacje?
ninjagecko

32
OP jest zdezorientowany. To, czego szuka, to umieszczenie n-punktów na kuli, tak aby minimalna odległość między dowolnymi dwoma punktami była jak największa. Dzięki temu punkty będą wyglądać na „równomiernie rozłożone” na całej kuli. Jest to całkowicie niezwiązane z tworzeniem jednolitego losowego rozkładu na kuli, o czym jest wiele z tych linków i o czym mówi wiele z poniższych odpowiedzi.
BlueRaja - Danny Pflughoeft

1
20 to niewiele punktów do umieszczenia na kuli, jeśli nie chcesz, aby wyglądały po prostu przypadkowo.
John Alexiou

2
Oto sposób na zrobienie tego (ma przykłady kodu): pdfs.semanticscholar.org/97a6/… (wygląda na to, że używa obliczeń siły odpychania)
trusktr

1
Oczywiście dla wartości na N w {4, 6, 8, 12, 20} istnieją dokładne rozwiązania, w których odległość od każdego punktu do (każdego z) jego najbliższych sąsiadów jest stała dla wszystkich punktów i wszystkich najbliższych sąsiadów.
dmckee --- ex-moderator kitten

Odpowiedzi:


13

W tym przykładzie kod node[k] jest po prostu k-tym węzłem. Generujesz tablicę N punktów i node[k]jest to k-ta (od 0 do N-1). Jeśli to wszystko, co cię dezorientuje, miejmy nadzieję, że możesz to teraz wykorzystać.

(innymi słowy, kjest to tablica o rozmiarze N, która jest zdefiniowana przed rozpoczęciem fragmentu kodu i która zawiera listę punktów).

Alternatywnie , opierając się na drugiej odpowiedzi tutaj (i używając Pythona):

> 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

Jeśli to narysujesz, zobaczysz, że odstępy w pionie są większe w pobliżu biegunów, dzięki czemu każdy punkt znajduje się mniej więcej na tym samym całkowitym obszarze przestrzeni (w pobliżu biegunów jest mniej miejsca „w poziomie”, więc daje więcej „w pionie” ).

To nie to samo, co wszystkie punkty mające mniej więcej taką samą odległość od swoich sąsiadów (o czym myślę, że mówią o tym twoje linki), ale może wystarczyć do tego, co chcesz i ulepszyć po prostu tworząc jednolitą siatkę długości / długości .


fajnie, dobrze jest zobaczyć rozwiązanie matematyczne. Myślałem o zastosowaniu separacji helisy i długości łuku. Nadal nie jestem pewien, jak uzyskać optymalne rozwiązanie, co jest interesującym problemem.
robert king

czy widziałeś, że zredagowałem swoją odpowiedź, dodając wyjaśnienie węzła [k] na górze? Myślę, że to może być wszystko, czego potrzebujesz ...
Andrew Cooke

Cudownie, dzięki za wyjaśnienie. Spróbuję później, bo obecnie nie mam czasu, ale bardzo dziękuję za pomoc. Dam ci znać, jak to się kończy dla moich celów. ^^
Przed

Stosowanie metody Spiral idealnie pasuje do moich potrzeb, bardzo dziękuję za pomoc i wyjaśnienie. :)
Przeddzień

13
Link wygląda na martwy.
Scheintod

140

Algorytm sfery Fibonacciego świetnie się do tego nadaje. Jest szybki i daje rezultaty, które na pierwszy rzut oka łatwo oszukają ludzkie oko. Możesz zobaczyć przykład z przetwarzaniem, który pokaże wynik w czasie po dodaniu punktów. Oto kolejny świetny interaktywny przykład autorstwa @gman. A oto prosta implementacja w Pythonie.

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 próbek daje to:

wprowadź opis obrazu tutaj


zmienna n jest wywoływana podczas definiowania phi: phi = ((i + rnd)% n) * przyrost. Czy n = próbki?
Andrew Staroscik

@AndrewStaroscik yes! Kiedy po raz pierwszy pisałem kod, użyłem "n" jako zmiennej i później zmieniłem nazwę, ale nie wykonałem należytej staranności. Dzięki, że to złapałeś!
Fnord


4
@Xarbrough kod daje punkty wokół sfery jednostkowej, więc po prostu pomnóż każdy punkt przez dowolny skalar, który chcesz dla promienia.
Fnord

2
@Fnord: Czy możemy to zrobić dla wyższych wymiarów?
pikachuchameleon

108

Metoda złotej spirali

Powiedziałeś, że nie możesz uruchomić metody złotej spirali i szkoda, bo jest naprawdę, naprawdę dobra. Chciałbym dać ci pełne zrozumienie tego, żebyś mógł zrozumieć, jak nie dopuścić do tego, by się „zgniatało”.

Oto szybki, nielosowy sposób tworzenia sieci, która jest w przybliżeniu poprawna; jak omówiono powyżej, żadna krata nie będzie idealna, ale może to wystarczyć. Porównuje się go do innych metod, np. Na BendWavy.org, ale ma po prostu ładny i ładny wygląd oraz gwarancję równych odstępów w limicie.

Podkład: spirale słonecznika na dysku jednostkowym

Aby zrozumieć ten algorytm, najpierw zapraszam do przyjrzenia się algorytmowi spirali słonecznika 2D. Jest to oparte na fakcie, że najbardziej irracjonalną liczbą jest złoty podział (1 + sqrt(5))/2i jeśli ktoś emituje punkty, stosując podejście „stań w środku, obróć złoty stosunek całych obrotów, a następnie emituj kolejny punkt w tym kierunku”, w naturalny sposób konstruuje się spirala, która w miarę jak dochodzi do coraz większej liczby punktów, niemniej jednak odmawia posiadania dobrze zdefiniowanych „słupków”, na których punkty się pokrywają. (Notatka 1.)

Algorytm równych odstępów na dysku to:

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()

i daje wyniki, które wyglądają następująco (n = 100 in = 1000):

wprowadź opis obrazu tutaj

Rozmieszczenie punktów promieniowo

Kluczową dziwną rzeczą jest formuła r = sqrt(indices / num_pts); jak doszedłem do tego? (Uwaga 2.)

Cóż, używam tutaj pierwiastka kwadratowego, ponieważ chcę, aby miały równe odstępy wokół dysku. To jest to samo, co powiedzieć, że w granicy dużego N chcę, aby mały obszar R ∈ ( r , r + d r ), Θ ∈ ( θ , θ + d θ ) zawierał liczbę punktów proporcjonalną do jego powierzchni, czyli r d r d θ . Teraz, jeśli udajemy, że mówimy tutaj o zmiennej losowej, ma to prostą interpretację, mówiąc, że łączna gęstość prawdopodobieństwa dla ( R , Θ ) jest po prostu crdla jakiejś stałej c . Normalizacja na dysku jednostkowym wymusiłaby wówczas c = 1 / π.

Pozwólcie, że przedstawię sztuczkę. Pochodzi z teorii prawdopodobieństwa, gdzie jest znane jako próbkowanie odwrotnego CDF : załóżmy, że chcesz wygenerować zmienną losową o gęstości prawdopodobieństwa f ( z ) i masz zmienną losową U ~ Jednolity (0, 1), tak jak wychodzi z random()w większości języków programowania. Jak Ty to robisz?

  1. Najpierw zamień swoją gęstość w skumulowaną funkcję dystrybucji lub CDF, którą nazwiemy F ( z ). Pamiętaj, że CDF rośnie monotonicznie od 0 do 1 z pochodną f ( z ).
  2. Następnie oblicz funkcję odwrotną funkcji CDF F -1 ( z ).
  3. Przekonasz się, że Z = F -1 ( U ) rozkłada się zgodnie z gęstością docelową. (Uwaga 3).

Teraz spirala złotego podziału rozdziela punkty w ładnie równy wzór dla θ, więc zintegrujmy to; dla dysku jednostkowego pozostaje F ( r ) = r 2 . Czyli funkcja odwrotna to F -1 ( u ) = u 1/2 , a zatem wygenerowalibyśmy losowe punkty na dysku we współrzędnych biegunowych z r = sqrt(random()); theta = 2 * pi * random().

Teraz zamiast losowo próbkować tę funkcję odwrotną, próbkujemyrównomiernie , a fajną rzeczą w próbkowaniu jednorodnym jest to, że nasze wyniki dotyczące rozłożenia punktów na granicy dużego N będą się zachowywać tak, jakbyśmy próbkowali ją losowo. Ta kombinacja jest sztuczką. Zamiast tego random()używamy (arange(0, num_pts, dtype=float) + 0.5)/num_pts, więc powiedzmy, że jeśli chcemy pobrać próbkę 10 punktów, to one są r = 0.05, 0.15, 0.25, ... 0.95. Jednolicie próbujemy r, aby uzyskać równe odstępy, i używamy przyrostu słonecznika, aby uniknąć okropnych „słupków” punktów w wyniku.

Teraz robię słonecznik na kuli

Zmiany, które musimy wprowadzić, aby kropkować kulę punktami, polegają jedynie na zmianie współrzędnych biegunowych na współrzędne sferyczne. Współrzędna promieniowa oczywiście nie wchodzi w to, ponieważ jesteśmy na kuli jednostkowej. Aby zachować trochę spójności w tym miejscu, mimo że byłem wyszkolony jako fizyk, użyję współrzędnych matematyków, gdzie 0 ≤ φ ≤ π to szerokość geograficzna schodząca z bieguna, a 0 ≤ θ ≤ 2π to długość geograficzna. Zatem różnica z powyższego polega na tym, że w zasadzie zastępujemy zmienną r przez φ .

Nasz element obszaru, który był r d r d θ , teraz staje się niewiele bardziej skomplikowanym sin ( φ ) d φ d θ . Więc nasza gęstość spoiny dla równomiernych odstępów wynosi sin ( φ ) / 4π. Całkując θ , otrzymujemy f ( φ ) = sin ( φ ) / 2, więc F ( φ ) = (1 - cos ( φ )) / 2. Odwracając to, możemy zobaczyć, że jednolita zmienna losowa wyglądałaby jak acos (1 - 2 u ), ale próbkujemy jednakowo zamiast losowo, więc zamiast tego używamy φ k = acos (1 - 2 ( k+ 0,5) / N ). Reszta algorytmu po prostu rzutuje to na współrzędne x, y i z:

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()

Ponownie dla n = 100 in = 1000 wyniki wyglądają następująco: wprowadź opis obrazu tutaj wprowadź opis obrazu tutaj

Dalsze badania

Chciałem się pochwalić blogiem Martina Robertsa. Zauważ, że powyżej utworzyłem przesunięcie moich indeksów, dodając 0,5 do każdego indeksu. To było dla mnie po prostu atrakcyjne wizualnie, ale okazuje się, że wybór offsetu ma duże znaczenie i nie jest stały w przedziale i może oznaczać nawet o 8% lepszą dokładność pakowania, jeśli zostanie wybrany poprawnie. Powinien również istnieć sposób, aby jego sekwencja R 2 pokryła kulę i byłoby interesujące zobaczyć, czy to również stworzyło ładne, równe pokrycie, być może takie, jakie jest, ale być może powinno być, powiedzmy, wzięte tylko z połowy Kwadrat jednostkowy przeciął lub tak po przekątnej i rozciągnął się, aby uzyskać okrąg.

Uwagi

  1. Te „słupki” są tworzone przez racjonalne przybliżenia liczby, a najlepsze racjonalne przybliżenia liczby pochodzą z jej ciągłego wyrażenia ułamkowego, z + 1/(n_1 + 1/(n_2 + 1/(n_3 + ...)))gdzie zjest liczbą całkowitą i n_1, n_2, n_3, ...jest skończoną lub nieskończoną sekwencją dodatnich liczb całkowitych:

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

    Ponieważ część ułamkowa 1/(...)zawsze zawiera się w przedziale od zera do jedynki, duża liczba całkowita w ułamku ciągłym pozwala na szczególnie dobre przybliżenie racjonalne: „jedna podzielona przez coś między 100 a 101” jest lepsza niż „podzielona przez coś między 1 a 2”. Dlatego najbardziej irracjonalna liczba jest liczbą, która jest 1 + 1/(1 + 1/(1 + ...))i nie ma szczególnie dobrych racjonalnych przybliżeń; φ = 1 + 1 / φ można rozwiązać mnożąc przez φ, aby otrzymać wzór na złoty współczynnik.

  2. Dla osób, które nie są tak zaznajomione z NumPy - wszystkie funkcje są „wektoryzowane”, więc sqrt(array)jest to to samo, co można napisać w innych językach map(sqrt, array). Więc to jest aplikacja komponent po komponencie sqrt. To samo dotyczy dzielenia przez skalar lub dodawania ze skalarami - te dotyczą wszystkich składników równolegle.

  3. Dowód jest prosty, gdy wiesz, że to jest wynik. Jeśli zapytasz, jakie jest prawdopodobieństwo, że z < Z < z + d z , to jest to to samo, co pytanie, jakie jest prawdopodobieństwo, że z < F -1 ( U ) < z + d z , zastosuj F do wszystkich trzech wyrażeń, zauważając, że jest funkcja monotonicznie rosnąca, stąd F ( z ) < U < F ( z + d z ), rozwiń prawą stronę na zewnątrz, aby znaleźć F ( z ) + f( z ) d z , a ponieważ U jest jednorodne, to prawdopodobieństwo wynosi tylko f ( z ) d z, jak obiecano.


4
Nie jestem pewien, dlaczego jest to tak daleko, jest to zdecydowanie najlepsza szybka metoda na zrobienie tego.
dniu

2
@snb dziękuję za miłe słowa! jest tak daleko w dół, po części dlatego, że jest dużo, dużo młodszy niż wszystkie pozostałe odpowiedzi tutaj. Dziwię się, że nawet radzi sobie tak dobrze, jak dawniej.
CR Drost,

Pozostaje mi jedno pytanie: ile punktów n muszę rozdzielić na określoną odległość maksymalną między dowolnymi dwoma punktami?
Felix D.

1
@FelixD. To brzmi jak pytanie, które może bardzo szybko się skomplikować, zwłaszcza jeśli zaczniesz używać, powiedzmy, odległości po ortodromie zamiast odległości euklidesowych. Ale może mogę odpowiedzieć na proste pytanie, jeśli konwertujemy punkty na kuli do ich diagramu Woronoja, można opisać każdą komórkę Woronoja jako mającą obszar w przybliżeniu 4π / N i można to przeliczyć na charakterystyczną odległość, udając raczej okrąg niż romb, πr² = 4π / N. Wtedy r = 2 / √ (N).
CR Drost

2
Użycie twierdzenia o próbkowaniu z faktycznie jednolitymi danymi zamiast losowo jednolitych danych wejściowych jest jedną z tych rzeczy, które sprawiają, że mówię: „Cóż, dlaczego # $% i nie pomyślałem o tym?” . Miły.
dmckee --- ex-moderator kitten

86

Nazywa się to punktami upakowania kuli i nie ma (znanego) ogólnego, idealnego rozwiązania. Istnieje jednak wiele niedoskonałych rozwiązań. Wydaje się, że trzy najpopularniejsze to:

  1. Utwórz symulację . Potraktuj każdy punkt jako elektron związany z kulą, a następnie przeprowadź symulację dla określonej liczby kroków. Odpychanie elektronów w naturalny sposób doprowadzi system do bardziej stabilnego stanu, w którym punkty znajdują się tak daleko od siebie, jak to tylko możliwe.
  2. Odrzucenie Hypercube . Ta fantazyjnie brzmiąca metoda jest w rzeczywistości bardzo prosta: równomiernie wybierasz punkty (znacznie więcej niż nich) wewnątrz sześcianu otaczającego kulę, a następnie odrzucasz punkty poza kulą. Traktuj pozostałe punkty jako wektory i znormalizuj je. To są twoje "próbki" - wybierz nje za pomocą jakiejś metody (losowo, chciwie itp.).
  3. Przybliżenia spiralne . Śledzisz spiralę wokół kuli i równomiernie rozprowadzasz punkty wokół spirali. Ze względu na zastosowaną matematykę są one trudniejsze do zrozumienia niż symulacja, ale znacznie szybsze (i prawdopodobnie obejmują mniej kodu). Najpopularniejszy wydaje się być autorstwa Saffa i in .

Dużo więcej informacji na temat tego problemu można znaleźć tutaj


Przyjrzę się taktyce spiralnej, którą Andrew Cooke zamieścił poniżej, jednak czy mógłbyś wyjaśnić różnicę między tym, czego chcę, a tym, czym jest „jednolita losowa dystrybucja”? Czy to tylko w 100% losowe rozmieszczenie punktów na kuli, tak aby były równomiernie rozmieszczone? Dzięki za pomoc. :)
Przed

4
@Befall: „jednolity rozkład losowy” odnosi się do równomiernego rozkładu prawdopodobieństwa - oznacza to, że wybierając losowy punkt na kuli, każdy punkt ma jednakowe prawdopodobieństwo wyboru. Nie ma to nic wspólnego z ostatecznym przestrzennym rozmieszczeniem punktów, a zatem nie ma nic wspólnego z twoim pytaniem.
BlueRaja - Danny Pflughoeft

Ahhh, ok, bardzo dziękuję. Poszukiwanie mojego pytania doprowadziło do mnóstwa odpowiedzi na oba, ale nie mogłem pojąć, co było dla mnie bezcelowe.
Przed

Żeby było jasne, każdy punkt ma zerowe prawdopodobieństwo, że zostanie wybrany. Stosunek prawdopodobieństw, że punkt będzie należał do dowolnych dwóch obszarów na powierzchni kuli, jest równy stosunkowi powierzchni.
AturSams

2
Ostatni link jest teraz martwy
Felix D.

10

To, czego szukasz, nazywa się kulistym pokryciem . Problem sferycznego pokrycia jest bardzo trudny, a rozwiązania są nieznane, z wyjątkiem niewielkiej liczby punktów. Wiadomo na pewno, że mając n punktów na kuli, zawsze istnieją dwa punkty odległe d = (4-csc^2(\pi n/6(n-2)))^(1/2)lub bliższe.

Jeśli potrzebujesz probabilistycznej metody generowania punktów równomiernie rozmieszczonych na sferze, jest to łatwe: generuj punkty w przestrzeni równomiernie według rozkładu Gaussa (jest wbudowany w Javę, nietrudno znaleźć kod dla innych języków). Więc w trójwymiarowej przestrzeni potrzebujesz czegoś takiego

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

Następnie rzutuj punkt na kulę, normalizując jego odległość od początku

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

Rozkład Gaussa w n wymiarach jest sferycznie symetryczny, więc rzut na kulę jest jednorodny.

Oczywiście nie ma gwarancji, że odległość między dowolnymi dwoma punktami w zbiorze równomiernie wygenerowanych punktów będzie ograniczona poniżej, więc możesz użyć odrzucenia, aby wymusić wszelkie takie warunki, które możesz mieć: prawdopodobnie najlepiej jest wygenerować całą kolekcję, a następnie w razie potrzeby odrzucić całą kolekcję. (Lub użyj opcji „wczesne odrzucenie”, aby odrzucić całą kolekcję, którą wygenerowałeś do tej pory; po prostu nie zatrzymuj niektórych punktów i pomiń inne). Możesz użyć wzoru dpodanego powyżej, pomniejszonego o trochę luzu, aby określić minimalną odległość między punktów, poniżej których odrzucisz zestaw punktów. Będziesz musiał obliczyć n wybrać 2 odległości, a prawdopodobieństwo odrzucenia będzie zależeć od luzu; trudno powiedzieć, jak to zrobić, więc przeprowadź symulację, aby poznać odpowiednie statystyki.


Głos za wyrażeniem minimalnej maksymalnej odległości. Przydatne do ograniczania liczby punktów, które chcesz wykorzystać. Przydałoby się jednak odniesienie do wiarygodnego źródła.
dmckee --- ex-moderator kitten

6

Ta odpowiedź jest oparta na tej samej „teorii”, która jest dobrze zarysowana w tej odpowiedzi

Dodaję tę odpowiedź jako:
- Żadna z pozostałych opcji nie pasuje do potrzeby „jednolitości” „trafienia na miejscu” (lub nie jest to oczywiście oczywiste). (Zwracając uwagę na zachowanie wyglądające jak dystrybucja planety, szczególnie pożądane w pierwotnym pytaniu, po prostu odrzucasz losowo ze skończonej listy k równomiernie utworzonych punktów (losowo z liczbą indeksów w k pozycji z powrotem).)
- Najbliższy inny implik zmusił cię do określenia „N” na podstawie „osi kątowej”, zamiast tylko „jednej wartości N” w obu wartościach osi kątowej (co przy małej liczbie N jest bardzo trudne, aby wiedzieć, co może, a co nie może mieć znaczenia ( np. chcesz 5 punktów - baw się dobrze))
- Ponadto bardzo trudno jest `` zrozumieć '', jak rozróżnić inne opcje bez żadnych zdjęć, więc oto, jak wygląda ta opcja (poniżej), i gotowa do uruchomienia implementacja, która z nią idzie.

gdzie N w 20:

wprowadź opis obrazu tutaj
a następnie N przy 80: wprowadź opis obrazu tutaj


oto gotowy do uruchomienia kod Python3, gdzie emulacja pochodzi z tego samego źródła: „ http://web.archive.org/web/20120421191837/http://www.cgafaq.info/wiki/Evenly_distributed_points_on_sphere ” znalezione przez innych . (Zapisane przeze mnie wykresy, uruchamiane po uruchomieniu jako „main”, pochodzą z: 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

testowane przy niskich liczbach (N w 2, 5, 7, 13 itd.) i wydaje się działać „dobrze”


5

Próbować:

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

Powyższa funkcja powinna działać w pętli z sumą N pętli i iteracją prądu pętli k.

Opiera się na wzorze nasion słonecznika, z wyjątkiem tego, że nasiona słonecznika są zakrzywione dookoła w pół kopuły i ponownie w kulę.

Oto zdjęcie, ale umieściłem kamerę do połowy wewnątrz kuli, więc wygląda na 2d zamiast 3d, ponieważ kamera jest w tej samej odległości od wszystkich punktów. http://3.bp.blogspot.com/-9lbPHLccQHA/USXf88_bvVI/AAAAAAAAADY/j7qhQsSZsA8/s640/sphere.jpg


2

Healpix rozwiązuje blisko powiązany problem (pikselizacja kuli z pikselami o równej powierzchni):

http://healpix.sourceforge.net/

Prawdopodobnie jest to przesada, ale może po obejrzeniu go zdasz sobie sprawę, że niektóre z jego innych fajnych właściwości są dla Ciebie interesujące. To znacznie więcej niż funkcja generująca chmurę punktów.

Wylądowałem tutaj, próbując go znaleźć; nazwa "healpix" nie przywołuje dokładnie sfer ...


1

przy małej liczbie punktów można przeprowadzić symulację:

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)]

aby poprawić moją odpowiedź, należy zmienić najbliższy_index = i na najbliższy_index = randchoice (i, j)
robert king

1

Weź dwa największe z twoich współczynników N, jeśli N==20to dwa największe czynniki są {5,4}, lub bardziej ogólnie {a,b}. Oblicz

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

Umieść swój pierwszy punkt na {90-dlat/2,(dlong/2)-180}, drugi na {90-dlat/2,(3*dlong/2)-180}, trzeci na {90-dlat/2,(5*dlong/2)-180}, aż raz objechałeś świat, w którym to momencie będziesz miał mniej więcej to, {75,150}kiedy będziesz obok {90-3*dlat/2,(dlong/2)-180}.

Oczywiście pracuję nad tym w stopniach na powierzchni kulistej ziemi, ze zwykłymi konwencjami tłumaczenia +/- na N / S lub E / W. I oczywiście daje to całkowicie nielosowy rozkład, ale jest jednolity i punkty nie są zebrane razem.

Aby dodać pewien stopień losowości, możesz wygenerować 2 normalne rozłożenie (ze średnią 0 i std dev {dlat / 3, dlong / 3}, jeśli to konieczne) i dodać je do swoich równomiernie rozłożonych punktów.


5
wyglądałoby to dużo lepiej, gdybyś pracował w grzechu (łac.), a nie w łac. i tak jest, będziesz miał dużo skupisk w pobliżu biegunów.
Andrew Cooke

1

edycja: To nie odpowiada na pytanie, które OP miał zadać, pozostawiając je tutaj na wypadek, gdyby ludzie uznali je za przydatne.

Używamy reguły mnożenia prawdopodobieństwa w połączeniu z nieskończonością. W rezultacie powstają 2 wiersze kodu, aby osiągnąć pożądany rezultat:

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

(zdefiniowane w następującym układzie współrzędnych :)

wprowadź opis obrazu tutaj

Twój język ma zwykle jednolity prymityw liczb losowych. Na przykład w Pythonie możesz użyć random.random()do zwrócenia liczby z zakresu [0,1). Możesz pomnożyć tę liczbę przez k, aby otrzymać liczbę losową z zakresu [0,k). Tak więc w Pythonie uniform([0,2pi))oznaczałoby random.random()*2*math.pi.


Dowód

Teraz nie możemy przypisać θ równomiernie, w przeciwnym razie zbrylalibyśmy się na biegunach. Chcemy przypisać prawdopodobieństwa proporcjonalne do pola powierzchni klina kulistego (θ na tym diagramie to w rzeczywistości φ):

wprowadź opis obrazu tutaj

Przemieszczenie kątowe dφ na równiku spowoduje przemieszczenie dφ * r. Jakie będzie to przemieszczenie przy dowolnym azymucie θ? Cóż, promień od osi z wynosi r*sin(θ), więc długość łuku tej „szerokości geograficznej” przecinającej klin wynosi dφ * r*sin(θ). W ten sposób obliczamy skumulowany rozkład obszaru do pobrania z niego, całkując powierzchnię wycinka od bieguna południowego do bieguna północnego.

wprowadź opis obrazu tutaj(gdzie rzeczy = dφ*r)

Spróbujemy teraz uzyskać odwrotność CDF, aby pobrać z niej próbkę: http://en.wikipedia.org/wiki/Inverse_transform_sampling

Najpierw normalizujemy, dzieląc nasz prawie-CDF przez jego maksymalną wartość. Ma to uboczny efekt anulowania dφ i r.

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

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

A zatem:

let x by a random float in range [0,1]
θ = -arcsin(1-2*x)

Czy nie jest to równoważne opcji, którą odrzucił jako „w 100% losową”? rozumiem, że chce, aby były one bardziej równomiernie rozmieszczone niż jednolity losowy rozkład.
andrew Cooke

@ BlueRaja-DannyPflughoeft: Hmm, w porządku. Chyba nie przeczytałem pytania tak uważnie, jak powinienem. I tak zostawiam to tutaj na wypadek, gdyby inni uznali to za przydatne. Dziękuję za zwrócenie uwagi.
ninjagecko

1

LUB ... aby umieścić 20 punktów, oblicz środki dwudziestościanów. Za 12 punktów znajdź wierzchołki dwudziestościanu. Za 30 punktów środek krawędzi dwudziestościanu. możesz zrobić to samo z czworościanem, sześcianem, dwunastościanem i ośmiościanem: jeden zestaw punktów znajduje się na wierzchołkach, inny na środku ściany, a drugi na środku krawędzi. Nie można ich jednak mieszać.


Dobry pomysł, ale działa tylko w przypadku 4, 6, 8, 12, 20, 24 lub 30 punktów.
The Guy with The Hat

Jeśli chcesz oszukiwać, możesz użyć środka twarzy i pionów. Będą one nie być równo rozmieszczone, ale przyzwoity przybliżeniem. To jest miłe, ponieważ jest deterministyczne.
chessofnerd

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)])

4
Byłoby pomocne, gdybyś napisał jakiś tekst wyjaśniający, co to ma zrobić, aby PO nie musiał wierzyć, że to po prostu zadziała.
hcarver

0

@robert king To naprawdę fajne rozwiązanie, ale zawiera kilka niechlujnych błędów. Wiem jednak, że bardzo mi to pomogło, więc nieważne z niechlujstwa. :) Oto poprawiona wersja ....

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()

-1

To działa i jest śmiertelnie proste. Tyle punktów, ile chcesz:

    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());
    }
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.