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

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 ² ) × 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 .

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]

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 ²

Krok 2: Odzyskaj CDF wzdłuż y = x :

Matematycznie to sprowadza się do zamiany x i y i rozwiązywanie y :

CDF :      y = x ²
Zamień:    x = y ²
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ć :-)

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.

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

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.

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.

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

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

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.

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

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.

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

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

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}

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.

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

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.

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.

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];
} // ()

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.

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

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.

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;