Discussion :

[lilivounet]

Bonjour,
Je cherche comment m'y prendre pour distribuer un nombre N de points, de façon homogène, dans une surface rectangulaire donnée.
Voici dans quel cadre j'en ai besoin, pour préciser ma question :
Je programme un petit jeu de puzzle. Dans la réalité, pour faire un puzzle, le joueur va commencer par étaler toutes les pièces devant lui, de façon à ce qu'elles soient toutes visibles. Dans mon programme, une partie rectangulaire de l'écran de jeu est prévue pour cela. Au début de la partie, je veux présenter au joueur toutes les pièces, dans le désordre et bien réparties dans cette zone (voir la pièce jointe, la zone rectangulaire y est indiquée en vert).
Une simple distribution aléatoire des pièces n'est pas satisfaisante, car cela peut générer des "amas" de pièces à certains endroits. Je cherche donc la façon de procéder pour que les pièces soient réparties de la façon la plus homogène possible dans le rectangle (même si ensuite je peux rajouter un décalage et une rotation aléatoire pour donner un aspect un peu "fouilli").
Je souhaite trouver un algoritme qui puisse servir dans tous les cas, quelque soit le nombre de pièces, leurs dimensions, et la dimension du rectangle (car ces paramètres varient selon le puzzle choisi et la difficulté du jeu). C'est pour cela qu'il me semble que procéder à une répartition homogène des points centraux de chaque pièce est une bonne idée. Au final, si la taille du rectangle est trop petite pour contenir toutes les pièces sans qu'elles se recouvrent les unes les autres, je saurais au moins que leur recouvrement est minimum.
Est-ce que quelqu'un sait comment je pourrais faire cela, ou me donner des liens intéressants?
Merci bien.

[Zavonen]

Je suppose que tu disposes d'une fonction :
randfloat() donnant un flottant aléatoire entre 0 et 1.
La plupart des langages la fournissent, sinon elle est facile à fabriquer à partir de randint().
En général cette fonction correspond à une distribution homogène sur [0,1].
En multipliant par k tu as une fonction homogène sur [0,k]
Donc le point aléatoire [h*randfloat(), k*randfloat()] est distribué de façon homogène sur le rectangle (0,0) (0,k) (k,h) (h,0).
Si le point inférieur gauche du ectangle est (a,b) tu prends
(a+h*randfloat(),b+h*randfloat())

[pseudocode]

Si j'ai bien compris ce que le P.O cherche a faire, c'est répartir aléatoirement des points sur une surface, tout en garantissant un espacement minimum entre chaque point.

C'est un problème récurent dans la synthèse d'image (multi-sampling, photon mapping). Pour cela on utilise ce qu'on appelle "Poisson Disk Distribution".


NB: rien a voir avec la loi de poisson.

[Zavonen]

Dans ce cas, générer les points comme ci-dessus et conserver le nuage sous forme de tableau liste ou autre. A chaque génération d'un nouveau point, calculer la distance du point au nuage, rejeter si insuffisante (< diamètre d'une pièce -->nouveau tirage).
Le problème des bords se règle en faisant les tirages dans un rectangle intérieur de dimensions plus petites.

[pseudocode]

Dans ce cas, générer les points comme ci-dessus et conserver le nuage sous forme de tableau liste ou autre. A chaque génération d'un nouveau point, calculer la distance du point au nuage, rejeter si insuffisante (< diamètre d'une pièce -->nouveau tirage).
Le problème des bords se règle en faisant les tirages dans un rectangle intérieur de dimensions plus petites.

Oui, c'est l'implémentation la plus simple pour faire un sampling "Poisson Disk". Il y en a d'autre plus optimisées mais je ne pense pas que la vitesse soit un problème ici.

Sinon, il y a aussi le "Jittering" qui est une approximation du "Poisson Disk". Cela consiste a découper la surface en cases égales, et a mettre un point dans chaque case (n'importe où dans la case).

[Zavonen]

Sinon, il y a aussi le "Jittering" qui est une approximation du "Poisson Disk". Cela consiste a découper la surface en cases égales, et a mettre un point dans chaque case (n'importe où dans la case).

Pas vraiment n'importe où; suffisamment loin du bord de la case. De facto dans une case qui est dans la case.