bonsoir,
j'ai 65 points uniformément répartis sur la sphère, je veux extraire 34 points (uniforme)à partir de 65 points.
pourriez vous m'aider à résoudre ce problème.
bien cordialement.
Version imprimable
bonsoir,
j'ai 65 points uniformément répartis sur la sphère, je veux extraire 34 points (uniforme)à partir de 65 points.
pourriez vous m'aider à résoudre ce problème.
bien cordialement.
Par curiosité, j'aimerais avoir la liste des 65 points d'origine.
Tu dis qu'ils sont uniformément répartis : C'est un maillage parfait, les distances 2-à-2 sont strictement égales, ou pas ? Et dans la 2nde option, ça veut dire que les 65 points sont presque uniformément répartis.
Et a priori, on est dans la 2nde option, car à ma connaissance, il n'existe pas de polyèdre régulier à 65 sommets.
Peux-tu déjà confirmer ce point.
Bonjour,
je vous remercie pour votre réponse.
vous trouverez ci-joint la liste des coordonnées des points.
je travaille dans le domaine de l'IRM de diffusion et l'uniformité des points est un critère très important pour pouvoir estimer le signal de diffusion.
j'ai utilisé cette application pour générer les 65 points.
Merci encore une fois pour votre aide.
Bien cordialement.
voici le lien de l'application
http://www.emmanuelcaruyer.com/q-space-sampling.php
Bof...
J'ai regardé le fichier gradient65.
J'ai calculé les distances 2 à 2 entre tous les points. Et pour chaque point, j'ai regardé ses plus proches voisins. Je m'attendais à ce que, entre un point donné et ses 6 plus proches voisins, on obtienne 6 fois la même valeur, ou en tout cas 6 valeurs très proches les unes des autres. Pas de pot, ce n'est pas du tout le cas.
Par exemple, pour le 1er point (0.049, 0.919, 0.391) , ses pus proches voisins sont à des distances de 0.267, 0.327, 0.411, 0.428 ... ... Et on a des valeurs similaires pour les autres points.
Autrement dit, la définition de 'répartition uniforme' n'est pas du tout celle que j'avais imaginée.
En regardant le lien que tu as donné, on constate un truc : Quand on demande N valeurs, on a N points, puis s quand on sélectionne un N+x points, on a les mêmes N points, plus x nouveaux points.
Ca confirme que la définition de répartition uniforme n'est pas celle que j'attendais.
Mais, ça répond peut-être à la question initiale ?
Pour extraire 34 points parmi 65, il faudrait donc prendre les 34 premiers points du fichier ? ça paraît pas si mal, car si on prend le centre de gravité des N premiers points, on trouve toujours un point assez proche de (0,0,0)
Bonjour,
Je tirerais au hasard selon une distribution uniforme, 34 coordonnées parmi les 65.
En Matlab cela donne :
Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
Bonjour,
Je crois que la notion d'uniformité a amené beaucoup de confusion, par son ambigüité.
L'ensemencement uniforme d'une sphère se réfère à une densité surfacique de probabilité uniforme, cad indépendante de l'endroit considéré; il peut résulter de plusieurs procédés aléatoires: Sphere Point Picking
et n'exclut pas la présence de petits agrégats très denses, où les distances locales sont très inférieures à la moyenne observée sur l'ensemble du nuage, entre plus proches voisins.
Or ce c'est manifestement pas ce que l'on observe sur le site indiqué par ines ben alaya: le nuage ne comporte pas de zones anormalement denses, ni les lacunes qui devraient les accompagner.
Consulter pour plus de précision Random Points on a Sphere, où la variante envisagée est confirmée:
A more æsthetically pleasing pattern can be generated using Poisson-disc sampling, where no points are less than a minimum distance apart.
Le problème est ici de remonter d'un nuage de 65 points à un autre qui n'en comporte plus que 34, par l'élimination systématique des points les plus proches afin que la loi de répartition soit conservée.
Lorsque (N) points sont aléatoirement répartis sur une sphère de rayon (R) et d'aire S = 4*Pi*R2, chacun d'eux est le pôle d'une calotte sphérique quasiment plane, tangente à sa plus proche voisine et dont l'aire vérifie s < S/N en raison de la surface résiduelle non recouverte.
En négligeant cette dernière, et en assimilant la calotte à un disque de rayon (r) - c'est le cas d'un grand nombre de points en arrangement compact et "régulier" - il vient:
s ~ 4*Pi*R2/N et s ~ Pi*r2 , ce qui conduit à r ~ 2*R/N1/2 ainsi qu'à une estimation de la distance minimale (Dm ~ 2*r) entre 2 points du nuage: Dm ~ 4*R/N1/2 .
Une solution consisterait donc à:
a) Déterminer la distance minimale (D0) dans le nuage initial à 65 points;
b) Calculer le nouveau seuil D1 = D0*(65/34)1/2 relatif au second nuage;
c) Éliminer par inventaire méthodique sur un premier indice (i) - par exemple par tirage aléatoire - les points trop proches (Mj , j <> i) vérifiant (MiMj)2 < (D1)2 .
Le résultat obtenu dépend à priori de la valeur du seuil (D1), ainsi que de l'ordre des indices testés (i); plusieurs essais seront nécessaires.
@ tbc92: recourir au polyèdre à (N) sommets et de forme optimale (Dmin maximale) est bien sûr une solution; mais la recherche de tels solides est assez pénible (sauf cas particulier de symétrie élevée), et il n'y a à priori aucun lien entre les polyèdres initial et final (65 et 34 sommets); on sort donc ici du sujet traité.
Si on se connecte sur le site en question, et qu'on Download le fichier pour 63 points, puis pour 65 points, on constate que les 63 premiers points sont communs aux 2 fichiers. Ce qui est incompatible avec la définition d'uniforme qu'on peut avoir, mais ça permet de comprendre la définition d'uniforme qu'on a dans ce contexte.
Et je suis à peu près convaincu que la démarche que tu proposes va nous amener aux 34 premières lignes du fichier des 65 lignes.
C'est tout à fait probable dans le cas de l'énumération rigide (i = 1, 2, 3 ... 34), et c'est en quelque sorte tricher en connaissant le mode génératoire de la liste (qui, ceci dit, m'intrigue un peu ... mais c'est ici secondaire). Il existe un grand nombre (C6534 ?) d'autres liste partielles de 34 termes, dont chacune est caractérisée par une distance minimale, et qui apparaîtront dès que l'on commence l'inventaire avec des valeurs dépassant 34.Citation:
Envoyé par tbc92
Faute de pouvoir les comparer toutes, on pourra se rabattre sur un nombre indéterminé de tirages aléatoires pour obtenir la plus grande valeur de (Dmin).
Une variante du même procédé, toujours construit sur le choix préalable du sommet initial (Mi0) et du seuil de distance (D1), et nécessite la constitution de 2 listes de points: l'ancienne (L1) correspondant à la liste de départ privée du sommet choisi (Mi0), et la nouvelle (L2) se réduisant initialement à ce même point:
À la nième étape (0 < n < 34), avant laquelle (n) points ont déjà été retenus et consignés dans (L2):
a) éliminer parmi les (p) points restants (p <= 65 - n) de (L1) ceux qui sont trop proches des précédents et vérifient:
(MiMj)2 < D12 , avec (i) dans [1 ; n] et (j) dans [1 ; p];
b) retenir - s'il en reste - celui correspondant à la plus faible distance dépassant la limite (D1), et transférer ce sommet de (L1) à (L2).
Si le processus fournit moins de 34 points, le reprendre pour une valeur plus faible de (D1).
Le critère d'arrêt devrait se réduire à la consigne de sécurité: ((p = 0) OR (aucun point à distance > D1))
qui permet d'éviter le plantage du programme.
Si l'on y inclut la collecte d'un nombre suffisant de sommets: ((p = 0) OR (aucun point à distance > D1)) OR (n = 34)
on prend le risque - dans le cas d'une valeur trop faible du seuil de distance (D1) - de laisser inachevée une construction vérifiant la condition initiale d'espacement mutuel des sommets (Dij >= D1), mais susceptible d'en comporter plus de 34: on observera alors une lacune dans la zone diamétralement opposée au point de départ.
Pour chaque sommet initial (Mi0) il faudra donc faire une série d'essais, afin de cerner les limites (D1min, D1max) de part et d'autre desquelles le nouveau nuage comporte 35, 34 et 33 sommets.
Espérons que le domaine recherché soit connexe :aie: Inutile de faire des cauchemars, le pire n'est jamais certain.
Autre solution, indépendante d'un seuil de distance et conduisant à une solution unique, mais dont la mise en oeuvre est assez lourde (je pressens déjà de légères réticences ... :furieux: ).
On part de la liste initiale comportant 65 points.
1) Pour les (k) points de toute liste intermédiaire (34 < k <= 65), inventorier les valeurs de la fonction "potentiel"
Ui = Somme(j=1 à k, j<>i)(1/(MiMj)q , avec q = 4 ou 8 (pour faire simple) .
2) Repérer la valeur maximale de (Ui) - cela s'effectue en même temps que le calcul précédent - et supprimer le point correspondant.
3) Reprendre les opérations (1) et (2) sur la nouvelle liste de sommets, qui n'en comporte plus que (k - 1), jusqu'à ce qu'il ne subsiste plus que 34 termes.
Il ne va pas de soi que le résultat obtenu coïncide avec l'une des 65 solutions attendues de l'algorithme précédent, parce que le critère d'élimination des sommets est ici différent: Ui = Max(U1, U2, ... Uk) .
On peut intuitivement s'attendre à ce que cela se produise pour un exposant élevé (q = 8, 16 ... ?).
Dans un premier temps je travaillerai sur 1/8 de sphère semi ouverte. le reste ce déduisant par symétrie et rotations.
Là ou je m'interroge c est que tes points sont forcément pas uniformément réparti.
65 ou 34 points au total. donc sur 1/8 de sphère j'ai 65/8 = 8.125 points ou 34/8=4.25 points.
Si tu te place en coordonnées sphériques tu t’apercevras que pour avoir des points uniformément répartis il faut que le pas de θ et φ soient un diviseur de 360 (en degrés)
Donc plus ton pas seras petit plus tu auras de points
Découper la sphère en 8 et procéder par symétries n'apporte rien, bien au contraire. Si on veut disposer 12 points de façons régulière, il y a une disposition parfaite (le dodécaedre régulier) et pourtant, 12 n'est pas un multiple de 8.
Je ne comprends toujours pas la justification de ce problème, et sur ce point seule l'étudiante qui a formulé la question pourrait nous apporter des éclaircissements:
Citation:
Envoyé par ines ben alaya
Que pour évaluer un phénomène de diffusion, on s'intéresse à (N) points aléatoirement répartis sur une sphère, de telle sorte que l'ensemble soit dépourvu d'éléments de symétrie, et présente un aspect suffisamment homogène, soit.Citation:
Envoyé par ines ben alaya
Mais pourquoi ne pas prendre directement N = 34 points, puisque leurs coordonnées sont immédiatement disponibles sur le site indiqué ?
Pourquoi prendre d'abord N0 = 65 points, et galérer ensuite pour en extraire ensuite N1 = 34 ? Pourquoi ne pas partir de 100 ou même 522 points, qui figurent sur la liste téléchargeable ?
D'autant que la restriction du choix des 34 points au premier nuage induit des contraintes difficiles à satisfaire, et pourra conduire à une distance minimale D1 notablement inférieure à son estimation théorique D0*(65/34)1/2 ; on risque de déboucher sur une distribution décevante, peu homogène, caractérisée par D1 ~ D0 .
La liste proposée sur le site résulte vraisemblablement (comme l'a vu un autre intervenant) de l'accumulation progressive des points selon une distribution en disques de Poisson. Ne pourrait-on pas se contenter des 34 (ou 65) premiers termes ?
pour tcb92
Jouer sur les symetries peut être utile dans le cas d'énorme volume de données pour éviter des calculs inutils si tu recherches de la performance.
Après ce n 'est pas nécéssaire effectivement.
par contre un dodécaedre régulier ce n 'est pas 12 points mais 20 points. et 12 faces.
Bonjour, :D
La remarque est juste, quoiqu'on aurait pu songer aux centres de chacune des faces, et non pas aux sommets (mais l'argument est à la limite de la mauvaise foi).Citation:
Envoyé par maleaume
Cependant tbc92 n'en a pas moins raison sur le fond, puisque la partition de la sphère en huit secteurs identiques, suppose de faire intervenir la symétrie par rapport à chacun des 3 plans orthogonaux (Oxy, Oyz, Ozx) du repère utilisé, donc des sous-ensembles de points en comportant 8 (en général), 4 (s'ils appartiennent à l'un des plans) ou 2 (s'ils sont sur l'un des axes): soit au total un nombre pair, ce qui n'est pas le cas du nuage initial (où l'on en trouve 65).
Il y a par ailleurs une raison plus profonde, la simulation d'un phénomène de diffusion à partir d'un modèle statique suppose une répartition aléatoire des points sur la sphère, donc l'absence totale de tout élément de symétrie - ce que permet d'obtenir le procédé d'ensemencement étudié, et contrairement à ce que tu souhaites et qui te paraît aller de soi.
Citation:
Envoyé par maleaume
On va se rabattre sur le dimension 2 : je veux disposer 155 points sur un cercle (sur le périmètre du cercle) ; c'est facile. Je calcule A= 360°/155 =2.3225°, et je dispose un point tous les 2.3225°.
Si je veux exploiter la symétrie, et partir du principe qu'en dimension 2, il me suffit de traiter 1 quart du cercle, et de faire une symétrie par rapport à l'axe des x, puis une symétrie par rapport à l'axe des y, c'est planté. Aucune manipulation ne me permettra de trouver la solution pourtant évidente.
Et si je décide de traiter la moitié du cercle, alors ça marche, à condition d'avoir eu la bonne idée de positionner le premier point sur cet axe de symétrie, et donc de traiter ce point différemment des autres.
Cet exemple qui est flagrant en dimension 2 se généralise en dimension 3. Mais c'est plus difficile à visualiser.
Donc symétrie, oui, a condition de prendre 1000 précautions et d'être dans un cas favorable.
Donc non dans l'absolu.
La répartition optimale de 34 points en répulsion mutuelle sur une sphère de rayon unité aboutit à une polyèdre à 64 faces triangulaires et 96 arêtes, dont 68 présentent la longueur minimale Dmin = 0.614809791345 . Bien qu'il s'agisse de la plus grande distance observable (1), le résultat est dans le cas présent irrecevable, en raison de la présence d'un axe de symétrie d'ordre 2, évident sur l'image ci-dessous: il joint les milieux des arêtes qui se projettent sur la partie centrale.
Pièce jointe 234035
La diffusion d'un faisceau de rayonnement parallèle à cet axe présenterait le même élément de symétrie, ce qui serait incompatible avec la répartition aléatoire des particules diffusantes.
Faut-il préciser qu'un tel arrangement est manuellement inaccessible, et ne relève pas d'une simple permutation des coordonnées ou de leur signe ?
Une distribution appropriée exclut tout élément de symétrie; l'identité est alors la seule transformation isométrique laissant inchangé le nuage de points, ce qui est le cas du polyèdre suivant, où les 96 arêtes, toutes inégales, présentent des longueurs comprises entre 0.581618635 et 0.930050654 (2). Noter que Dmin est ici nettement inférieur au seuil précédemment trouvé.
Pièce jointe 234039
Ce résultat équivaut au procédé des disques de Poisson, à ceci près que le diamètre n'est pas prédéterminé (parce qu'on ensemence une surface d'aire finie); et il n'y a par ailleurs aucun lien avec un éventuel polyèdre à 65 sommets.
(1) Sous réserve que la limite a bien été atteinte ... le procédé est long et demande de nombreuses itérations en fonction de certains paramètres.
(2) Couleur cyan: distance minimale; rouge: distance maximale; vert ... orangé: valeurs intermédiaires.
