répartir n points sur une sphère unité le mieux possible

watermarker · 19/05/2006 - 15h26

Je cherche à répartir n points sur une sphère unité de manière a ce que la distance minimum entre deux points soit maximale. J'aimerais savoir si vous pouviez m'éclairer ou me conseiller de la documentation traitant de ce sujet.
Merci d'avance.

yat · 19/05/2006 - 15h39

Je ne sais pas si c'est ce que tu veux, mais je peux te proposer une méthode algorithmique :
1) tu places aléatoirement les points dans un cube qui contient la sphère
2) tu projettes les points sur la sphère
3) tu considères que les points se repoussent et tu calcules leur nouvelle position
4) si l'étape 3 a changé quelque chose tu recommences en 2

Pour le 3, la méthode simple c'est de considérer qu'il n'y a pas d'inertie, et déterminer directement la position suivante du point en fonction des forces exercées par les autres point. L'autre méthode est de conserver les vitesses des points et de traiter les accélérations, en n'oubliant pas d'ajouter des frottements.

Après quelques essais de paramétrages, ça peut converger en quelques itérations, et à l'équilibre les points sont répartis de manière uniforme. Maintenant je ne peux pas affirmer que ça respecte strictement la maximisation de la distance minimale.

Jean-Luc P · 19/05/2006 - 15h45

Envoyé par watermarker

Je cherche à répartir n points sur une sphère unité de manière a ce que la distance minimum entre deux points soit maximale.

Pour commencer, considérons une sphère à deux dimensions, que nous appellerons cercle...

Oups FU2 humour scientifique

matthias · 19/05/2006 - 15h54

Il n'y a pas de solution théorique connue au cas général. Algorithmiquement le plus simple est effectivement de procéder comme le propose Yat (on peut prendre comme modèle physique des particules chargées électriquement).
2 liens en anglais :
http://mathworld.wolfram.com/SphericalCode.html
http://astronomy.swin.edu.au/~pbourk.../spherepoints/

fderwelt · 19/05/2006 - 16h35

Bonjour,

matthias <<

Il y a une solution théorique, du moins algorithmique, elle a comme seul inconvénient d'être impraticable.
"Sphere Packings, Lattices and Groups", JH Conway & NJA Sloane, Springer-Verlag, 1991.

Passionnant, mais inutilisable.

-- françois

Ksilver · 20/05/2006 - 13h34

mais qu''est ce qui nous dit que les deux problemes aboutissent a la meme sollution ?

"maximiser la distance minimal entre les bille" et "position d'equilibre de n charge ponctuelle sur une sphere"...

d'ailleur pour le deuxieme la position d'equilibre obtenue depend fortement de la loi de force utilisé (1/r² si on parle de charge ponctuelle, mais on peut utiliser d'autre loi, 1/r ou K-r par exemple...)

ceci dit si vous avez des references sur le problemes "position d'equilibre de n charge ponctuelle sur une sphere" sa m'interesse moi ...

matthias · 20/05/2006 - 14h16

Si vous voulez un peu de lecture et quelques images :
http://www.ogre.nu/pack/pack.htm
http://presh.com/hovinga/outline.html
http://www.ogre.nu/sphere.htm
http://sitemason.vanderbilt.edu/page/hmbADS

Bon courage

Quinto · 23/05/2006 - 01h43

Je pense que le problème a un lien avec la théorie du potentiel, les mesures d'équilibre, les problèmes de capacités et de fonction de Green associés à un ensemble. Je pense que le lien se fait via le diamètre, voir le diamètre transfini de ton ensemble, ce qui revient à travailler avec des polynômes type Fekete ou Chebychev.
Bref, avec ces mots clés et ce que t'ont répondu les autres avant moi, tu devrais surement trouver quelque chose qui t'intéresse sur le sujet.

Note que si en théorie il n'y a pas de belle formule connue, algorithmiquement, ca se fait assez bien.

A+

invite986312212 · 23/05/2006 - 08h12

Envoyé par Ksilver

mais qu''est ce qui nous dit que les deux problemes aboutissent a la meme sollution ?

"maximiser la distance minimal entre les bille" et "position d'equilibre de n charge ponctuelle sur une sphere"...

ça ne me semble pas évident que des particules chargées sur une sphère se placent dans une position d'équilibre. On peut imaginer qu'elles se mettent à "orbiter" sans fin.

Quinto · 23/05/2006 - 16h29

Notons quand meme que dans le cas d'un cercle, ca ne pose pas vraiment de probleme.

Pour ce qui est du fait que les particules se mettent ou non à tourner sans fin ca n'a aucune importance, il suffit de faire tourner le domaine en meme temps pour faire en sorte qu'elles ne bougent plus. Ce qui importe c'est la manière dont elles se placent les une par rapport aux autre qui importe.

yat · 23/05/2006 - 16h37

Envoyé par Quinto

Pour ce qui est du fait que les particules se mettent ou non à tourner sans fin ca n'a aucune importance, il suffit de faire tourner le domaine en meme temps pour faire en sorte qu'elles ne bougent plus. Ce qui importe c'est la manière dont elles se placent les une par rapport aux autre qui importe.

Si les particules tournent sans fin, c'est qu'on n'a pas introduit de frottements, et sans frottements je pense que toutes les particules vont osciller sans jamais s'arréter, même les unes par rapport aux autres.

invite986312212 · 23/05/2006 - 16h38

mais est-ce que c'est évident que les particules se déplaceraient comme les sommets d'un solide inscrit?

mais même dans le cas unidimensionnel je n'intuite pas la solution:
prenons deux points aux deux extrêmités du diamètre d'un cercle et supposons une répulsion en 1/r^2. Si on donne une impulsion à l'un des deux points, est-ce que le système va se mettre à tourner ou bien est-ce que le point va revenir à sa position initiale?

yat · 23/05/2006 - 16h51

Envoyé par ambrosio

prenons deux points aux deux extrêmités du diamètre d'un cercle et supposons une répulsion en 1/r^2. Si on donne une impulsion à l'un des deux points, est-ce que le système va se mettre à tourner ou bien est-ce que le point va revenir à sa position initiale?

Le point aucune raison de revenir à sa position initiale. Une fois qu'il a bougé, la position d'équilibre de l'autre va bouger aussi et il va se déplacer vers elle.

Le système va se mettre à tourner et s'arréter plus ou moins vite en fonction des frottements. Ce qui est sur c'est qu'il finira par atteindre une nouvelle position d'équilibre ou les deux points sont à nouveau diamétralement opposés

ExtatiK Design · 24/05/2006 - 18h06

Tiens, la question me rappel ça: http://www.vanderbilt.edu/news/releases?id=15880
Y'a pas déjà eu un dossier ou un fil sur Futura ?

Ksilver · 24/05/2006 - 18h49

" Note que si en théorie il n'y a pas de belle formule connue, algorithmiquement, ca se fait assez bien."

il y a d'autre methode que la recheche numerique de la position optimal (avec une methode genre descente du gradient ou chose dans ce genre la) ?