Trzeba wygenerować losową równomiernie wewnątrz koła o promieniu R .
Zdaję sobie sprawę, że po prostu wybierając jednorodnie losowy kąt w przedziale [0 ... 2π) i jednolicie losowy promień w przedziale (0 ... R ) uzyskałbym więcej punktów w kierunku środka, ponieważ dla dwóch podanych promienie, punkty w mniejszym promieniu będą bliżej siebie niż w punktach o większym promieniu.
Znalazłem tutaj wpis na blogu , ale nie rozumiem jego uzasadnienia. Przypuszczam, że jest to poprawne, ale naprawdę chciałbym zrozumieć, skąd on bierze (2 / R 2 ) × r i jak wyciąga ostateczne rozwiązanie.
Aktualizacja: 7 lat po opublikowaniu tego pytania wciąż nie otrzymałem zadowalającej odpowiedzi na pytanie dotyczące matematyki stojącej za algorytmem pierwiastka kwadratowego. Więc spędziłem dzień na pisaniu odpowiedzi. Link do mojej odpowiedzi .
źródło
Odpowiedzi:
Podejdźmy do tego tak, jak zrobiłby to Archimedes.
Jak możemy równomiernie wygenerować punkt w trójkącie ABC, gdzie | AB | = | BC |? Uprośćmy to poprzez rozszerzenie na równoległobok ABCD. Łatwo jest generować punkty jednolicie w ABCD. Jednolicie wybieramy losowy punkt X na AB i Y na BC i wybieramy Z tak, że XBYZ jest równoległobokiem. Aby uzyskać jednolicie wybrany punkt w oryginalnym trójkącie, po prostu złóż wszystkie punkty pojawiające się w ADC z powrotem do ABC wzdłuż AC.
Teraz rozważ koło. W granicy możemy myśleć o tym jako o nieskończenie wielu trójkątach izocel ABC ABC z początkiem B i A i C na obwodzie znikającymi blisko siebie. Możemy wybrać jeden z tych trójkątów, po prostu wybierając kąt theta. Musimy teraz wygenerować odległość od środka, wybierając punkt w ABC taśmy. Ponownie rozciągnij się do ABCD, gdzie D jest teraz dwa razy większy od promienia środka koła.
Wybieranie losowego punktu w ABCD jest łatwe przy użyciu powyższej metody. Wybierz losowy punkt na AB. Jednolicie wybierz losowy punkt na BC. To znaczy. wybierz parę liczb losowych xiy równomiernie na [0, R], podając odległości od środka. Nasz trójkąt jest cienkim kawałkiem, więc AB i BC są zasadniczo równoległe. Zatem punkt Z to po prostu odległość x + y od początku. Jeśli x + y> R składamy z powrotem.
Oto kompletny algorytm dla R = 1. Mam nadzieję, że zgadzasz się, że to całkiem proste. Korzysta z trig, ale możesz dać gwarancję, ile czasu to zajmie i ile
random()
potrzebuje połączeń, w przeciwieństwie do próbkowania odrzucenia.Tutaj jest w Mathematica.
źródło
random()+random()+random()
z bardziej złożonym fałdowaniem (tj. 6-kierunkowym fałdowaniem nieskończenie cienkiego równoległościanu do terahedronu). Nie jestem jednak przekonany, że to dobra metoda.Jak wygenerować losowy punkt w okręgu o promieniu R :
(Przyjmując
random()
równomiernie podaje wartość od 0 do 1)Jeśli chcesz przekonwertować to na współrzędne kartezjańskie, możesz to zrobić
Dlaczego
sqrt(random())
?Spójrzmy na matematykę, która prowadzi do
sqrt(random())
. Załóżmy dla uproszczenia, że pracujemy z okręgiem jednostkowym, tj. R = 1.Średnia odległość między punktami powinna być taka sama, niezależnie od tego, jak daleko od środka patrzymy. Oznacza to na przykład, że patrząc na obwód koła o obwodzie 2 powinniśmy znaleźć dwa razy więcej punktów niż liczba punktów na obwodzie koła o obwodzie 1.
Ponieważ obwód koła (2π r ) rośnie liniowo z r , wynika z tego, że liczba losowych punktów powinna rosnąć liniowo z r . Innymi słowy, pożądana funkcja gęstości prawdopodobieństwa (PDF) rośnie liniowo. Ponieważ plik PDF powinien mieć powierzchnię równą 1, a maksymalny promień to 1, mamy
Wiemy więc, jak powinna wyglądać pożądana gęstość naszych losowych wartości. Teraz: Jak wygenerować taką losową wartość, gdy mamy tylko jednolitą losową wartość między 0 a 1?
Używamy sztuczki zwanej próbkowaniem z transformacją odwrotną
Brzmi skomplikowanie? Pozwól mi wstawić cytat z małym bocznym śladem, który przekazuje intuicję:
… Wracając do generowania losowych wartości promienia, w których nasz plik PDF wynosi 2 x .
Krok 1: Utwórz CDF:
Ponieważ pracujemy z rzeczywistymi, CDF jest wyrażony jako całka pliku PDF.
CDF ( x ) = ∫ 2 x = x 2
Krok 2: Odzyskaj CDF wzdłuż y = x :
Matematycznie to sprowadza się do zamiany x i y i rozwiązywanie y :
CDF : y = x 2
Zamień: x = y 2
Rozwiąż: y = √ x
CDF -1 : y = √ x
Krok 3: Zastosuj wynikową funkcję do jednolitej wartości od 0 do 1
CDF -1 (losowo ()) = and losowo ()
Właśnie dlatego postanowiliśmy wyprowadzić :-)
źródło
random(min_radius², max_radius²)
, czy masz na myśli coś równoważnegorandom() * (max_radius² - min_radius²) + min_radius²
, gdzierandom()
zwraca jednolitą wartość od 0 do 1?Oto szybkie i proste rozwiązanie.
Wybierz dwie losowe liczby z zakresu (0, 1), a mianowicie
a
ib
. Jeślib < a
zamień je. Chodzi o to, że(b*R*cos(2*pi*a/b), b*R*sin(2*pi*a/b))
.Możesz pomyśleć o tym rozwiązaniu w następujący sposób. Jeśli weźmiesz okrąg, wytniesz go, a następnie wyprostujesz, otrzymasz trójkąt prostokątny. Przeskaluj ten trójkąt w dół, a będziesz miał trójkąt od
(0, 0)
do(1, 0)
do(1, 1)
iz powrotem do(0, 0)
. Wszystkie te przekształcenia zmieniają gęstość równomiernie. To, co zrobiłeś, równomiernie wybrał losowy punkt w trójkącie i odwrócił proces, aby uzyskać punkt w okręgu.źródło
b < a
możemy to osiągnąć! np. w javascript jsfiddle.net/b0sb5ogL/1Zwróć uwagę na gęstość punktów proporcjonalną do odwrotnego kwadratu promienia, dlatego zamiast wybierać
r
z[0, r_max]
, wybierać z[0, r_max^2]
, a następnie obliczać współrzędne jako:Zapewni to jednolity rozkład punktów na dysku.
http://mathworld.wolfram.com/DiskPointPicking.html
źródło
Pomyśl o tym w ten sposób. Jeśli masz prostokąt, w którym jedna oś jest promieniem, a jedna jest kątem, i weźmiesz punkty wewnątrz tego prostokąta, które są w pobliżu promienia 0. Wszystkie one spadną bardzo blisko początku (czyli blisko siebie na okręgu). Jednak, punkty w pobliżu promienia R wszystkie spadną w pobliżu krawędzi koła (to znaczy daleko od siebie).
To może dać ci pojęcie o tym, dlaczego otrzymujesz takie zachowanie.
Współczynnik wyprowadzony na tym łączu informuje, ile odpowiedniego obszaru w prostokącie należy dostosować, aby nie zależał od promienia po odwzorowaniu na okrąg.
Edycja: Więc to, co pisze w łączu, który udostępniasz, brzmi: „Łatwo to zrobić, obliczając odwrotność skumulowanego rozkładu, i otrzymujemy dla r:”.
Podstawowa zasada polega na tym, że można utworzyć zmienną o pożądanym rozkładzie z jednolitego poprzez odwzorowanie jednolitego za pomocą funkcji odwrotnej funkcji skumulowanego rozkładu żądanej funkcji gęstości prawdopodobieństwa. Czemu? Na razie przyjmij to za pewnik, ale to fakt.
Oto moje intuicyjne wyjaśnienie matematyki. Funkcja gęstości f (r) w odniesieniu do r musi być proporcjonalna do samego r. Zrozumienie tego faktu jest częścią każdej podstawowej księgi rachunkowej. Zobacz sekcje dotyczące elementów obszaru polarnego. Wspominali o tym inni plakaty.
Nazwiemy to f (r) = C * r;
To okazuje się większość pracy. Ponieważ f (r) powinno być gęstością prawdopodobieństwa, można łatwo zauważyć, że całkując f (r) w przedziale (0, R) otrzymujesz C = 2 / R ^ 2 (jest to ćwiczenie dla czytelnika .)
Zatem f (r) = 2 * r / R ^ 2
OK, więc w ten sposób otrzymujesz formułę w linku.
Następnie ostatnia część wychodzi od jednolitej zmiennej losowej u w (0,1), którą należy odwzorować za pomocą funkcji odwrotnej funkcji rozkładu skumulowanego z tej pożądanej gęstości f (r). Aby zrozumieć, dlaczego tak jest, musisz znaleźć tekst prawdopodobieństwa zaawansowanego, taki jak Papoulis, (lub sam go wyprowadzić).
Całkując f (r) otrzymujesz F (r) = r ^ 2 / R ^ 2
Aby znaleźć funkcję odwrotną tego, ustaw u = r ^ 2 / R ^ 2, a następnie rozwiąż dla r, co daje ci r = R * sqrt (u)
To również ma sens intuicyjnie, u = 0 powinno być odwzorowane na r = 0. Również u = 1 powinno być odwzorowane na r = R. Ponadto działa według funkcji pierwiastka kwadratowego, która ma sens i pasuje do łącza.
źródło
Powodem, dla którego naiwne rozwiązanie nie działa, jest to, że daje ono wyższą gęstość prawdopodobieństwa punktom bliższym środka okręgu. Innymi słowy, okrąg o promieniu r / 2 ma prawdopodobieństwo r / 2 otrzymania punktu w nim wybranego, ale ma powierzchnię (liczbę punktów) pi * r ^ 2/4.
Dlatego chcemy, aby gęstość prawdopodobieństwa promienia miała następującą właściwość:
Prawdopodobieństwo wyboru promienia mniejszego lub równego danemu r musi być proporcjonalne do obszaru koła o promieniu r. (ponieważ chcemy mieć równomierny rozkład punktów, a większe obszary oznaczają więcej punktów)
Innymi słowy, chcemy, aby prawdopodobieństwo wyboru promienia między [0, r] było równe jego udziałowi w całkowitej powierzchni koła. Całkowity obszar okręgu wynosi pi * R ^ 2, a obszar okręgu o promieniu r wynosi pi * r ^ 2. Dlatego chcielibyśmy, aby prawdopodobieństwo wyboru promienia między [0, r] było (pi * r ^ 2) / (pi * R ^ 2) = r ^ 2 / R ^ 2.
Teraz nadchodzi matematyka:
Prawdopodobieństwo wyboru promienia między [0, r] jest całką p (r) dr od 0 do r (tylko dlatego, że dodajemy wszystkie prawdopodobieństwa mniejszych promieni). Zatem chcemy całki (p (r) dr) = r ^ 2 / R ^ 2. Możemy wyraźnie zobaczyć, że R ^ 2 jest stałą, więc wszystko, co musimy zrobić, to dowiedzieć się, które p (r), kiedy zintegrowane dałoby nam coś w rodzaju r ^ 2. Odpowiedź jest wyraźnie stała *. całka (r * stała dr) = r ^ 2/2 * stała. Musi to być równe r ^ 2 / R ^ 2, a zatem stała = 2 / R ^ 2. Zatem masz rozkład prawdopodobieństwa p (r) = r * 2 / R ^ 2
Uwaga: Innym bardziej intuicyjnym sposobem myślenia o tym problemie jest wyobrażenie sobie, że próbujesz nadać każdemu okręgowi o gęstości prawdopodobieństwa promienia ra równą proporcji liczby punktów na jego obwodzie. Tak więc okrąg o promieniu r będzie miał na obwodzie 2 * pi * r „punktów”. Łączna liczba punktów to pi * R ^ 2. Dlatego powinieneś podać prawdopodobieństwo ra okręgu równe (2 * pi * r) / (pi * R ^ 2) = 2 * r / R ^ 2. Jest to o wiele łatwiejsze do zrozumienia i bardziej intuicyjne, ale nie jest tak matematyczne.
źródło
Niech ρ (promień) i φ (azymut) będą dwiema losowymi zmiennymi odpowiadającymi współrzędnym biegunowym dowolnego punktu wewnątrz koła. Jeśli punkty są równomiernie rozmieszczone, to jaka jest funkcja rozkładu ρ i φ?
Dla dowolnego r: 0 <r <R prawdopodobieństwo, że współrzędna promienia ρ będzie mniejsza niż r, wynosi
P [ρ <r] = P [punkt znajduje się w okręgu o promieniu r] = S1 / S0 = (r / R) 2
Gdzie S1 i S0 oznaczają odpowiednio obszary okręgu o promieniu r i R. CDF można więc podać jako:
I PDF:
Zauważ, że dla R = 1 losowa zmienna sqrt (X), gdzie X jest jednolita na [0, 1) ma ten dokładny CDF (ponieważ P [sqrt (X) <y] = P [x <y ** 2] = y * * 2 dla 0 <y <= 1).
Rozkład φ jest oczywiście równomierny od 0 do 2 * π. Teraz możesz tworzyć losowe współrzędne biegunowe i konwertować je na kartezjańskie za pomocą równań trygonometrycznych:
Nie można się oprzeć opublikowaniu kodu python dla R = 1.
Dostaniesz
źródło
To naprawdę zależy od tego, co rozumiesz przez „jednolicie losowy”. Jest to subtelna kwestia i więcej na ten temat można przeczytać na stronie wiki tutaj: http://en.wikipedia.org/wiki/Bertrand_paradox_%28probability%29 , gdzie ten sam problem, dając różne interpretacje „równomiernie losowej” daje różne odpowiedzi!
W zależności od tego, jak wybierzesz punkty, rozkład może się różnić, nawet jeśli w pewnym sensie są one jednolicie losowe .
Wygląda na to, że wpis na blogu próbuje uczynić go jednolicie losowym w tym sensie: jeśli weźmiesz podkoło koła o tym samym środku, prawdopodobieństwo, że punkt spadnie w tym regionie, jest proporcjonalne do obszaru Region. To, jak sądzę, stara się podążać za standardową interpretacją „równomiernie losowego” dla regionów 2D z określonymi obszarami : prawdopodobieństwo upadku punktu w dowolnym regionie (z dobrze zdefiniowanym obszarem) jest proporcjonalne do obszaru tego regionu.
źródło
Oto mój kod Python do generowania
num
losowych punktów z koła o promieniurad
:źródło
r = np.sqrt(np.random.uniform(0.0, rad**2, num))
?Myślę, że w tym przypadku użycie współrzędnych biegunowych jest sposobem na skomplikowanie problemu, znacznie łatwiej byłoby wybrać losowe punkty na kwadrat o bokach długości 2R, a następnie wybrać
(x,y)
takie punktyx^2+y^2<=R^2
.źródło
Rozwiązanie w Javie i przykład dystrybucji (2000 punktów)
oparty na rozwiązaniu previus https://stackoverflow.com/a/5838055/5224246 od @sigfpe
źródło
Najpierw generujemy plik cdf [x], który jest
Prawdopodobieństwo, że punkt jest mniejszy niż odległość x od środka koła. Załóżmy, że okrąg ma promień R.
oczywiście jeśli x wynosi zero, to cdf [0] = 0
oczywiście jeśli x jest R, to cdf [R] = 1
oczywiście jeśli x = r, to cdf [r] = (Pi r ^ 2) / (Pi R ^ 2)
Wynika to z faktu, że każdy „mały obszar” na okręgu ma takie samo prawdopodobieństwo wybrania, więc prawdopodobieństwo jest proporcjonalne do danego obszaru. Obszar podany w odległości x od środka okręgu to Pi r ^ 2
więc cdf [x] = x ^ 2 / R ^ 2, ponieważ Pi się znoszą
mamy cdf [x] = x ^ 2 / R ^ 2, gdzie x przechodzi od 0 do R
Rozwiązujemy więc dla x
Możemy teraz zastąpić cdf losową liczbą od 0 do 1
Wreszcie
otrzymujemy współrzędne biegunowe {0.601168 R, 311.915 deg}
źródło
Istnieje liniowa zależność między promieniem a liczbą punktów „w pobliżu” tego promienia, dlatego musi on zastosować rozkład promienia, który powoduje, że liczba punktów danych w pobliżu promienia jest
r
proporcjonalna dor
.źródło
Kiedyś użyłem tej metody: może być całkowicie niezoptymalizowana (tzn. Używa tablicy punktów, więc nie nadaje się do dużych kół), ale zapewnia wystarczającą losowość. Możesz pominąć tworzenie matrycy i narysować bezpośrednio, jeśli chcesz. Metoda polega na losowym losowaniu wszystkich punktów w prostokącie, które mieszczą się w okręgu.
źródło
Elementem obszaru w okręgu jest dA = rdr * dphi. Ten dodatkowy czynnik r zniszczył twój pomysł losowego wyboru ar i phi. Podczas gdy phi jest rozłożone płasko, r nie jest, ale płasko w 1 / r (tzn. Istnieje większe prawdopodobieństwo, że uderzysz w granicę niż w „bycze oko”).
Aby więc generować punkty równomiernie rozmieszczone na okręgu, wybierz phi z rozkładu płaskiego i r z rozkładu 1 / r.
Alternatywnie zastosuj metodę Monte Carlo zaproponowaną przez Mehrdada.
EDYTOWAĆ
Aby wybrać losową wartość r w 1 / r, możesz wybrać losową wartość x z przedziału [1 / R, nieskończoność] i obliczyć r = 1 / x. r jest następnie dystrybuowane płasko w 1 / r.
Aby obliczyć losowe phi, wybierz losowe x z przedziału [0, 1] i oblicz phi = 2 * pi * x.
źródło
Nie wiem, czy to pytanie jest nadal otwarte na nowe rozwiązanie z już udzieloną odpowiedzią, ale zdarzyło mi się, że sam spotkałem dokładnie to samo pytanie. Próbowałem „uzasadnić” siebie rozwiązaniem i znalazłem jedno. Może to być to samo, co niektórzy już tu sugerowali, ale tak czy inaczej:
aby dwa elementy powierzchni koła były równe, zakładając równe dr, musimy mieć dtheta1 / dtheta2 = r2 / r1. Zapisywanie prawdopodobieństwa dla tego elementu jako P (r, theta) = P {r1 <r <r1 + dr, theta1 <theta <theta + dtheta1} = f (r, theta) * dr * dtheta1, i ustawienie dwóch prawdopodobieństwa (dla r1 i r2) równe, dochodzimy do (zakładając, że r i theta są niezależne) f (r1) / r1 = f (r2) / r2 = stała, co daje f (r) = c * r. Reszta określająca stałą c wynika z warunku, że f (r) jest plikiem PDF.
źródło
Rozwiązanie dla programistów:
Mapa bitowa jest konieczna tylko do wyjaśnienia logiki. To jest kod bez mapy bitowej:
źródło
Nadal nie jestem pewien dokładnego „(2 / R2) × r”, ale widoczna jest liczba punktów wymaganych do rozdzielenia w danej jednostce „dr”, tj. Wzrost r będzie proporcjonalny do r2, a nie r.
sprawdź w ten sposób ... liczba punktów pod pewnym kątem theta i między r (0,1r do 0,2r), tj. ułamek ri liczba punktów między r (0,6r do 0,7r) byłaby równa, jeśli użyjesz standardowej generacji, ponieważ różnica wynosi tylko 0,1r między dwoma przedziałami. ale ponieważ obszar pokryty między punktami (0,6r do 0,7r) będzie znacznie większy niż obszar pokryty między 0,1r do 0,2r, równa liczba punktów będzie rzadko rozmieszczona na większym obszarze, zakładam, że już wiesz, więc funkcja generowanie losowych punktów nie może być liniowe, lecz kwadratowe (ponieważ liczba punktów wymaganych do rozłożenia w danej jednostce „dr”, tj. wzrost r będzie proporcjonalny do r2, a nie r), więc w tym przypadku będzie odwrotnie kwadratowe, ponieważ mamy deltę (0.
źródło
Taki zabawny problem.
Uzasadnienie prawdopodobieństwa wyboru punktu obniżenia wraz ze wzrostem odległości od początku osi wyjaśniono wielokrotnie powyżej. Rozliczamy to, biorąc pierwiastek z U [0,1]. Oto ogólne rozwiązanie dla dodatniej wartości rw Pythonie 3.
źródło
Możesz także użyć swojej intuicji.
Obszar koła to
pi*r^2
Dla
r=1
To daje nam powierzchnię
pi
. Załóżmy, że mamy jakąś funkcjęf
, która równomiernie rozproszyłabyN=10
punkty wewnątrz koła. Stosunek tutaj jest10 / pi
Teraz podwajamy obszar i liczbę punktów
Dla
r=2
iN=20
To daje powierzchnię,
4pi
a stosunek wynosi teraz20/4pi
lub10/2pi
. Stosunek będzie się zmniejszał, im większy będzie promień, ponieważ jego wzrost jest kwadratowy, aN
skala liniowa.Aby to naprawić, możemy po prostu powiedzieć
Jeśli wygenerujesz wektor we współrzędnych biegunowych takich jak ten
Więcej punktów wylądowałoby wokół centrum.
length
nie jest już równomiernie rozłożony, ale wektor będzie teraz równomiernie rozłożony.źródło
1) Wybierz losowy X od -1 do 1.
2) Korzystając ze wzoru na koło, oblicz maksymalne i minimalne wartości Y, biorąc pod uwagę, że X i promień 1:
3) Wybierz losowe Y spośród tych skrajności:
4) Uwzględnij swoje położenie i promień w wartości końcowej:
źródło