Wygeneruj losowy punkt w okręgu (równomiernie)

212

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 .

aioobe
źródło
18
Czy wada próbkowania odrzucenia jest naprawdę wielką sprawą? Oczekiwana liczba wymaganych prób wynosi 4 / π ≈ 1,27, a prawdopodobieństwo, że potrzebujesz więcej niż k prób, wynosi (1-π / 4) ^ k. Dla k = 20 jest to ≈ .00000000000004, a dla k = 50 jest rzędu 10 ^ {- 34}. Możesz wziąć te szanse każdego dnia; poradzisz sobie dobrze.
ShreevatsaR
3
W rzeczywistości próba odrzucenia zapewnia gwarancję zakończenia. Szanse są nieskończenie niskie (a dokładnie zero), że Twój algorytm nigdy się nie skończy.
Jared Nielsen
2
Moim zdaniem znaczenie wad próbkowania przy odrzuceniu jest proporcjonalne do łatwości zastosowania metody próbkowania, która pozwala uniknąć odrzucenia. W takim przypadku wada jest ważna, ponieważ próbkowanie bez odrzucenia jest proste.
spex
4
@spex W praktyce technika odrzucania jest szybsza, ponieważ pozwala uniknąć konieczności oceny funkcji transcendentalnych.
pjs
2
(ciąg dalszy) odrzucenie: 0,52 s Wszystkie dały identyczne średnie i standardowe odchylenia (do 3 sig. rys.). Zgodnie z oczekiwaniami, próbka odrzucenia nie powiodła się w 27% przypadków (4 / pi-1), dlatego potrzebowała 27% więcej liczb losowych niż Btilly, ale 15% mniej niż sigfpe. Potwierdza to komentarze pjs i innych, że próba odrzucenia jest prawdopodobnie najlepszym podejściem, chyba że generowanie losowych danych jest bardzo drogie.
Peter Davidson,

Odpowiedzi:

189

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.

t = 2*pi*random()
u = random()+random()
r = if u>1 then 2-u else u
[r*cos(t), r*sin(t)]

Tutaj jest w Mathematica.

f[] := Block[{u, t, r},
  u = Random[] + Random[];
  t = Random[] 2 Pi;
  r = If[u > 1, 2 - u, u];
  {r Cos[t], r Sin[t]}
]

ListPlot[Table[f[], {10000}], AspectRatio -> Automatic]

wprowadź opis zdjęcia tutaj

sigfpe
źródło
6
@Karelzarath Podoba mi się sprzeczne z intuicją pojęcie nieskończenie cienkiego trójkąta, który z jednej strony jest jeszcze szerszy niż z drugiej :-) Otrzymuje właściwą odpowiedź.
sigfpe,
2
@hammar Nie jestem pewien, czy dobrze się uogólnia do n wymiarów. Ale do 3d możesz użyć innego wyniku Archimedesa! Użyj twierdzenia „hat-box”, aby wygenerować punkt na cylindrze (łatwe!), A następnie odwzorować go z powrotem na kulę. To daje kierunek. Teraz używaj 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.
sigfpe
2
Pomyślałem, że 1 minuta
wymyślił
3
@Tharwen Zwróć uwagę, że w okręgu jest więcej punktów o promieniu 0,9-1,0 niż o promieniu 0,0-0,1. random () + random () generuje promienie, które prawdopodobnie wynoszą około 1,0, ale mieszczą się w przedziale 0,0-2,0. Po złożeniu są bardziej prawdopodobne, że mają około 1,0 i zawsze mieszczą się w przedziale 0,0-1,0. Co więcej, jest to dokładnie proporcja potrzebna w pierwszym zdaniu tego komentarza. Już samo zmniejszenie o połowę daje więcej liczb wokół znaku 0,5, co byłoby błędem.
sigfpe,
2
@Tharwen Spróbuj użyć obu schematów do generowania liczb losowych i zobacz, co otrzymujesz. 2 * random () daje liczby równomiernie rozmieszczone w zakresie od 0 do 2. random () + random () daje liczby w zakresie od 0 do 2, ale (zwykle) będzie więcej liczb w pobliżu 1,0 niż w pobliżu 0,0 lub 2,0. To tak, jakby rzucić dwiema kostkami i sumowaniem z większym prawdopodobieństwem dałoby 7 niż jakakolwiek inna liczba.
sigfpe,
133

Jak wygenerować losowy punkt w okręgu o promieniu R :

r = R * sqrt(random())
theta = random() * 2 * PI

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

x = centerX + r * cos(theta)
y = centerY + r * sin(theta)


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ą

  1. Z pliku PDF utwórz funkcję dystrybucji skumulowanej (CDF)
  2. Odzwierciedl to wzdłuż y = x
  3. Zastosuj wynikową funkcję do jednolitej wartości od 0 do 1.

Brzmi skomplikowanie? Pozwól mi wstawić cytat z małym bocznym śladem, który przekazuje intuicję:

Załóżmy, że chcemy wygenerować punkt losowy o następującym rozkładzie:

                

To jest

  • 1/5 punktów równomiernie między 1 a 2, oraz
  • 4/5 punktów równomiernie między 2 a 3.

CDF jest, jak sama nazwa wskazuje, skumulowaną wersją pliku PDF. Intuicyjnie: podczas gdy PDF ( x ) opisuje liczbę losowych wartości w x , CDF ( x ) opisuje liczbę losowych wartości mniejszych niż x .

W takim przypadku CDF wyglądałby następująco:

                

Aby zobaczyć, jak to jest przydatne, wyobraź sobie, że strzelamy pociskami od lewej do prawej na równomiernie rozmieszczonych wysokościach. Gdy kule trafią w linię, spadają na ziemię:

                

Zobacz, jak gęstość pocisków na ziemi odpowiada naszemu pożądanemu rozkładowi! Prawie jesteśmy na miejscu!

Problem polega na tym, że dla tej funkcji oś y jest wyjściem, a oś x jest wejściem . Możemy tylko „strzelać pociskami z ziemi prosto w górę”! Potrzebujemy funkcji odwrotnej!

Dlatego odzwierciedlamy całość; x staje się y, a y staje się x :

                

Nazywamy to CDF -1 . Aby uzyskać wartości zgodnie z pożądanym rozkładem, używamy CDF -1 (random ()).

… 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ć :-)

aioobe
źródło
Ten algorytm można wykorzystać do wydajnego generowania punktów na pierścieniu.
Ivan Kovtun
Na ringu? Jak ze stałym promieniem? Nie jestem pewien, czy rozumiem twoje pytanie, ale jeśli masz ustalony promień, musisz po prostu randomizować kąt.
aioobe
2
Próbowałem użyć prostszego słowa „Pierścień” zamiast pierścienia - regionu ograniczonego dwoma koncentrycznymi okręgami. W takim przypadku algorytm odrzucania nie działa i trudno jest uogólnić pierwszy algorytm najwyższego poziomu. A obudowa narożna z jednym promieniem jest również objęta twoim algorytmem. Zawsze generujemy promień jako sqrt (losowo (min_radius ^ 2, max_radius ^ 2)), nawet gdy min_radius == max_radius.
Ivan Kovtun
1
Och, miło! Mówiąc wprost random(min_radius², max_radius²), czy masz na myśli coś równoważnego random() * (max_radius² - min_radius²) + min_radius², gdzie random()zwraca jednolitą wartość od 0 do 1?
aioobe
tak, dokładnie to mam na myśli: promień = sqrt (random () * (max_radius² - min_radius²) + min_radius²).
Ivan Kovtun
27

Oto szybkie i proste rozwiązanie.

Wybierz dwie losowe liczby z zakresu (0, 1), a mianowicie ai b. Jeśli b < azamień 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.

btilly
źródło
To z jakiegoś powodu daje mi znacznie bardziej równomierny rozkład niż zaakceptowana odpowiedź, chociaż musiałem podzielić współrzędną przez promień, w przeciwnym razie znajduje się w kręgu R ^ 2
Greg Zaal
3
Dzięki, to jest twój kod w Javie, może ktoś uzna go za przydatny: float random1 = MathUtils.random (); float random2 = MathUtils.random (); float randomXPoint = random2 * promień MathUtils.cos (MathUtils.PI2 * random1 / random2); float randomYPoint = random2 * promień MathUtils.sin (MathUtils.PI2 * random1 / random2);
Tony Ceralva,
bardzo dobrze! Podoba mi się pomysł większego prawdopodobieństwa scentralizowania punktów, więc jeśli nie wymienimy się, kiedy b < amożemy to osiągnąć! np. w javascript jsfiddle.net/b0sb5ogL/1
Guilherme
Myślę, że twoje rozwiązanie jest złe. Nie daje jednorodnych wyników. Sprawdź zrzut ekranu prntscr.com/fizxgc
bolec_kolec
4
Czy możesz wyjaśnić nieco więcej, jak wyciąć okrąg i go wyprostować?
kec
21

Zwróć uwagę na gęstość punktów proporcjonalną do odwrotnego kwadratu promienia, dlatego zamiast wybierać rz [0, r_max], wybierać z [0, r_max^2], a następnie obliczać współrzędne jako:

x = sqrt(r) * cos(angle)
y = sqrt(r) * sin(angle)

Zapewni to jednolity rozkład punktów na dysku.

http://mathworld.wolfram.com/DiskPointPicking.html

Libor
źródło
12

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.

Chris A.
źródło
10

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.

użytkownik502248
źródło
9

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:

          0          if r<=0
  CDF =   (r/R)**2   if 0 < r <= R
          1          if r > R

I PDF:

PDF = d/dr(CDF) = 2 * (r/R**2) (0 < r <= R).

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:

x = ρ * cos(φ)
y = ρ * sin(φ)

Nie można się oprzeć opublikowaniu kodu python dla R = 1.

from matplotlib import pyplot as plt
import numpy as np

rho = np.sqrt(np.random.uniform(0, 1, 5000))
phi = np.random.uniform(0, 2*np.pi, 5000)

x = rho * np.cos(phi)
y = rho * np.sin(phi)

plt.scatter(x, y, s = 4)

Dostaniesz

wprowadź opis zdjęcia tutaj

Pommy
źródło
7

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
5
A raczej prawdopodobieństwo, że punkt spadnie w dowolnym dowolnym regionie, jest proporcjonalne do obszaru regionu - przy założeniu, że region ma obszar .
ShreevatsaR
@Shree: Prawidłowo, co mam na myśli przez moje oświadczenie w nawiasach. Wyjaśnię to, dzięki. btw, o blogu, nie było prawdziwego dowodu, że arbitralne obszary dają proporcjonalne prawdopodobieństwa, dlatego postanowiłem to sformułować w ten sposób.
6

Oto mój kod Python do generowania numlosowych punktów z koła o promieniu rad:

import matplotlib.pyplot as plt
import numpy as np
rad = 10
num = 1000

t = np.random.uniform(0.0, 2.0*np.pi, num)
r = rad * np.sqrt(np.random.uniform(0.0, 1.0, num))
x = r * np.cos(t)
y = r * np.sin(t)

plt.plot(x, y, "ro", ms=1)
plt.axis([-15, 15, -15, 15])
plt.show()
krishnab
źródło
1
Dlaczego nie tylko r = np.sqrt(np.random.uniform(0.0, rad**2, num))?
4

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 punkty x^2+y^2<=R^2.

ascanio
źródło
Masz na myśli x ^ 2 + y ^ 2 <= R ^ 2 Myślę, że.
sigfpe
1
To jest próbkowanie odrzucenia. Jest w porządku, ale oznacza, że ​​czas obliczeń może się nieco różnić, co może być problemem.
Steve Bennett
Wszystkie kwadraty są 4-stronne.
xaxxon
Ten algorytm jest bardziej wydajny niż wszystko, co obejmuje pierwiastki kwadratowe lub obliczenia sin / cos. Odrzuca mniej niż 21,5% punktów kwadratu.
Ivan Kovtun
3

Rozwiązanie w Javie i przykład dystrybucji (2000 punktów)

public void getRandomPointInCircle() {
    double t = 2 * Math.PI * Math.random();
    double r = Math.sqrt(Math.random());
    double x = r * Math.cos(t);
    double y = r * Math.sin(t);
    System.out.println(x);
    System.out.println(y);
}

Dystrybucja 2000 punktów

oparty na rozwiązaniu previus https://stackoverflow.com/a/5838055/5224246 od @sigfpe

bolec_kolec
źródło
2

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

R^2 cdf[x] = x^2

x = R Sqrt[ cdf[x] ]

Możemy teraz zastąpić cdf losową liczbą od 0 do 1

x = R Sqrt[ RandomReal[{0,1}] ]

Wreszcie

r = R Sqrt[  RandomReal[{0,1}] ];
theta = 360 deg * RandomReal[{0,1}];
{r,theta}

otrzymujemy współrzędne biegunowe {0.601168 R, 311.915 deg}

Steven Siew
źródło
1

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 rproporcjonalna do r.

rekurencyjny
źródło
1

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.

bool[,] getMatrix(System.Drawing.Rectangle r) {
    bool[,] matrix = new bool[r.Width, r.Height];
    return matrix;
}

void fillMatrix(ref bool[,] matrix, Vector center) {
    double radius = center.X;
    Random r = new Random();
    for (int y = 0; y < matrix.GetLength(0); y++) {
        for (int x = 0; x < matrix.GetLength(1); x++)
        {
            double distance = (center - new Vector(x, y)).Length;
            if (distance < radius) {
                matrix[x, y] = r.NextDouble() > 0.5;
            }
        }
    }

}

private void drawMatrix(Vector centerPoint, double radius, bool[,] matrix) {
    var g = this.CreateGraphics();

    Bitmap pixel = new Bitmap(1,1);
    pixel.SetPixel(0, 0, Color.Black);

    for (int y = 0; y < matrix.GetLength(0); y++)
    {
        for (int x = 0; x < matrix.GetLength(1); x++)
        {
            if (matrix[x, y]) {
                g.DrawImage(pixel, new PointF((float)(centerPoint.X - radius + x), (float)(centerPoint.Y - radius + y)));
            }
        }
    }

    g.Dispose();
}

private void button1_Click(object sender, EventArgs e)
{
    System.Drawing.Rectangle r = new System.Drawing.Rectangle(100,100,200,200);
    double radius = r.Width / 2;
    Vector center = new Vector(r.Left + radius, r.Top + radius);
    Vector normalizedCenter = new Vector(radius, radius);
    bool[,] matrix = getMatrix(r);
    fillMatrix(ref matrix, normalizedCenter);
    drawMatrix(center, radius, matrix);
}

wprowadź opis zdjęcia tutaj

Marino Šimić
źródło
3
Dystrybucje nie są „wystarczająco losowe”. Są albo losowe dla danej definicji losowości. Twoja odpowiedź jest skośna: nie komentujesz swojego kodu ani nie wyjaśniasz, jak do niego doszedłeś. Skośne odpowiedzi są trudne do naśladowania i trudniejsze do zaufania.
Richard
1

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.

Benjamin Bannier
źródło
Jak dokładnie wybrać r z „rozkładu 1 / r” ?
aioobe
0

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.

arsaKasra
źródło
Ciekawe podejście na początek od dtheta1 / dtheta2 = r2 / r1. Czy mógłbyś wyjaśnić, jak wymyśliłeś to równanie?
aioobe
Jak wspomnieli inni (na przykład honk), element różnicowy powierzchni koła jest podawany jako r dr dtheta, więc jeśli przyjmiemy r1 = r2, wówczas będziemy mieli dr1 * dtheta1 = dr2 * dtheta2, a reszta nastąpi .
arsaKasra
0

Rozwiązanie dla programistów:

  • Utwórz mapę bitową (macierz wartości boolowskich). Może być tak duży, jak chcesz.
  • Narysuj okrąg na tej mapie bitowej.
  • Utwórz tabelę przeglądową punktów koła.
  • Wybierz losowy indeks w tej tabeli odnośników.
const int RADIUS = 64;
const int MATRIX_SIZE = RADIUS * 2;

bool matrix[MATRIX_SIZE][MATRIX_SIZE] = {0};

struct Point { int x; int y; };

Point lookupTable[MATRIX_SIZE * MATRIX_SIZE];

void init()
{
  int numberOfOnBits = 0;

  for (int x = 0 ; x < MATRIX_SIZE ; ++x)
  {
    for (int y = 0 ; y < MATRIX_SIZE ; ++y)
    {
      if (x * x + y * y < RADIUS * RADIUS) 
      {
        matrix[x][y] = true;

        loopUpTable[numberOfOnBits].x = x;
        loopUpTable[numberOfOnBits].y = y;

        ++numberOfOnBits;

      } // if
    } // for
  } // for
} // ()

Point choose()
{
  int randomIndex = randomInt(numberOfBits);

  return loopUpTable[randomIndex];
} // ()

Mapa bitowa jest konieczna tylko do wyjaśnienia logiki. To jest kod bez mapy bitowej:

const int RADIUS = 64;
const int MATRIX_SIZE = RADIUS * 2;

struct Point { int x; int y; };

Point lookupTable[MATRIX_SIZE * MATRIX_SIZE];

void init()
{
  int numberOfOnBits = 0;

  for (int x = 0 ; x < MATRIX_SIZE ; ++x)
  {
    for (int y = 0 ; y < MATRIX_SIZE ; ++y)
    {
      if (x * x + y * y < RADIUS * RADIUS) 
      {
        loopUpTable[numberOfOnBits].x = x;
        loopUpTable[numberOfOnBits].y = y;

        ++numberOfOnBits;
      } // if
    } // for
  } // for
} // ()

Point choose()
{
  int randomIndex = randomInt(numberOfBits);

  return loopUpTable[randomIndex];
} // ()
selalerer
źródło
0

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.

sernik
źródło
Jesteś pierwszym, który odwołuje się tutaj do twierdzenia Pitagorasa. Bardzo bym chciał, gdybyś mógł to rozszerzyć o jedną lub dwie liczby, popierające twoje wyjaśnienie. Obecnie
mam trudności z obserwowaniem
@ aioobe Próbowałem sformułować odpowiedź, w razie potrzeby mogę dodać diagramy :)
cheesefest,
Rozumiem, dlaczego nie mogę rozłożyć tego liniowo. Nie rozumiem tutaj związku z Pitagorasem lub sin / cos. Może diagramy mogą mi tutaj pomóc.
aioobe
Pitagoras to mój błąd, proszę zapomnij o tym, ale mam nadzieję, że zrozumiałeś kwadratową naturę funkcji, dokładny (2 / R2) × r potrzebuje dowodu i nie jestem w stanie wymyślić żadnego dowodu na to
cheesefest
0

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.

import numpy
import math
import matplotlib.pyplot as plt

def sq_point_in_circle(r):
    """
    Generate a random point in an r radius circle 
    centered around the start of the axis
    """

    t = 2*math.pi*numpy.random.uniform()
    R = (numpy.random.uniform(0,1) ** 0.5) * r

    return(R*math.cos(t), R*math.sin(t))

R = 200 # Radius
N = 1000 # Samples

points = numpy.array([sq_point_in_circle(R) for i in range(N)])
plt.scatter(points[:, 0], points[:,1])

wprowadź opis zdjęcia tutaj

AChervony
źródło
0

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łaby N=10punkty wewnątrz koła. Stosunek tutaj jest10 / pi

Teraz podwajamy obszar i liczbę punktów

Dla r=2iN=20

To daje powierzchnię, 4pia stosunek wynosi teraz 20/4pilub 10/2pi. Stosunek będzie się zmniejszał, im większy będzie promień, ponieważ jego wzrost jest kwadratowy, a Nskala liniowa.

Aby to naprawić, możemy po prostu powiedzieć

x = r^2
sqrt(x) = r

Jeśli wygenerujesz wektor we współrzędnych biegunowych takich jak ten

length = random_0_1();
angle = random_0_2pi();

Więcej punktów wylądowałoby wokół centrum.

length = sqrt(random_0_1());
angle = random_0_2pi();

length nie jest już równomiernie rozłożony, ale wektor będzie teraz równomiernie rozłożony.

Maik Klein
źródło
-1

1) Wybierz losowy X od -1 do 1.

var X:Number = Math.random() * 2 - 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:

var YMin:Number = -Math.sqrt(1 - X * X);
var YMax:Number = Math.sqrt(1 - X * X);

3) Wybierz losowe Y spośród tych skrajności:

var Y:Number = Math.random() * (YMax - YMin) + YMin;

4) Uwzględnij swoje położenie i promień w wartości końcowej:

var finalX:Number = X * radius + pos.x;
var finalY:Number = Y * radois + pos.y;
Xytor
źródło
2
Nierównomierne - prawdopodobieństwo dla [-1, 0] jest znacznie wyższe niż dla [0, 0], biorąc pod uwagę, że p ([- 1, Y]) = p ([0, Y]), i jest tylko jeden wybór dla [-1, Y] i wiele opcji dla [0, Y].
Amadan,
To rozwiązanie preferuje punkty w kierunku lewej i prawej strony koła. Punkty o wartości bliskiej zeru są niedostatecznie reprezentowane. W ogóle nie jednolity rozkład.
Dawood ibn Kareem