Créer un vecteur aléatoire

**Rafy** · 25/06/2006, 20h39

La génération de nombre aléatoire est un sujet assez vaste, les utilisations nombreuses. Je souhaiterais créer un vecteur (3D) aléatoire :

Il est possible de choisir chaque coordonnées de manière aléatoire, par exemple choisir chaque coordonnées entre -1 et 1, de générer un vecteur avec ces coordonnées.

Ceci apportent quelques problèmes :
-> Il est possible de tomber sur le vecteur nul (ce qui n'est pas un problème en soit), mais par la suite si on désir un vecteur de norme, 1 aléatoire, alors notre modé de génération nous retourne un vecteur que l'on ne pourra pas normaliser.
-> Le vecteur ainsi généré n'est pas choisi de manière uniforme dans le volume possible, je m'explique. Ce n'est pas parcequ'on choisi aléatoirement uniformément les coodronnées qu'elles ne vont pas donner une répartition des vecteurs générés aléatoire et uniforme...
La preuve dans le cas décrit au dessus, on constate une répartition non uniforme dans l'espace; on peut distinguer une forte concentration au centre et sur 4 axes qui sont les bisectrices des sommets des tétraèdres formés par les axes sur lesquels ont à choisi les coordonnées aléàtoirement.... (Je ne sais pas si j'ai pas perdu du monde en route la

)
Pour faire clair, dans le plan (en 2D) on aurai une forte concentration des vecteurs généré sur deux axes : la première bisectrice, et sa perpendiculaire passant par l'origine du repère...

Ma question :
Comment serai-t-il possible de générer de manière simple et rapide des vecteurs aléàtoires sans ces effets néfastes

j'insiste sur simple et rapide car je présens une certaine dérive possible.
Il faut se dire que cette génération va être appelée dans un jeu, jusqu'à 10000 par frame, donc pas de truc dans le genre trucs de fou.... merci d'avance

**Graffito** · 25/06/2006, 20h49

Bonjour,

En 2D les coordonnées polaires résolvent le problème. En 3D aussi, je pense.

**Rafy** · 25/06/2006, 20h53

Ben en fait non car ça fait toujours une concentration autour de l'origine...
Alors j'avais pensé faire un choix non linéaire du rayon, c'est à dire non pas choisir un nombre pour le rayon de manière equiprobable, mais plutôt logarithmique de manière à éloingner les possibilités de choix au centre mais c'est lourd à mettre en place car il faut que je fasse une fonction rand non linéaire, donc pour faire un truc jolie une fonction rand à laquelle on peut passer une fonction de répartition....

**Matthieu Brucher** · 26/06/2006, 09h02

Si le générateur aléatoire a une dimensionalité supérieure à 3, c'est bon non ?
En fait, je pense aux générateurs qui peuvent générer n dimensions statistiquement indépendantes comme les MT19937 par exemple.

**Médiat** · 26/06/2006, 09h43

Envoyé par Rafy

Ben en fait non car ça fait toujours une concentration autour de l'origine...
Alors j'avais pensé faire un choix non linéaire du rayon

Tu peux faire quelque chose de très très simple
R = rayon maximum,
Rand une fonction qui te ramène un nombre entre 0 et 1
r = rayon trouvé :

r = R * Racine n-ième(Rand)

A toi de déterminer la bonne valeur de n...

**FrancisSourd** · 26/06/2006, 09h54

Je me souviens de cette discussion:

http://www.developpez.net/forums/showthread.php?t=78786

**ToTo13** · 26/06/2006, 10h05

Bonjour,

il est possible de faire des tirages aléatoires avec la fonction du langage que tu utilises, puis de passer ces nombres dans des algos utilisant des fonction XOR. Ceci est fait en cryptographie.

**Rafy** · 26/06/2006, 17h00

Envoyé par Miles

Si le générateur aléatoire a une dimensionalité supérieure à 3, c'est bon non ?
En fait, je pense aux générateurs qui peuvent générer n dimensions statistiquement indépendantes comme les MT19937 par exemple.

Je ne connais pas les MT19937, mais ce que je sais c'est que choisir aléatoirement uniformément suivant 3 axes ne va pas donner un choix aléaoitre uniforme en combinant les directions...

**Matthieu Brucher** · 26/06/2006, 17h02

Avec un MT19937 oui, tu peux même aller au-delà de 600 dimensions à ton parallélépipère dans lequel tu tires tes points, et la répartitition sera toujours encore uniforme dans le volume.
Maintenant, si pour toi, le but est de générer aléatoirement dans une sphère, c'est un autre problème

**Rafy** · 26/06/2006, 17h02

Envoyé par Médiat

Tu peux faire quelque chose de très très simple
R = rayon maximum,
Rand une fonction qui te ramène un nombre entre 0 et 1
r = rayon trouvé :

r = R * Racine n-ième(Rand)

A toi de déterminer la bonne valeur de n...

Ouais j'avais pensé utiliser le sinus ou le cosinus pour me créer une non uniformité dans le choix pour le rayon....
Racine sera plus rapide mais provoquera surement des trucs étrange en 0 du fait de la tangeante nul : il va y avoir un effet de fuite du centre, et je pense que ça va faire l'effet inverse : je n'aurais plus rien au milieu.... A voir il faut tester...
Mais je ne sais pas comment faire pour générer un veteur aléatoire dans l'espace... Car le coup des coordonnées polaire dans le plan peuvent peut-être palier au problème d'effet de "croix", mais dans l'espace, il faut que je choisisse 2 angles, et un rayon, et je pense que je vais encore avoir un problème avec ces 2 angles... Il vas y avoir un autre effet de bord.
Et puis il va y avoir des projections à faire pour revenir en coordonnées cartésiennes, c'est à dire plein de sinus et de cosinus, et ça c'est pas très cool, car c'est pas rapide... (je rapelle : jusqu'a 10000 fois par frame) Ca risque de piquer.

**Rafy** · 26/06/2006, 17h10

Envoyé par Miles

Avec un MT19937 oui, tu peux même aller au-delà de 600 dimensions à ton parallélépipère dans lequel tu tires tes points, et la répartitition sera toujours encore uniforme dans le volume.
Maintenant, si pour toi, le but est de générer aléatoirement dans une sphère, c'est un autre problème

Si j'arrive à avoir un vecteur de norme 1 aléatoire, c'est bon. Donc on peut dire que oui, c'est dans une sphere... Mais le coup de passer d'un cube à une sphere c'est juste une question de normalisation...

**Rafy** · 26/06/2006, 17h13

Envoyé par ToTo13

Bonjour,

il est possible de faire des tirages aléatoires avec la fonction du langage que tu utilises, puis de passer ces nombres dans des algos utilisant des fonction XOR. Ceci est fait en cryptographie.

Je travail en C++.
Mais si je dois faire des XOR, il faut que je stocke tout les vecteurs que je génère, non ? Et si j'en créé 10000 par frame, je vais saturer la mémoire rapidement

Ou alors je n'ai pas compris la méthode.

**Rafy** · 26/06/2006, 17h16

Envoyé par FrancisSourd

Je me souviens de cette discussion:

http://www.developpez.net/forums/showthread.php?t=78786

Je viens de lire le post. Ca veut dire qu'au lieu de choisir mes coordonnées entre -1 et 1, si je les choisi entre -inf et +inf, alors je vais minimiser la concentration sur les diagonales du cube englobant ????

**Matthieu Brucher** · 26/06/2006, 17h40

Envoyé par Rafy

Si j'arrive à avoir un vecteur de norme 1 aléatoire, c'est bon. Donc on peut dire que oui, c'est dans une sphere... Mais le coup de passer d'un cube à une sphere c'est juste une question de normalisation...

Dans ce cas, tu prends un générateur aléatoire de dimension suffisante, et c'est bon.

**Rafy** · 26/06/2006, 17h46

Hum, oui et le MT19937, c'en est un ???
Et le truc que j'ai posté juste avant, c'est bon aussi ou pas ????

**Matthieu Brucher** · 26/06/2006, 17h48

Le MT19937, c'est un générateur de Mersenne-Twister utilisant un nombre de Mersenne avec n=19937. C'est générateur de haute dimension, comme indiqué précédemment. Normalement, tu ne devrais pas avoir de pb avec un tel générateur vu ses capacités - contrairement aux générateurs à congruence linéaire

-

**Rafy** · 26/06/2006, 17h57

Je suis en train de regarder ça, sur http://miles.developpez.com/tutoriels/cpp/boost/random/

Je ne sais pas trop ce que c'est que la "vitesse approximative", plus le nombre est petit, et plus c'est rapide ?

**Matthieu Brucher** · 26/06/2006, 18h00

Oui, c'est ça. C'est en fait la vitesse indicative donnée par Boost, je ne sais donc pas exactement à quoi elle correspond

**Rafy** · 26/06/2006, 18h08

Si je créé un vecteur avec comme coordonnées, 3 nombres que je viens de générer avec MT19937, je n'aurai plus de problème d'effet de "croix" ????
Je vais vérifier ça.
Je vais essayer au par avant je vais voir si en changeant ma méthode courante (au lieu de prendre les nombre entre -1 et 1, de les prendre entre -inf et +inf) j'obtiens quelquechose, ça ne me ferrai pas trop de changement.
Sinon ben je vais me lancer dans le MT19937

Merci à tous pour vos réponses.
Je ne metterai le tag résolu que quand j'aurai réussi à avoir ma répartition uniforme.....