Generare un punto casuale all’interno di un cerchio (in modo uniforme)

Ho bisogno di generare una uniformemente punto casuale all’interno di un cerchio di raggio R.

Mi rendo conto che scegliendo semplicemente un modo uniforme casuale angolo nell’intervallo [0 … 2π), in modo uniforme e casuale raggio nell’intervallo (0 … R) finirei con più punti verso il centro, dal momento che per due raggi, punti il raggio più piccolo sarà più vicino l’uno all’altro per i punti più ampio raggio.

Ho trovato un blog su questo qui ma non capisco il suo ragionamento. Suppongo che sia corretto, ma mi piacerebbe davvero capire da dove arriva (2/R2r e come egli deriva la soluzione finale.


Aggiornamento: 7 anni dopo la pubblicazione di questa domanda io non avevo ancora ricevuto una risposta soddisfacente alla effettiva domanda per quanto riguarda la matematica dietro la radice quadrata algoritmo. Così ho passato una giornata a scrivere una risposta a me stesso. Link alla mia risposta.

  • Provare qualcosa di simile: Il pdf al raggio R dovrebbe essere proporzionale al diametro lì.
  • È lo svantaggio di rifiuto di campionamento è davvero un grande affare? Il numero previsto di prova richiesto è 4/π ≈ 1.27, e la probabilità che avete bisogno di più di k cerca è (1-π/4)^k. Per k=20, questo è ≈ .00000000000004 e per k=50 e ‘ dell’ordine di 10^{ -34}. Si può prendere quelle quote in qualsiasi giorno; non avrete problemi.
  • Correlate: stackoverflow.com/questions/1841014/…
  • Ho modificato la mia risposta qui sotto per spiegare il grassetto commento.
  • In realtà, il rifiuto di campionamento di fornire una garanzia per la terminazione. Le probabilità sono infinitamente basso (per essere precisi, zero) che il tuo algoritmo non terminerà mai.
  • A mio parere, l’importanza di svantaggio di rifiuto di campionamento è proporzionale alla facilità di utilizzo di un metodo di campionamento che evita il rigetto. In questo caso, lo svantaggio è importante perché il campionamento senza rigetto è semplice.
  • In pratica, il rifiuto, la tecnica è più veloce in quanto si evita la necessità di trascendentale funzione di valutazioni.
  • Ho voluto fare qualche test di velocità differenze, così ho implementato l’approccio raccomandato dal sigfpe e btilly, così come il semplice rifiuto della tecnica. Esecuzione in c# (che utilizza il Sistema.Casuale con costante seme) i miei tempi per 10m punti sono stati sigfpe: 1.17 s btilly: 1.12 s
  • (cont) rifiuto: 0.52 s hanno dato Tutti identici medie e deviazioni standard (a 3 sig. fig). Come previsto, il rifiuto di campionamento non è riuscito 27% del tempo (4/pi-1), in modo necessario, il 27% in più di numeri casuali di btilly ma il 15% in meno sigfpe. Questo conferma le osservazioni fatte da pjs e altri che il rifiuto di campionamento è probabilmente l’approccio migliore, a meno che non casuali sono molto costosi per generare.

InformationsquelleAutor aioobe | 2011-04-29

 

21 Replies
  1. 182

    Lasciare che l’approccio di questo come di Archimede avrebbe.

    Come si può generare un punto in modo uniforme in un triangolo ABC, dove |AB|=|BC|? Proviamo a rendere questo più facile da estendere a un parallelogramma ABCD. È facile generare punti in modo uniforme in ABCD. Abbiamo uniformemente scegliere un punto casuale X AB e Y su BC e scegliere Z tali che XBYZ è un parallelogramma. Per ottenere una uniformemente punto scelto in originale triangolo ci basta piegare i punti che appaiono in ADC di nuovo giù per ABC lungo CA.

    Consideriamo ora un cerchio. Al limite si può pensare ad esso come un infinito numero di isoceles triangoli ABC con B all’origine e A e C sulla circonferenza infinitamente vicini. Si può scegliere uno di questi triangoli semplicemente scegliendo un angolo theta. Così ora abbiamo bisogno di generare una distanza dal centro con la scelta di un punto nello spicchio di ABC. Di nuovo, estendere ad ABCD, dove D è ora due volte il raggio dal centro del cerchio.

    Scelta di un punto casuale in ABCD è facile utilizzando il metodo di cui sopra. Scegliere un punto casuale su AB. Uniformemente scegliere un punto casuale su BC. Ie. scegliere una coppia di numeri casuali x e y in modo uniforme su [0,R], dando distanze dal centro. Il nostro triangolo è un sottile nastro in modo AB e BC sono sostanzialmente in parallelo. Quindi il punto Z è semplicemente una distanza x+y dall’origine. Se x+y>R si piega verso il basso.

    Ecco l’algoritmo completo per R=1. Spero siate d’accordo è abbastanza semplice. Utilizza trig, ma si può dare una garanzia su quanto tempo ci vorrà, e come molti random() chiamate necessita, a differenza di rifiuto di campionamento.

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

    Qui è in 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]
    

    Generare un punto casuale all'interno di un cerchio (in modo uniforme)

    • Mi piace il controsenso concetto di infinitamente piccolo triangolo, che è ancora più ampio in uno dei due estremi 🙂 Si ottiene la risposta giusta.
    • Bello. Questo evita il calcolo della radice quadrata.
    • Penso che tu intenda isoscele triangoli, non equilatero?
    • Sì! Tanto tempo fa quando ho fatto geometria classica 🙂
    • r = sqrt(random()) funziona anche.
    • Solo per curiosità: questo generalizzare ben maggiori dimensioni (ad esempio una sfera tridimensionale)?
    • Non è sicuro che sia generalizza a n dimensioni. Ma il 3d è possibile utilizzare un altro risultato da Archimede! Utilizzare il “cappello-box” teorema di generare un punto sul cilindro (facile!) e poi la mappa è tornato a sfera. Che dà una direzione. Ora uso random()+random()+random() con un po ‘ più complesso pieghevole (ie. 6-strada piega di un infinitesimamente sottile parallelepipedo a un terahedron). Non sono convinto che questo è un buon metodo però.
    • Ho pensato a 1 min a capire la differenza tra random()+random() e 2*casuale()… sono così stupido :/
    • Non è che puoi semplicemente dimezzare r e non perdere tempo a piegare la punta verso il basso?
    • Si noti come in un cerchio ci sono più punti con un raggio di 0.9-1.0 rispetto al raggio 0.0-0.1. random()+random() genera raggi più probabile che sia in giro 1.0, ma giacciono nell’intervallo 0.0-2.0. Quando è ripiegato verso il basso sono più probabili essere di circa 1.0 e sempre nell’intervallo 0.0-1.0. Cosa c’è di più, è esattamente la percentuale necessaria nella prima frase di questo commento. Basta dimezzare produce più numeri intorno a 0.5 marchio e che sarebbe sbagliato.
    • Oh, naturalmente. Vedo ora. OK, un’altra domanda: perché usare random() + random() invece di 2 * random()?
    • Provare a utilizzare entrambi i programmi per generare numeri casuali e vedere cosa si ottiene. 2*casuale() dà i numeri uniformemente distribuiti nell’intervallo da 0 a 2. random()+random() dà i numeri nell’intervallo da 0 a 2 ma c’e ‘ (di solito) più numeri vicino 1.0 di circa 0.0 2.0. E ‘ come lanciare i dadi e la somma è più probabile che dare 7 rispetto a qualsiasi altro numero.
    • Hmm… è un controsenso…
    • Probabilità può essere come quello. Scrivere il codice e giocare con le alternative che tu chiedi. 🙂
    • Può questo metodo essere facilmente estesa per ottenere una uniforme punto casuale della zona all’interno di un cerchio di raggio R1, ma al di fuori di un cerchio di raggio R2, dove R1 > R2 e sia i cerchi sono concentrati nello stesso punto? (Utilizzando il rifiuto di campionamento è abbastanza facile, voglio dire, senza di esso).
    • Ho postato il mio commento come una autonoma domanda, nel caso in cui qualcuno si sente rispondere: stackoverflow.com/questions/13064912/…
    • Se si sta scrivendo un software per generare il numero casuale di punti, non utilizzare questo algoritmo. Il rifiuto di campionamento in un quadrato utilizza un minor numero di chiamate a random(), che è probabilmente la parte più costosa di questo algoritmo.
    • Non sembra come la formula corrisponde alla tua storia. Sembrano due diverse soluzioni, con un utilizzando un parallelogramma metodo e l’altro utilizzando un rotolo di dadi metodo.
    • Perché il ripiegamento verso il basso random()+random() la corretta distribuzione?
    • Si guarda intorno, un sacco di persone hanno suggerito che r=sqrt[random[]]; I tracciati entrambi e entrambi sono a destra. i.imgur.com/zIgqbN2.png i.imgur.com/4bBe7WF.png ho anche capito che non possono permettersi mathematica.
    • Ugh. Non Ldap qui. Oh, bene. Qualcosa mi da fastidio un po’. Considerare il limite per r che tende a 1 di dp/dr dove p è la probabilità di ottenere raggio r. Dal random() + random() sembra che dovrebbe avere un continuo derivata prima 1, ed è anche simmetrica attorno 1, che implica il predetto limite è 0. Ma questo limite non è sicuramente pari a zero se utilizziamo r = sqrt(random()). Pensieri?
    • Questo può essere spiegato dal fatto che la somma di due numeri casuali uniformemente distribuiti in [0,1] ha Irwin Hall di distribuzione. Questa distribuzione (per due numeri la somma) ha forma triangolare con vertice in x=1. Essa è simmetrica rispetto a x=1, quindi se si piega valori >1 indietro, la loro distribuzione sarà la stessa come la distribuzione dei valori ≤1. Risultato complessivo è la distribuzione, linearmente crescente sull’intervallo [0,1].

  2. 75

    Come generare un punto casuale all’interno di un cerchio di raggio R:

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

    (Supponendo random() dà un valore compreso tra 0 e 1 in modo uniforme)

    Se si desidera convertire questo in coordinate Cartesiane, si può fare

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

    Perché sqrt(random())?

    Andiamo a guardare la matematica che porta fino a sqrt(random()). Si supponga, per semplicità, che stiamo lavorando con il cerchio unitario, cioè R = 1.

    La distanza media tra i punti dovrebbe essere lo stesso indipendentemente da quanto lontano dal centro guardiamo. Questo significa, per esempio, che a guardare il perimetro di un cerchio di circonferenza 2 dovremmo trovare due volte come molti punti come il numero di punti sul perimetro di un cerchio di circonferenza 1.


                    Generare un punto casuale all'interno di un cerchio (in modo uniforme)

    Dato che la circonferenza di un cerchio (2πd) cresce linearmente con r, ne consegue che il numero di punti casuali dovrebbe crescere linearmente con r. In altre parole, il desiderato funzione di densità di probabilità (PDF) cresce linearmente. Dal momento che un PDF deve avere un’area pari a 1 e il raggio massimo è 1, abbiamo


                    Generare un punto casuale all'interno di un cerchio (in modo uniforme)

    In modo da sapere come la densità desiderata dei nostri valori casuali dovrebbe essere simile.
    Ora: Come facciamo a generare un valore casuale quando tutto ciò che abbiamo è un uniforme valore casuale tra 0 e 1?

    Usiamo un trucco chiamato antitrasformata di campionamento

    1. Dal PDF, creare il funzione di distribuzione cumulativa (CDF)
    2. Specchio di questo lungo y = x
    3. Applicare la funzione risultante di un valore uniforme tra 0 e 1.

    Sembra complicato? Mi permetta di inserire una casella gialla con un po ‘ di raccordo ferroviario che trasporta l’intuizione:

    Supponiamo di voler generare un punto casuale con la seguente distribuzione:

                    Generare un punto casuale all'interno di un cerchio (in modo uniforme)

    Che è

    • 1/5 dei punti in modo uniforme tra 1 e 2, e
    • 4/5 dei punti in modo uniforme tra il 2 e il 3.

    CDF è, come suggerisce il nome, la versione cumulativa del PDF. Intuitivamente: Mentre PDF(x) descrive il numero di valori casuali a x, CDF(x) descrive il numero di valori casuali meno di x.

    In questo caso il CDF è simile:

                    Generare un punto casuale all'interno di un cerchio (in modo uniforme)

    Per vedere come questo è utile, immagina di sparare proiettili da sinistra a destra uniformemente distribuito heights. Come i proiettili colpire il a discesa a terra:

                    Generare un punto casuale all'interno di un cerchio (in modo uniforme)

    Vedere come la densità dei punti sul terreno corrispondono alla nostra distribuzione desiderata! Ci siamo quasi!

    Il problema è che per questa funzione, il y asse è il uscita e il x asse è il ingresso. Possiamo solo “sparare proiettili da terra dritto”! Abbiamo bisogno di una funzione inversa!

    Questo è il motivo per cui abbiamo specchio il tutto; x diventa y e y diventa x:

                    Generare un punto casuale all'interno di un cerchio (in modo uniforme)

    Noi chiamiamo questo CDF-1. Per ottenere i valori secondo la distribuzione desiderata, usiamo CDF-1(random()).

    …quindi, la generazione casuale dei valori del raggio in cui il nostro PDF è uguale a 2x.

    Passaggio 1: Creare il CDF:

    Dato che stiamo lavorando con i reali, il CDF è espresso come parte integrante del PDF.

    CDF(x) = ∫ 2x = x2

    Passo 2: Specchio CDF lungo y = x:

    Matematicamente questo si riduce a scambio x e y e risoluzione dei problemi per y:

    CDF:     y = x2

    Swap:   x = y2

    Risolvere:   y = √x

    CDF-1:  y = √x

    Passo 3: Applicare la funzione risultante di un valore uniforme tra 0 e 1

    CDF-1(random()) = √random()

    Che è quello che ci proponiamo di ricavare 🙂

    • Questo algoritmo può essere utilizzato per generare in modo efficiente i punti sul ring.
    • Sul ring? Come con un raggio fisso? Non so se ho capito la tua domanda, ma se si dispone di un raggio fisso, è solo bisogno di randomizzare l’angolo.
    • Ho provato ad usare la semplice parola “Anello” invece di Anulus regione delimitata da due cerchi concentrici. In questo caso il rifiuto algoritmo diventa meno efficace e il primo algoritmo è difficile generalizzare. E il caso d’angolo con un raggio, inoltre, è coperto con il tuo algoritmo. Abbiamo sempre generare il raggio, come sqrt(casuale(min_radius^2, max_radius^2)) anche quando min_radius==max_radius.
    • Oh, bello! Per essere chiari, quando si dice random(min_radius², max_radius²), vuoi dire qualcosa di equivalente a random() * (max_radius² - min_radius²) + min_radius², dove random() restituisce un valore uniforme tra 0 e 1?
    • sì, questo è esattamente ciò che voglio dire: raggio = sqrt(casuale() * (max_radius2 – min_radius2) + min_radius2).
  3. 27

    Qui è una soluzione veloce e semplice.

    Scegliere due numeri casuali nell’intervallo (0, 1), cioè a e b. Se b < a, li scambia. Il punto è (b*R*cos(2*pi*a/b), b*R*sin(2*pi*a/b)).

    Si può pensare a questa soluzione come segue. Se hai preso il cerchio, tagliare, poi si raddrizzò fuori, si ottiene un triangolo retto. Scala triangolo in basso, e si avrebbe un triangolo da (0, 0) per (1, 0) per (1, 1) e di nuovo a (0, 0). Tutte queste trasformazioni cambiare la densità in modo uniforme. Quello che hai fatto è uniformemente scelto un punto casuale del triangolo invertito il processo per ottenere un punto nel cerchio.

    • Questo, per qualche motivo, mi dà molto più uniforme distribuzione di accettato la risposta, anche se io ho bisogno di dividere la coordinata dal raggio, altrimenti è all’interno di un cerchio di R^2
    • Grazie, questo è il codice in Java, forse qualcuno sarà utile: float random1 = MathUtils.random(); float random2 = MathUtils.random(); float randomXPoint = random2*raggioMathUtils.cos(MathUtils.PI2*random1/random2); float randomYPoint = random2*raggioMathUtils.peccato(MathUtils.PI2*random1/random2);
    • molto buona! Mi piace l’idea di più di probabilità per centralizzare i punti, e se non abbiamo swap quando b < a, si può raggiungere questo! ad esempio in javascript jsfiddle.net/b0sb5ogL/1
    • Penso che la tua soluzione è male. Non mi uniformemente risultati. Controllare questo screenshot prntscr.com/fizxgc
    • Inoltre ho controllato il codice e sembra che non uniforme. Si prega di controllare il mio grafico prntscr.com/fj0162 Ci sono troppi puntini vicino (0,0)
    • Non ho idea di quale codice è stato eseguito. Ma jsfiddle.net/7891b51f è la mia soluzione, come scritto da Guilherme, con uniform passato in modo che sarebbe. Eseguire più volte. Funziona benissimo.
    • Hai ragione. Ho risolto il mio codice. C’è una soluzione corretta in Java: double a = rand.nextDouble(); double b = rand.nextDouble(); if (b < a) { double temp = b; b = a; a = temp; } double newPointX = b * Math.cos(2 * Math.PI * a / b); doppio newPointY = b * Math.sin(2 * Math.PI * a / b);
    • Puoi spiegare un po ‘ di più su come tagliare il cerchio e raddrizzare fuori?

  4. 18

    Nota la densità è proporzionale all’inverso del quadrato del raggio, quindi invece di raccogliere r da [0, r_max], scegli tra [0, r_max^2], quindi calcolare le coordinate come:

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

    Questo vi darà uniforme distribuzione dei punti su un disco.

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

  5. 12

    Pensate in questo modo. Se si dispone di un rettangolo in cui un asse è il raggio e un angolo e si prende i punti all’interno di questo rettangolo che sono vicino a raggio 0. Tutti questi cadono molto vicino all’origine (che è sul cerchio). Tuttavia, i punti in prossimità di raggio R, tutti questi cadono vicino al bordo del cerchio (che è, distanti l’uno dall’altro).

    Questo potrebbe dare qualche idea del motivo per cui si stanno ottenendo questo comportamento.

    Il fattore che è derivato sul link che ti dice quanto corrispondente area del rettangolo deve essere adattata non dipende dal raggio, una volta mappato il cerchio.

    Edit: Così ciò che scrive nel link si condivide è, “è abbastanza facile fare il calcolo inverso della distribuzione cumulativa, e otteniamo r:”.

    La premessa di base è qui che è possibile creare una variabile con una distribuzione uniforme della mappatura l’uniforme la funzione inversa della funzione di distribuzione cumulativa di desiderata, funzione di densità di probabilità. Perché? Basta prendere per scontato, per ora, ma questo è un dato di fatto.

    Ecco il mio somehwat intuitiva spiegazione di matematica. La funzione di densità f(r) rispetto a r deve essere proporzionale a r stesso. La comprensione di questo fatto è parte di una qualsiasi base di calcolo i libri. Vedere le sezioni in area polare elementi. Alcuni altri manifesti hanno parlato di questo.

    Così chiameremo f(r) = C*r;

    Questa risulta essere la maggior parte del lavoro. Ora, dal momento che f(r) deve essere una densità di probabilità, si può facilmente vedere che, integrando f(r) sull’intervallo (0,R) si ha che C = 2/R^2 (questo è un esercizio per il lettore.

    Quindi, f(r) = 2*r/R^2

    OK, questo è come si ottiene la formula del collegamento.

    Poi, la parte finale è di andare uniforme variabile casuale u (0,1) è necessario mappare la funzione inversa della funzione di distribuzione cumulativa da questa densità desiderata f(r). Per capire perché questo è il caso, hai bisogno di trovare un avanzato probabilità di testo come Papoulis probabilmente (o derivare da soli.)

    Integrando f(r) F(r) = r^2/R^2

    A trovare la funzione inversa di questo si imposta u = r^2/R^2 e quindi risolvere per r, che ti dà r = R * sqrt(u)

    Questo rende totalmente intuire troppo, u = 0 dovrebbe mappa per r = 0. Inoltre, u = 1 dovrebbe mappa per r = R. Inoltre, si va definendo la funzione di radice quadrata, che ha un senso e confronta i link.

  6. 9

    Il motivo per cui l’ingenuo soluzione non funziona è che si dà una maggiore densità di probabilità per i punti più vicini al centro del cerchio. In altre parole il cerchio di raggio r/2 ha probabilità r/2 per ottenere un punto selezionato, ma si ha area (numero di punti) pi*r^2/4.

    Quindi vogliamo un raggio di densità di probabilità di avere la seguente struttura:

    La probabilità di scegliere un raggio minore o uguale a un dato r deve essere proporzionale all’area del cerchio di raggio r. (perché vogliamo avere una distribuzione uniforme dei punti e più grande significa più punti)

    In altre parole, vogliamo la probabilità di scegliere un raggio compreso tra [0,r] pari alla quota della superficie totale del cerchio. Totale area del cerchio è pi*R^2, e l’area del cerchio di raggio r è pi*r^2. Così vorremmo che la probabilità di scegliere un raggio compreso tra [0,r] per essere (pi*r^2)/(pi*R^2) = r^2/R^2.

    Ora arriva la matematica:

    La probabilità di scegliere un raggio compreso tra [0,r] è l’integrale di p(r) dr da 0 a r (solo perché ci aggiungi tutte le probabilità dei raggi più piccoli). Per questo vogliamo integrale(p(r)dr) = r^2/R^2. Possiamo chiaramente vedere che R^2 è una costante, quindi tutto quello che dobbiamo fare è capire che p(r), se integrato avrebbe dato qualcosa come r^2. La risposta è chiaramente r * costante. integrale(r * costante dr) = r^2/2 * costante. Questo deve essere uguale a r^2/R^2, quindi costante = 2/R^2. Così si ha la distribuzione di probabilità p(r) = r * 2/R^2

    Nota: un Altro modo più intuitivo pensare al problema è quello di immaginare che si sta cercando di dare a ogni cerchio di raggio r di una densità di probabilità pari alla proporzione del numero di punti che ha sulla sua circonferenza. Così un cerchio di raggio r 2 * pi * r “punti” sulla sua circonferenza. Il numero totale di punti è pi * R^2. Così si dovrebbe dare il cerchio r una probabilità pari a (2 * pi * r) /(pi * R^2) = 2 * r/R^2. Questo è molto più facile da capire e più intuitivo, ma non è così matematicamente.

  7. 7

    In realtà dipende da cosa si intende per ‘uniformemente casuale”. Questo è un sottile punto e si può leggere di più sulla pagina wiki qui: http://en.wikipedia.org/wiki/Bertrand_paradox_%28probability%29, dove lo stesso problema, dando interpretazioni diverse a ‘uniformemente casuale’ dà risposte diverse!

    A seconda di come si sceglie i punti, la distribuzione può variare, anche se sono uniformemente casuale in alcuni senso.

    Sembra che il blog è di cercare di rendere uniforme casuale nel senso seguente: Se si tratta di un sub-cerchio del cerchio, con lo stesso centro, quindi la probabilità che il punto cade in quella regione è proporzionale all’area della regione. Che, credo, è il tentativo di seguire l’ora standard interpretazione di ‘uniformemente casuale’ per il 2D regioni con aree definite su di loro: probabilità che un punto di cadere in qualche regione (con zona ben definito) è proporzionale alla superficie di quella regione.

    • O meglio, la probabilità che il punto cade in qualsiasi arbitrario regione è proporzionale all’area della regione — supponendo che la regione ha una superficie.
    • Corretto, che è quello che volevo intendere, la mia affermazione tra parentesi. Io renderlo più chiaro, grazie. btw, sul blog, non c’era nessuna prova reale che arbitraria aree di danno proporzionale probabilità, quindi ho scelto la frase in questo modo.
  8. 7

    Lasciate che ρ (raggio) e φ (azimut) di due variabili casuali corrispondenti alle coordinate polari di un punto arbitrario all’interno del cerchio. Se i punti sono distribuiti uniformemente in che cosa consiste il disribution funzione di r e f?

    Per ogni r: 0 < r < R la probabilità di raggio di coordinate ρ meno allora r è

    P[ρ < r] = P[punto è all’interno di un cerchio di raggio r] = S1 /S0 =(r/R)2

    Dove S1 e S0 sono le aree di cerchio di raggio r e R rispettivamente.
    Così il CDF può essere determinato come:

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

    E PDF:

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

    Nota che per R=1 variabile casuale sqrt(X), dove X è uniforme su [0, 1) è esattamente la CDF (perché P[sqrt(X) < y] = P[x < y**2] = y**2 per 0 < a <= 1).

    La distribuzione di φ è ovviamente uniforme da 0 a 2*π. Ora è possibile creare casuale coordinate polari e convertirli Cartesiano utilizzando le equazioni trigonometriche:

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

    Non può resistere a postare il codice python per 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)
    

    Vi saranno mostrati

    Generare un punto casuale all'interno di un cerchio (in modo uniforme)

  9. 6

    Ecco il mio codice Python per generare num punti casuali da un cerchio di raggio 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()
    • Perché non r = np.sqrt(np.random.uniform(0.0, rad**2, num))?
  10. 4

    Credo che in questo caso usando le coordinate polari è un modo per complicare il problema, sarebbe molto più facile se si sceglie punti casuali in un quadrato con lati di lunghezza 2R e quindi selezionare i punti (x,y) tale che x^2+y^2<=R^2.

    • Vuoi dire che x^2+y^2<=R^2 credo.
    • sì, certo..
    • Questo è il rifiuto di campionamento. Ok, ma ciò significa che il tempo di calcolo varia un po’, che potrebbe essere un problema.
    • Tutte le piazze sono su 4 lati.
    • Questo algoritmo è più efficiente che tutto ciò che riguarda le radici quadrate o sin/cos calcoli. Si rifiuta di meno che il 21,5% dei punti della piazza.
  11. 3

    Soluzione in Java e la distribuzione di esempio (2000 punti)

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

    Generare un punto casuale all'interno di un cerchio (in modo uniforme)

    basato sul precedente soluzione https://stackoverflow.com/a/5838055/5224246 da @sigfpe

  12. 2

    Prima siamo in grado di generare un cdf[x] che è

    La probabilità che un punto è a meno di una distanza x dal centro del cerchio. Si supponga che il cerchio ha un raggio di R.

    ovviamente se x è uguale a zero, allora cdf[0] = 0

    ovviamente se x è R, allora il cdf[R] = 1

    ovviamente se x = r, allora il cdf[r] = (Pi r^2)/(Pi R^2)

    Questo perché ogni “piccola area” il cerchio ha la stessa probabilità di essere scelto, in Modo che la probabilità è proporzionale all’area in questione. E la superficie di una distanza x dal centro del cerchio è Pi r^2

    così cdf[x] = x^2/R^2, perché la Pi annullano a vicenda

    abbiamo cdf[x]=x^2/R^2 dove x va da 0 a R

    Così siamo in grado di risolvere per x

    R^2 cdf[x] = x^2
    
    x = R Sqrt[ cdf[x] ]
    

    Possiamo ora sostituire il cdf con un numero casuale da 0 a 1

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

    Infine

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

    otteniamo le coordinate polari
    {0.601168 R, 311.915 deg}

  13. 1

    C’è una relazione lineare tra il raggio e il numero di punti “vicino” che il raggio, quindi ha bisogno di utilizzare un raggio di distribuzione che è anche il numero di punti di dati, vicino a un raggio r proporzionale alla r.

  14. 1

    Ho usato una volta questo metodo:
    Questo può essere totalmente non ottimizzata (vale a dire che utilizza un array di punto, quindi, la sua inutilizzabile per grandi cerchi), ma dà distribuzione casuale abbastanza. Si può saltare la creazione della matrice e disegnare direttamente se si desidera. Il metodo per rendere tutti i punti in un rettangolo che si trovano all’interno del cerchio.

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

    Generare un punto casuale all'interno di un cerchio (in modo uniforme)

    • Le distribuzioni non sono “abbastanza casuale”. Essi sono o non casuale per una determinata definizione di caso. La tua risposta è obliquo: non commento il tuo codice, né spiegare come si arriva a questo. Oblique risposte sono difficili da seguire e di più per la fiducia.
  15. 1

    L’elemento di area in un cerchio è dA=rdr*dphi. Extra factor r distrutto la tua idea di scegliere a caso un r e phi. Mentre phi è distribuito piatto, r non è, ma piatto in 1/r (cioè è più probabile che a colpire il limite di “occhio di bue”).

    In modo da generare punti uniformemente distribuiti sulla circonferenza pick phi da una tv distribuzione e r 1/r di distribuzione.

    In alternativa, utilizzare il metodo Monte Carlo proposto da Mehrdad.

    MODIFICA

    Scegliere un casuale r appartamento in 1/r, si potrebbe scegliere una casuale x l’intervallo [1/R, infinity] e calcolare r=1/x. r viene poi distribuito appartamento in 1/r.

    Per calcolare casuale phi scegliere un casuale x l’intervallo [0, 1] e calcolare phi=2*pi*x.

    • Esattamente come faccio a scegliere un d da “1/r di distribuzione”?
    • aioobe, ho aggiornato la mia risposta.
  16. 0

    Non so se questa domanda è ancora aperta per una soluzione nuova, con le risposte già date, ma mi è capitato di avere di fronte esattamente la stessa domanda me la faccio. Ho provato a “ragionare” con me stesso per una soluzione, e ho trovato uno. Potrebbe essere la stessa cosa, come alcuni hanno già suggerito qui, ma in ogni caso qui è:

    in ordine per due elementi del cerchio in superficie per essere uguale, a parità di dottor, dobbiamo avere dtheta1/dtheta2 = r2/r1. Scrivere l’espressione della probabilità che l’elemento di P(r, theta) = P{ r1< r< r1 + dr, theta1< theta< theta + dtheta1} = f(r,theta)*dr*dtheta1, e impostando le due probabilità (r1 e r2) pari, si arriva a (supponendo che r e theta sono indipendenti) f(r1)/r1 = f(r2)/r2 = costante, che dà f(r) = c*r. E il resto, determinare la costante c segue la condizione f(r) essendo un PDF.

    • Interessante approccio per iniziare con dtheta1/dtheta2 = r2/r1. Puoi spiegarti meglio come è nata questa equazione?
    • Come altri hanno detto (clacson, per esempio), un differenziale della superficie di un cerchio è dato come rdrdtheta, quindi, se assumiamo che r1 = r2, allora avremo dr1*dtheta1 = dr2*dtheta2 e il resto segue.
  17. 0

    Un programmatore soluzione:

    • Creare una mappa di bit (una matrice di valori booleani). Può essere grande come si desidera.
    • Disegnare un cerchio in che mappa di bit.
    • Creare una tabella di ricerca del cerchio punti.
    • Selezionare casualmente un indice nella tabella di ricerca.
    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];
    } //()

    La bitmap è necessaria solo per la spiegazione della logica. Questo è il codice senza la bitmap:

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

    Ancora non sono sicuro circa l’esatta ‘(2/R2)×r’, ma quello che è evidente è il numero di punti necessari per essere distribuito in data unità ‘dr’, ovvero aumento di r sarà proporzionale a r2 e non r.

    controllare questo modo…numero di punti in qualche angolo theta e tra r (0,1 r a 0,2 r), cioè la frazione di r ed il numero di punti tra r (0.6 r a 0,7 r) sarebbe uguale se si utilizza standard generazione, dal momento che la differenza è solo 0,1 r tra due intervalli. ma dal momento che l’area coperta tra i punti (0.6 r a 0,7 r) sarà molto più grande area coperta tra 0,1 r a 0,2 r, parità di numero di punti sarà scarsamente distanziati in un’area più grande, questo suppongo che tu già conosci, in Modo che la funzione per generare i punti casuali non deve essere lineare ma quadratica, (dal momento che il numero di punti necessari per essere distribuito in data unità ‘dr’, ovvero aumento di r sarà proporzionale a r2 e non r), quindi, in questo caso sarà inversa quadratica, dal momento che il delta che abbiamo (0,1 r) in entrambi gli intervalli di piazza di qualche funzione in modo che possa agire come valore di inizializzazione per lineare generazione di punti (dal postfazioni, questo seme è usato in modo lineare in il peccato e la funzione cos), così ci conosciamo, dr deve essere quadratica valore e per fare questo seme quadratica, abbiamo bisogno di di origine di questo valori dalla radice quadrata di r non r stesso, spero che questo rende un po ‘ più chiaro.

    • Sei stato il primo a riferimento teorema di Pitagora qui. Mi piacerebbe se si potesse espandere questo con una figura o due, per sostenere la tua spiegazione. Ho un momento difficile dopo, come è ora 🙁
    • Ho provato a riformulare la risposta, posso aggiungere diagrammi, se necessario:)
    • Ho capito perché non riesco a stenderlo in modo lineare. Quello che non capisco è qui il collegamento di Pitagora o di sin/cos. Forse schemi mi può aiutare qui.
    • Pitagora è il mio errore, si prega di non pensarci, ma la speranza è capito quadratica natura della funzione, l’esatta (2/R2)×r esigenze di prova e non riesco a venire con qualsiasi prova per questo
  19. 0

    Ad un problema divertente.

    La logica della probabilità di un punto scelto abbassamento distanza dall’asse origine aumenta è spiegato più volte sopra. Ci conto per che facendo la radice di U[0,1].
    Ecco una soluzione generale di un positivo r in Python 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])
    

    Generare un punto casuale all'interno di un cerchio (in modo uniforme)

  20. 0

    Si può anche usare il vostro intuito.

    L’area di un cerchio è pi*r^2

    Per r=1

    Questo ci darà un’area di pi. Supponiamo di avere un qualche tipo di funzione fche sarebbe uniformemente distrubute N=10 punti all’interno di un cerchio. Il rapporto qui è 10 /pi

    Ora abbiamo il doppio dell’area e il numero di punti

    Per r=2 e N=20

    Questo dà un’area di 4pi e il rapporto è ora 20/4pi o 10/2pi. Il rapporto sarà sempre più piccoli e più piccoli, il più grande è il raggio di curvatura è, perché la sua crescita è di secondo grado e la N scala linearmente.

    Per risolvere questo possiamo solo dire

    x = r^2
    sqrt(x) = r
    

    Se vuoi generare un vettore in coordinate polari come questo

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

    Più punti che si terra intorno al centro.

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

    length non è uniformemente distribuito in più, ma il vettore sarà ora distribuito uniformemente.

  21. -1

    1) Scegliere un casuale X compreso tra -1 e 1.

    var X:Number = Math.random() * 2 - 1;
    

    2) Utilizzando il cerchio formula, calcolare il massimo e il minimo dei valori di Y dato X e raggio di 1:

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

    3) Scegliere un casuale Y tra questi estremi:

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

    4) Incorporare la vostra posizione e i valori del raggio nel valore finale:

    var finalX:Number = X * radius + pos.x;
    var finalY:Number = Y * radois + pos.y;
    
    • Non uniforme – la probabilità per [-1, 0] è molto più alto rispetto a [0, 0], dato che p([-1, Y]) = p([0, Y]), e c’è una sola scelta per [-1, Y] e molti scelte per [0, Y].
    • Questa soluzione favorisce punti verso i lati sinistro e destro del cerchio. Punti con x vicino a zero sono sotto-rappresentate. Non una distribuzione uniforme a tutti.

Lascia un commento