Génération de points "semi" aléatoire

[invited38b5b91]

Bonjour,

J'ai un petit problème d'algorithmie qui pose problème au niveau mathématique.
Le principe de l'algorithme est de générer des couples longitudes/lattitudes aléatoire autour de la position de l'utilisateur (Ca j'y arrive avec les formules trigonométriques).
Mais l'utilisateur peut bouger et alors il faut générer de nouveaux points à l'extérieur du périmètre initial mais à l'intérieur du nouveau périmètre. De la même façon si l'utilisateur revient à son point initial il faut que les points soit identiques à ceux du départ.

J'ai mis un petit schéma pour que ça soit plus clair.

• Le cercle rouge représente le périmètre initial ou j'ai généré 50 points aléatoirement.
• L'utilisateur se déplace (cercle vert) et là j'aimerais être capable de générer 50 nouveaux points en gardant les points concurrence tout en générant de nouveaux points dans le cercle vert et hors du cercle rouge.

Donc ma question c'est existe t-il une formule qui permet de générer XX points dans un cercle mais qui conserve la position des points si l'on change le centre du cercle ?

Si je n'ai pas été super clair précisez le moi. J'ai placé ce sujet en Mathématiques parceque je pense que c'est plus un problème de Math plutôt que d'Informatique. (si je me trombe dites le moi)
-----

[danyvio]

J'ai peut-être mal compris l'ampleur du problème, mais cela semble être un "simple" problème de mémorisation de l'ensemble des points à une étape donnée.
D'autre part, je pose la question : le retour au statu quo ante est-il valable lors d'un simple aller-retour , ou faut-il prévoir le retour au point initial après x déplacements ? Auquel cas il faut historiser tout...

[invited38b5b91]

La mémorisation n'est pas viable parceque la mémoire de l'application est limitée.
Le retour au point initial peut se faire au bout de X déplacements et de manière non linéaire.
Petit détail j'ai gardé en mémoire les 100 valeurs aléatoires (50 rayons aléatoires et 50 angles aléatoires) qui ont permis de créer les points initiaux.

Donc pour le point initial aléatoire
O = Centre du premier cercle
r = rayon aléatoire (gardé en mémoire)
a = angle (compris entre 0 et 2PI)
x1 = Ox + r * cos(a)
y1 = Oy + r * sin(a)

Donc je décale le cercle
O'x = Ox + decalx
O'y = Oy + decaly

Et c'est là que ça bloque, je cherche à savoir si il y a une formule qui placerait le point au même endroit si le point reste dans le cercle et qui le place ailleurs sinon (j'avais pensé à faire une sorte d'inversion mais ça s'avère foireux).
Et le cercle bouge de manière non linéaire. La relation peut se faire par rapport au positionnement précédent ou par rapport au positionnement initial si une relation existe.

[inviteccac9361]

Bonjour,

Si je n'ai pas été super clair précisez le moi. J'ai placé ce sujet en Mathématiques parceque je pense que c'est plus un problème de Math plutôt que d'Informatique. (si je me trombe dites le moi)

Je pense qu'il s'agit plutot d'un probleme informatique.
La generation semi-aleatoire peut être obtenu par une fonction de type rand, rnd etc, selon le langage.
(au lieu de la mémorisation des 100 points initiaux, ce qui ne fonctionera pas je pense)

Le principe de cette fonction est qu'elle est initialisée avec une valeur de départ.
Par exemple randomize(50)
Ensuite à chaque lancement de rnd, l'occurence suivante de la suite (puisqu'il s'agit en réalité d'une suite donnant des nombres "aleatoires") est fournie.

Donc, si on initialise la fonction aleatoire avec 50, le prochain chiffre fourni sera toujours le même, le second aussi etc.
Ceci évite de mémoriser une longue suite de valeurs,
mais implique de la parcourir dans l'ordre (lancer n fois tres exactement la fonction, sans évidement réutiliser cette fonction à d'autres fins pendant ce laps de temps)
pour avoir une valeur au nieme indice.

Moralité, ce que tu gagnes en memoire, tu le perds en temps.
Dans ton cas précis, si tu n'as pas de contraintes en temps trop important,
tu peux génerer l'ensemble des points et selectionner uniquement ceux qui se trouvent dans le périmetre de ton rayon.

Un conseil, évite les cosinus, c'est gourmand en temps de calcul en général.
Tu peux ainsi utiliser une liste qui crée des couples de valeurs x et y dans un carré,
puis selectionner ceux que tu veux afficher en testant la distance de celui-ci par rapport à ton utilisateur.
x0 ey y0 etant la position de l'utilisateur.
x et y la position du point.
(x-x0)²+(y-y0)² etant la distance entre ton utilisateur et le point.

Mais ce n'est pas aussi simple...
Dans ce cas précis, tu vois que tu dois vérifier pour l'ensemble des points si ceux-ci sont dans ton périmetre au pas.
Ce qui sera long en temps de calcul si ta zone est grande, et donc le nombre de points.

L'astuce consiste à découper la zone que peut parcourir ton utilisateur en carrés,
de generer une liste par carré, et de ne tester que les points générés depuis les carrés adjacents à celui dans lequel se trouve l'utilisateur + celui ou il se trouve.
Soit 9 carrés.
Chaque liste de chaque carré sera donc générée avec la valeur mémorisée du carré, cette valeur pouvant être son indice absolu.
exemple:
x allant de 0 à 9 imbriquant y allant de 0 à 19
C=y+x*20
Le carré est initialisé avec la valeur unique C
randomize(C)

Tu vois qu'ici, utiliser un rayon aboutissant à des cercles, à la place d'un carré serait un handicap,
puisque tu ne pourrais pas avoir à ce moment des points répartis uniformements.
x=rnd et y=rnd par contre te fournira des points répartis uniformément pour un carré,
que tu peux donc accoler pour créer l'ensemble de la zone que ton utilisateur peut parcourir.

Reste donc à tester la distance de ton utilisateur aux points de tes 9 carrés, ce qui est raisonable en temps de calcul.

[A voir en vidéo sur Futura]

[invited38b5b91]

Ton idée des carrés est très intéréssantes, je vais partir sur ça ça devrait fonctionner. Il y a un bouton pour préciser que la question a été résolu ?