[Java] Random e distribuzione uniforme

[Lim]

Sto cercando di implementare un algoritmo che generi casualmente N oggetti da distribuire uniformemente sulla superficie di una sfera.
Ho pensato che lavorare con le coordinate sferiche sarebbe stata la scelta migliore (r, fi, theta).
L'idea, quindi, è quella di generare randomicamente gli angoli fi e theta per ogni oggetto, poi attraverso il raggio della sfera, posiziono l'oggetto sulla superficie.
Utilizzo i metodi della classe Random di Java, ho testato la generazione degli angoli verificando che hanno una distribuzione grosso modo uniforme.
Però al momento di utilizzare realmente il metodo per collocare gli oggetti sulla sfera, vedo (visualizzo il la sfera in 3D) che c'è una concentrazione maggiore di oggetti lungo l'asse Z. Non riesco a capire come mai :muro:

Incollo qui sotto il codice utilizzato:


Random rand=new Random();
float theta=0;
float fi=0;
double max=Math.PI;
double min=0;

for (int i=0;i<n;i++){

fi=(float) Math.atan2(rand.nextGaussian(),rand.nextGaussian());

theta= (float) (rand.nextFloat()*(max-min)+min);
}



L'angolo fi varia tra -PI e +PI, mentre theta tra 0 e PI.
Per un approfondimento sulle coordinate sferiche rimando qui (http://it.wikipedia.org/wiki/Sistema_di_riferimento#Il_sistema_sferico).

La verifica che ho fatto per valutare se la generazione di fi e theta fosse realmente uniforme è consistita nel popolare un array di 360 elementi per fi e 180 elementi per theta. Ho convertito gli angoli generati in GRADI e poi in INT e per ogni occorrenza di un certo angolo (intero) sono andato ad incrementare il corrispondente elemento nell'array. Ho importato gli elementi dell'array in un foglio di calcolo esterno ed ho creato un grafico. In effetti entrambi gli angoli hanno distribuzione uniforme.
Certo, la verifica l'ho fatta con angoli interi ed in gradi, ma in radianti (double) non credo proprio che ci siano differenze, o sbaglio?

Chiedo aiuto per capire cosa c'è che non va nel mio ragionamento e per trovare insieme eventuali soluzioni alternative...

Grazie in anticipo!!! :D

[banryu79]

Scusa, una curiosità: perchè per fi usi nextGaussian e per theta ti basta nextFloat? Lo chiedo da ignorante, non perchè penso sia quello il tuo problema.

EDIT:
Occhio che sono ignorante forte, quindi potrei puntare il dito su cavolate.

L'angolo fi varia tra -PI e +PI, mentre theta tra 0 e PI.

Dato che PI vale 180° così abbiamo che ogni "fi" generato è nel range [-180°, 180°] mentre ogni "theta" generato è nel range [0°, 180°].
Ma "theta" non dovrebbe essere anche lui compreso nel range [-180° 180°]?

Lo chiedo perchè:

... Ho importato gli elementi dell'array in un foglio di calcolo esterno ed ho creato un grafico. In effetti entrambi gli angoli hanno distribuzione uniforme.

Che la distribuzione dei 360 valori e dei 180 valori pseudorandom generati da java.util.Random fosse abbastanza uniforme è pacifico.

[tuccio`]

theta= (float) (rand.nextFloat()*(max-min)+min);
mentre theta tra 0 e PI.? :E

[Lim]

Scusa, una curiosità: perchè per fi usi nextGaussian e per theta ti basta nextFloat? Lo chiedo da ignorante, non perchè penso sia quello il tuo problema.

Inizialmente generavo fi allo stesso modo di theta, cambiando soltanto il max e min nella formula. Avevo comunque lo stesso problema, concentrazione troppo elevata intorno all'asse Z. Ho deciso allora di cambiare approccio, sfruttando la funzione Math.atan2(y,x), che calcola l'arco tangente del rapporto delle due coordinate, effettuando anche i controlli se uno dei due o entrambi sono uguali a 0.

Utilizzando nextFloat in atan2, non si ottiene una distribuzione uniforme. Sono andato un pò a tentativi all'inizio...

[Lim]

? :E

Mi sono sbagliato? Pensi che sia qui l'errore?

[Lim]

Dato che PI vale 180° così abbiamo che ogni "fi" generato è nel range [-180°, 180°] mentre ogni "theta" generato è nel range [0°, 180°].
Ma "theta" non dovrebbe essere anche lui compreso nel range [-180° 180°]?



Beh, in realtà le coordinate sferiche vincolano theta compreso tra 0 e 180, guarda il link che ho messo... Dal grafico capirai al volo che teoricamente è corretto...



Che la distribuzione dei 360 valori e dei 180 valori pseudorandom generati da java.util.Random fosse abbastanza uniforme è pacifico.


Beh, si. Pensavo anche io di potermi appoggiare a questa cosa, ma il risultato non lo è, forse combinando insieme i due angoli non si ottiene + la uniformità, ma non capisco molto perchè... (che dipenda proprio dai vincoli imposti su theta?) :doh:

[tuccio`]

Mi sono sbagliato? Pensi che sia qui l'errore?
ah no, ricordavo male, nextFloat ritorna numeri tra 0 e 1 quindi niente (e comunque la cosa non giustificava comunque la distribuzione sull'asse z)

[Caldwell83]

Dai miei vaghi ricordi di statistica la distribuzione gaussiana non è uniforme, ma è piu' concentrata al centro. Se cerchi "Gaussiana" in google images troverai il grafico della distribuzione.

Per avere una distribuzione uniforme devi utilizzare nextFloat() o nextDouble, che si restituisce un numero fra 0 e 1, ma se tu lo moltiplichi per il valore massimo ti trovi il numero random che ti serve, oppure puoi utilizzare nextInt(valoreMax) che ti restituisce un intero compreso tra 0 e valoreMax -1.

[Lim]

Dai miei vaghi ricordi di statistica la distribuzione gaussiana non è uniforme, ma è piu' concentrata al centro. Se cerchi "Gaussiana" in google images troverai il grafico della distribuzione.

Per avere una distribuzione uniforme devi utilizzare nextFloat() o nextDouble, che si restituisce un numero fra 0 e 1, ma se tu lo moltiplichi per il valore massimo ti trovi il numero random che ti serve, oppure puoi utilizzare nextInt(valoreMax) che ti restituisce un intero compreso tra 0 e valoreMax -1.


Vero, è la classica campana rovesciata, media=0 e varianza=1.
Dai tentativi fatti ho visto che la Gaussiana si comporta meglio di nextFloat.
Inoltre non uso la gaussiana per generare l'angolo, ma la uso per generare le coordinate x ed y che vanno ad alimentare la funzione Math.atan2(y,x).
In pratica, questa funzione, partendo dalle coordinate rettangolari, calcola l'arco tangente di (y/x), restituendo fi. Usando questo approccio, ottengo risultati migliori rispetto a quando genero x ed y con nextFloat.

Comunque, è lo stesso risultato che ottengo con
(r.nextFloat()*(max-min)+min), ho provato a cambiare solo per vedere se risolvevo l'anomalia sull'asse Z.

[Caldwell83]

Fai questa prova:
Genera entrambi gli angoli nello stesso modo, senza passare dall'arcotangente.

[Lim]

Fai questa prova:
Genera entrambi gli angoli nello stesso modo, senza passare dall'arcotangente.

Già fatta come prova, stessa formula (tranne che per l'estremo superiore del calcolo).
Sull'asse Z la densità è più alta. Non so proprio dove sbaglio, forse è la combinazione dei due angoli che genera una densità maggiore?

In teoria, se la concentrazione è più alta intorno a Z, sembrerebbe che theta assuma con più frequenza valori prossimi a 0 e a 180°, mentre per fi è indifferente...

[banryu79]

edit.

[yorkeiser]

Potrei essere arrugginito (anzi lo sono), ma non mi risulta che in coordinate sferiche i due angoli siano indipendenti, come tu stai assumendo calcolando randomicamente il secondo.
Ci sono precise relazioni che legano i due angoli e il raggio, e sono date appunto dalle formule che hai linkato su wikipedia.

[Lim]

Potrei essere arrugginito (anzi lo sono), ma non mi risulta che in coordinate sferiche i due angoli siano indipendenti, come tu stai assumendo calcolando randomicamente il secondo.
Ci sono precise relazioni che legano i due angoli e il raggio, e sono date appunto dalle formule che hai linkato su wikipedia.

HO RISOLTO!!! :D

Allora, come dici te in coordinate sferiche i due angoli non sono indipendenti, ma per la mia applicazione, in cui voglio posizionare a caso in coordinate sferiche, l'approccio andrebbe anche bene. Nel senso, mi genero un fi, mi genero un theta e poi tramite il raggio, trovo la collocazione nello spazio sferico.
Le formule di wikipedia sono semplici e chiare su questo punto.

Tornando al mio problema, quello che volevo fare era distribuire uniformemente oggetti sulla superficie di una sfera (immaginiamo la Terra). La procedura non è banale, in quanto la densità tende ad aumentare mano a mano che ci si allontana dal cerchio di raggio massimo (equatore).

Questo perché, anche se l'algoritmo genera in modo uniforme gli angoli fi e theta, andando a collocare gli oggetti nei pressi dei poli, essi saranno inevitabilmente + densi! (i paralleli sono via via più piccoli).
Quindi NON devo generare in modo uniforme gli angoli fi e theta, ma devo tenere in considerazione il fatto che mi sto allontanando dall'equatore.

Dopo una lunga ricerca ho trovato le seguenti formule:

fi= 2 * pigreco * rand1
theta= arccos(2 * rand2 -1)

con rand1 e rand2 numeri aleatori compresi tra 0 e 1.



http://mathworld.wolfram.com/images/eps-gif/SphericalDistribution_900.gif


Ringrazio tutti per il supporto e cito la fonte (http://mathworld.wolfram.com/SpherePointPicking.html) :read: per chi volesse approfondire l'argomento.


P.S. Tanto per fare chiarezza, nella fonte citata fi e theta sono invertiti. Credo che sia più "corretto" indicarli come ho fatto io, inoltre concordano con Wikipedia...