Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 38

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



  1. #1
    watermarker

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


    ------

    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.

    -----

  2. Publicité
  3. #2
    yat

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

    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.

  4. #3
    Jean-Luc P

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

    Citation 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
    Jean-Luc
    La violence est le dernier refuge de l'incompétence.
    Salvor Hardin

  5. #4
    matthias

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

    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/

  6. A voir en vidéo sur Futura
  7. #5
    fderwelt

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

    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.

  8. #6
    Ksilver

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

    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 ...

  9. Publicité
  10. #7
    matthias

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


  11. #8
    Quinto

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

    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+

  12. #9
    invite986312212
    Invité

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

    Citation 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.

  13. #10
    Quinto

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

    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.

  14. #11
    yat

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

    Citation 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.

  15. #12
    invite986312212
    Invité

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

    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?

  16. Publicité
  17. #13
    yat

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

    Citation 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

  18. #14
    ExtatiK Design

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

    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.

  19. #15
    Ksilver

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

    " 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) ?

  20. #16
    Ksilver

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

    "ç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...

  21. #17
    Tamfang

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

    Citation Envoyé par Ksilver Voir le message
    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"...
    C'est vrai que non, mais les solutions se ressemblent assez fort.

    (ogre.nu c'est moi)

  22. #18
    breukin

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

    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.

  23. Publicité
  24. #19
    Ksilver

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

    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...)

  25. #20
    invité576543
    Invité

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

    Citation Envoyé par Ksilver Voir le message
    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é.
    Ca ne doit pas être le sens usuel de "polyèdre régulier"...

    Cordialement,

  26. #21
    invité576543
    Invité

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

    Citation Envoyé par breukin Voir le message
    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.
    Pour les polyèdres uniformes, on a tous les nombres pairs à partir de 4 sans exception, à cause des prismes...

    Cordialement,

  27. #22
    invité576543
    Invité

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

    Citation Envoyé par Ksilver Voir le message
    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...)
    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,

  28. #23
    breukin

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

    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.

  29. #24
    invité576543
    Invité

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

    Citation Envoyé par breukin Voir le message
    J'avais exclu les prismes et les antiprismes
    C'est clair, mais ma remarque était essentiellement de vocabulaire: le terme "polyèdre uniforme" ne les exclut pas.

    Je me suis donc réduit aux 75 polyèdres uniformes, pour que les sommets soient sur une même sphère.
    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.)

    Cordialement,

  30. Publicité
  31. #25
    invité576543
    Invité

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

    Citation Envoyé par breukin Voir le message
    Pour 8, 1 seul polyèdre uniforme, donc 1 seule répartition (l'hexaèdre).
    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,

  32. #26
    Ksilver

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

    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.

  33. #27
    invité576543
    Invité

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

    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,

  34. #28
    Ksilver

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

    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...)

  35. #29
    invité576543
    Invité

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

    Citation Envoyé par Ksilver Voir le message
    à 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.
    C'est bien la même chose que je décrivais autrement...

    Cordialement,

  36. #30
    Ksilver

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

    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 ?

Page 1 sur 2 1 DernièreDernière

Discussions similaires

  1. Distribution uniforme de points sur sphère.
    Par 281281 dans le forum Mathématiques du supérieur
    Réponses: 9
    Dernier message: 14/04/2010, 15h07
  2. déplacer un point sur une sphère suivant une direction
    Par watermarker dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 26/08/2006, 01h43
  3. placer n points sur une boule unité de dimension voulue
    Par watermarker dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 31/05/2006, 17h42
  4. Points sur une sphère
    Par EaGle58 dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 20/04/2006, 14h40
  5. La plus petite sphère contenant quatre points
    Par matou dans le forum Mathématiques du supérieur
    Réponses: 47
    Dernier message: 01/04/2005, 13h50