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.

[pseudocode]

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

Le "Jittering" c'est juste une approximation. En moyenne les points respectent un certain espacement, mais bien sur il y a des cas ou des points sont proches les uns des autres. Dans ces cas la, on a plusieurs solutions: retirages, déplacements, ...

[lilivounet]

Merci de vos réponses. C'est ce genre de choses que j'attendais, super.
Si je comprends bien la méthode proposée pour une implémentation simple du "Poisson Disk Distribution", c'est :
1) Je place le point 0 au hasard
2) i = 1
3) Je place le point i au hasard
4) Je vérifie que la distance de ce nouveau point i n'est pas trop proche de tous les points déjà placés : distance(point i, point j) > seuil mini, pour tous les j tels que 0 <= j < i
5) S'il est trop proche je reviens à l'étape 3
6) Sinon je fait i = i + 1 et je reviens à l'étape 3
7) Ceci jusqu'à avoir placé tous les points

(désolé pour la présentation, je ne connais pas les conventions d'écriture d'un algorithme!)

Effectivement ça ne semble pas très optimisé, mais quand je vois les documents proposés pour faire quelque chose de plus élaboré (ça par exemple) je tremble.

Ce qui me pose question c'est : comment choisir la distance minimale en fonction de la taille des pièces (rectangulaires), de leur nombre, et de la taille du rectangle d'arrivée, pour être sûr de ne pas rentrer dans une boucle infinie. En effet il faut prévoir que ce ne soit pas possible que les pièces ne se chevauchent pas du tout, si elles sont trop nombreuses par rapport à la taille du rectangle d'arrivée.

Sinon, en ce qui concerne le Jittering, je n'ai pas trouvé de méthode pour faire ce découpage en cases. Je dois chercher encore sur le net. Auriez-vous déjà sous la main un bon lien à ce sujet?

Merci vraiment de vos conseils!

[pseudocode]

Effectivement ça ne semble pas très optimisé, mais quand je vois les documents proposés pour faire quelque chose de plus élaboré (ça par exemple) je tremble.

Pas de panique. C'est la méthode de construction par diagramme de Voronoi.
Dans ton cas, ce n'est sans doute pas necessaire d'en passer par là.

Ton algo peut tout de même être légèrement optimisé (pour eviter les boucles infinies et optimiser les choix des points):

Fast Poisson Disk Sampling

Ce qui me pose question c'est : comment choisir la distance minimale en fonction de la taille des pièces (rectangulaires), de leur nombre, et de la taille du rectangle d'arrivée, pour être sûr de ne pas rentrer dans une boucle infinie.

Et bien, je dirais qu'il faut que toutes les N pieces tiennent dans ton rectangle:

N * surface_cercle = surface_rectangle
N * PI.R² = surface_rectangle
R = racine( surface_rectangle / PI.N )

Donc choisir une distance inter-point inférieure à 2*R.

[lilivounet]

Ah oui, là ça va beaucoup mieux !
Avec le document que tu me montres je vais pouvoir tenter une première implémentation. Je reviendrais ensuite donner des nouvelles. Pour l'instant ça reste flou pour moi, car je ne vois pas comment la méthode pourra générer exactement le bon nombre de points. J'imagine que sur la base que tu proposes pour calculer R, j'aurais à peu près le nombre de points voulu. A partir du moment où j'arrive à avoir au moins assez de points, je n'aurais plus qu'à en utiliser exactement le nombre qu'il me faut pour placer les pièces, en éliminant aléatoirement ceux qui sont en trop. Ou encore à stopper l'algorithme dès que j'ai assez de points.
Merci

[pseudocode]

Effectivement, tu dois calculer R pour avoir un peu plus que le nombre de points souhaité. Ensuite tu construis ta distribution et tu en prends le bon nombre.

[lilivounet]

Me revoilà !
C'est bon ça marche.
J'ai implémenté l'algorithme que tu m'as donné (ton dernier lien) et j'ai obtenu une belle distribution.
En prenant
R = racine( surface_rectangle / PI.N )
j'avais à peu près le double de points que ce que je voulais.

Finalement j'ai fait
R = racine( surface_rectangle / PI.N ) * adjust
avec 1.2 < adjust < 1.6
Comme le tirage des points est aléatoire, forcément le résultat n'est pas stable. Par exemple pour N = 100 le nombre de points oscillait entre 102 et 120 pour adjust = 1.36 (je ne me souviens plus exactement, mais c'est de cet ordre). Pire, avec le même adjust et N=12, le nombre de points trouvés pouvait être en dessous de 12. Il n'y a pas de valeur pour adjust qui sera "bonne" pour tous les N.
J'ai donc décidé de faire plusieurs tirages, en diminuant le rayon progressivement, jusqu'à avoir une distribution avec assez de points. Alors seulement j'élimine ceux qui sont en trop.
Je mets le résultat dans un swf (flash) en espérant que vous puissiez le voir simplement en cliquant dessus.

Bon au final on dirait que le Poisson Disk Distribution n'est pas parfaitement adapté, puisqu'il distribue des points à partir d'une surface et d'un rayon, et pas d'une surface et d'un nombre de points. Mais bon, ça marche et c'est déjà beaucoup.

Grands mercis à tous les deux

[lilivounet]

p.s. :
pseudocode, est-ce que tu connaitrais s'il te plaît une adresse qui regroupe des ressources similaires à celle que tu m'as donné sur le "Fast Poisson Disk Sampling" ?

[pseudocode]

En prenant
R = racine( surface_rectangle / PI.N )
j'avais à peu près le double de points que ce que je voulais.

heu... Il me semble que j'avais dit de prendre comme distance 2*R.

Finalement j'ai fait
R = racine( surface_rectangle / PI.N ) * adjust
avec 1.2 < adjust < 1.6

Interessant. Je parierai sur la valeur 4/PI.

Bon au final on dirait que le Poisson Disk Distribution n'est pas parfaitement adapté, puisqu'il distribue des points à partir d'une surface et d'un rayon, et pas d'une surface et d'un nombre de points. Mais bon, ça marche et c'est déjà beaucoup.

Oui, c'est vrai que dans le cas des images de synthèse on fixe le "rayon" du disque mais pas le nombre de disques souhaité.

pseudocode, est-ce que tu connaitrais s'il te plaît une adresse qui regroupe des ressources similaires à celle que tu m'as donné sur le "Fast Poisson Disk Sampling" ?

Heu... non. Mais en cherchant dans les ressources parlant de super/multi-sampling en images de synthèse, tu devrais trouver.

[lilivounet]

heu... Il me semble que j'avais dit de prendre comme distance 2*R.

c'est très vrai, ça !

Interessant. Je parierai sur la valeur 4/PI.

Pour info :

Pour
N=50
distance = racine( surface rectangle / (PI.N) ) * ( 4 / PI)
J'obtiens entre 62 et 72 points (sur une cinquantaine de tirages)

Pour
N=50
distance = racine( surface rectangle / (PI.N) ) * 2 (cad ta proposition initiale)
J'obtiens entre 23 et 30 points.

Heu... non. Mais en cherchant dans les ressources parlant de super/multi-sampling en images de synthèse, tu devrais trouver.

Bon j'ai un peu cherché, sans trouver, mais ce n'est pas grave, c'était pour me le mettre de côté à l'occasion de cette intéressante discussion, dont je te remercie encore.

[pseudocode]

Pour
N=50
distance = racine( surface rectangle / (PI.N) ) * ( 4 / PI)
J'obtiens entre 62 et 72 points (sur une cinquantaine de tirages)

Oui, il y a le cas des disques sur les bords du rectangle qui "débordent". Le coef idéal doit être complexe a calculer. Enfin bon, ce n'est pas le sujet, mais ça pourrait faire un bon défi.