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.
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.
Envoyé par watermarker
Pour commencer, considérons une sphère à deux dimensions, que nous appellerons cercle...
Oups FU2 humour scientifique
Jean-Luc
La violence est le dernier refuge de l'incompétence.
Salvor Hardin
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/
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
Les optimistes croient que ce monde est le meilleur possible. Les pessimistes savent que c'est vrai.
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 ...
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
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+
ç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.
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.
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.
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?
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
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 ?
"Have a ball, and get involved" - Beastie Boys.
" 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) ?
"ç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."
et bien si tu imagine que les billes sont a la surface de la sphere ne subisse aucune force exterieur, et subisse un frotement fluide a la surface de la sphere, elles vont forcements s'arreter un jour, le mouvement perpetuelle sa n'existe pas ^^
et si elle s'arrete c'est forcement a une position d'equilibre (puisque les frotements n'influe pas la dessus) ... en revanche savoir si elles ce sont arreté dans l'equilibre le plus stable ou non, sa c'est plus delicat...
C'est vrai que non, mais les solutions se ressemblent assez fort.
(ogre.nu c'est moi)
Pour certaines valeurs de n, ne devrait-on pas aboutir aux sommets de polyèdres uniformes ?
Les valeurs en question sont 4, 6, 8, 12, 20, 24, 30, 48, 60 et 120.
Breukin :
pour faire simple (mais ce n'est pas prouvé) tu peut trouver des polyhèdre régulier seulement si ceux si ont une majorité de faces triangulaire avec eventuellement quelque faces carré.
de mémoir ca marchais dans les cas,
n=4 (tétrahèdre)
n=6 octahèdre
n=12 icosahèdre
n=24 >>> jme rapelle plus du nom, mais celui avec 4 triangle et un caré à chaque sommet
n=32 pentaki dodécahèdre (c'est le polyhèdre obtenu en prenant les milieux des faces d'un balon de football, composé de triangle isocéle qui ce regroupe soit par 6 soit par 5 à chaque sommet
pour les suivant ca dégénère encore, les structure type 'dome géodésique' apparaisse parfois, mais pas systématquement (en effet, pour les nombres de charges élevés, il y a plusieur structre d'équilibre, à des niveaux d'énergie très proche qui apparaisse a peu pres aussi souvent les unes que les autre lors de la résolution numérique, les dome géodésique ne sont en géneral pas minimaux, mais suffisement stable pour apparaitre...)
Ca ne doit pas être le sens usuel de "polyèdre régulier"...
Cordialement,
Pour les polyèdres uniformes, on a tous les nombres pairs à partir de 4 sans exception, à cause des prismes...
Cordialement,
Qu'entends-tu par "dôme géodésique"? J'aurais tendance à comprendre "une triangulation avec tous les sommets ayant 6 voisins, sauf 12 d'entre eux qui en ont 5" (choix classique pour les balles de golf par exemple). Pourrais-tu confirmer, ou donner une définition du même ordre de précision?
Les triangulations en question donnent en particulier la série de nombres de sommets de 12 (icosaèdre), 42, ..., 12+10(i²+2i), ... et ça tend pour n croissant à l'infini vers la triangulation du plan, solution symétrique.
Cordialement,
J'avais exclu les prismes et les antiprismes car, intuitivement, il ne vont pas répondre au problème initial.
Pour 4, 1 seul polyèdre uniforme, donc 1 seule répartition (le tétraèdre).
Pour 6, 2 polyèdres uniformes, mais 1 seule répartition (l'octaèdre).
Pour 8, 1 seul polyèdre uniforme, donc 1 seule répartition (l'hexaèdre).
Pour 12, 8 polyèdres uniformes, conduisant à 3 répartitions (dont le dodécaèdre, mais aussi le tétraèdre tronqué et l'hexaoctaèdre) => laquelle répond au problème ?
Pour 20, 5 polyèdres uniformes, mais 1 seule répartition (l'icosaèdre).
Pour 24, 10 polyèdres uniformes, conduisant à 4 répartitions (donc l'hexaèdre adouci) => laquelle répond au problème ?
Pour 30, 9 polyèdres uniformes, mais une seule répartition (l'icosidodécaèdre).
Pour 48, 3 polyèdres uniformes, et 3 répartitions => laquelle répond au problème ?
Pour 60, 32 polyèdres uniformes, et... nombre de répartitions à calculer (donc le dodécaèdre adouci) => laquelle répond au problème ?
Pour 120, 4 polyèdres uniformes, et 4 répartitions => laquelle répond au problème ?
PS Le pentaki-dodécaèdre, dual du dodécaèdre tronqué ou ballon de football, n'a pas tous ses sommets sur la même sphère. Mais il est vrai qu'on peut les projeter.
Je me suis donc réduit aux 75 polyèdres uniformes, pour que les sommets soient sur une même sphère.
C'est clair, mais ma remarque était essentiellement de vocabulaire: le terme "polyèdre uniforme" ne les exclut pas.
Je n'ai pas vérifié chaque décompte, mais le nombre 75 indique clairement que tu inclus les non-convexes. Pour le problème en question, ce n'est pas plus pertinent de prendre les non-convexes que de prendre les prismes, il me semble. (L'égalité grossière de distance avec les plus proches voisins n'est une conséquence de l'uniformité que dans le cas convexe.)Je me suis donc réduit aux 75 polyèdres uniformes, pour que les sommets soient sur une même sphère.
Cordialement,
Dans ce cas particulier, un autre polyèdre uniforme convexe à 8 sommets, l'anti-prisme à base carrée a toutes les chances d'être plus performant.
Cordialement,
ce que je voulais dire, c'est qu'on à aucune chance de trouver les polyhèdre type cube/dodécahèdre ou encore le ballon de football qui ont des faces carré, pentagonal ou héxagonal, bien moins stable que les triangulation...
cependant on a parfois des faces carré qui apparaisse tous de meme, notement pour n=8 (un anti-prisme à base caré) et pour n=24 (dont je ne connais pas le nom...)
à propos des Dôme géodésique, je parlais essentiellement de ca :
http://fr.wikipedia.org/wiki/G%C3%A9ode
ou de tous ce qu'on trouve en tapant "dome géodésique" sur google
bien entendu on ne conserve que ceux à face triangulaire.
Pour finir, si je voulais aborder le problème en partant de solutions symétriques, je ne regarderais pas du côté des polyèdres uniformes, mais des polyèdres convexes sommet-transitifs. L'intérêt principal est de limiter le calcul à un seul sommet, et être sommet-transitif suffit.
On peut alors voir cela en partant des groupes ponctuels (ceux des prismes et les 7 spéciaux):
- un groupe de prisme est de taille 4n et permet des polyèdres sommet-transitif de 2n et 4n sommets;
- le groupe du tétraèdre permet 24 sommets (2 paramètres libres), 12 (1 paramètre libre) et le cas particulier de 4 sommets.
- le groupe du noeud de bois permet 24 sommets (2 paramètres libres) et 12 sommets (1 paramètre libre) - les cas particuliers sont dégénérés.
- le groupe des rotations du tétraèdres (ou du groupe précédent, c'est le même) permet 12 sommets (2 paramètres libres)
- le groupe du cube permet 48 (2 paramètres libres), 24 (1 paramètre libre) et les cas particuliers de 6, 8, et 12 sommets
- le groupe des rotations du cube permet 24 sommets (2 paramètres libres)
- le groupe de l'icosaèdre permet 120 sommets (2 paramètres libres), 60 sommets (1 paramètre libre) et les cas particuliers de 12, 20 et 30 sommets.
- le groupe des rotations de l'icosaèdre permet 60 sommets (2 paramètres libres).
On retrouve les mêmes nombre de sommets (pas étonnant, les uniformes sont des cas particuliers de sommet-transitifs!), mais il y a pas mal de chance que les solutions symétriques optimales soient autres que les uniformes dans de nombreux cas.
Cordialement,
sinon regardait ceci par exemple :
http://physics.syr.edu/thomson/thomsonapplet.htm
jusqu'a n=50 c'est tres fiable (audessus, faut déja etre plus prudent...)
C'est bien la même chose que je décrivais autrement...
Cordialement,
mmy, à propos de la démarche que tu propose dans le poste de 17h02 : est ce que tous les groupe fini d'isométrie sont connu ?
