Trouver le "barycentre inverse" d'un nuage de points

[invitef0706432]

Bonjour à tous,

Remarque 1 : Je ne suis pas mathématicien

Remarque 2 : J'ai toujours eu du mal avec les maths

Voila mon exercice : J'ai d'une part un nuage 1D de n points et à l’intérieur un point supplémentaire que j'appelle G.

Les coordonnées (notons les x) des n points et du point G sont connues.

Le point G peut coïncider avec un des points du nuage.

Plusieurs points du nuage peuvent coïncider.

J'aimerais (très fort) pouvoir calculer les coefficients m (un pour chaque point) tels que (définition d'un barycentre).

______________________________

Jusque là, je me suis dit intuitivement : "si je fixe un seul coefficient m, alors je dois pouvoir déduire les autres."

Donc, en fixant , on a :

En partant de ça, on peut écrire un système à n-1 équation :



avec





et



Voila, donc en refaisant plusieurs fois les calculs j'arrive à ça.

Problèmes:

1- Premièrement dans cet algo si le point G coïncide avec un des points du nuage de point le dénominateur s'annule (division par zéro).
2- En implémentant cet algo dans un programme Python, 8 fois sur dix ça fonctionne mais malheureusement des fois l'algo diverge lors de la résolution de l’équation matricielle et je ne sais absolument pas quoi faire avec ça...

Donc je me demandais si je n'ai pas fait une erreur quelque part et surtout s'il n'y a pas un moyen plus simple pour faire ce que je veux faire...

Je suis peut-être en train d'essayer de réinventer la roue...

Merci à tous pour votre aide et vos réponses !

Bien cordialement
-----

[acx01b]

salut,

si xG différent de 0, alors trouver un x_i différent de 0, m_i = x_G / x_i, tous les autres m_j sont à 0 ?

en 2D ou en N dimensions le problème devient plus intéressant, et il se rapproche de PCA (ou analyse en composante principale)

[gg0]

Bonjour.

Si on est en dimension inférieure à n, il existe généralement des coefficients m_i qui conviennent. Ils ne sont pas uniques, mais définis à un coefficient multiplicatif près. par exemple pour 2 points sur un axe, de coordonnées (abscisses) a et b, et si G a pour abscisse g, tu cherches m et m' tels que

Si on ajoute la condition m+m'=1, on obtient g=ma +(1-m)b qui donne la valeur de m si A et B sont distincts. Mais en remplaçant m par 2m et m' par 2m', l'égalité marche toujours. Ce qui correspond à poser m+m'=2, d'ailleurs.

Donc :
A priori on peut trouver des valeurs
Elles ne sont pas uniques.

Question : A quoi ça sert ?

Cotrdialement.

NB : Un cours sur la notion de barycentre pourrait t'éclairer.

[invitef0706432]

en 2D ou en N dimensions le problème devient plus intéressant, et il se rapproche de PCA (ou analyse en composante principale)

Salut @acx01b !

En fait mon problème est en 3D, mais je me suis dit qu'il pouvait être décomposé en trois problèmes à 1D... (un pour x, un pour y et un pour z)

si xG différent de 0, alors trouver un x_i différent de 0, m_i = x_G / x_i, tous les autres m_j sont à 0 ?

Ehhhhhh..... je comprends pas très bien ce que tu dis....

il n'y a pas d'indice j puisque i = 1,2,3,...,n

...

[A voir en vidéo sur Futura]

[invitef0706432]

A priori on peut trouver des valeurs
Elles ne sont pas uniques.

Bonjour @gg0

En effet, il y a plusieurs valeurs, et c'est pour ça que je me suis dit que fixer une valeur permettait de n'avoir qu'une seule solution pour les autres valeurs (mais je suis incapable de le démontrer et peut-être n'est-ce pas toujours vrai, je ne sais pas...).

Question : A quoi ça sert ?

Au final, ça doit servir à déformer un maillage 3D (tetrahedrique). Le nuage de points, ce sont les noeuds en périphérie, et le point G est un noeud à l'intérieur du maillage. Le but est de calculer les coefficients m pour chaque noeud interne avant déformation, puis de déformer la surface du maillage, puis de déplacer les noeuds internes en utilisant les coefficients précédemment calculés.

NB : Un cours sur la notion de barycentre pourrait t'éclairer.

Bah j'ai cherché sur internet ! Le mieux que j'ai trouvé est la formule plus haut (x_g = ...)

Je suis bien entendu ouvert à toute nouvelle information sur le sujet

Bien cordialement,

[ansset]

Au final, ça doit servir à déformer un maillage 3D (tetrahedrique). Le nuage de points, ce sont les noeuds en périphérie, et le point G est un noeud à l'intérieur du maillage. Le but est de calculer les coefficients m pour chaque noeud interne avant déformation, puis de déformer la surface du maillage, puis de déplacer les noeuds internes en utilisant les coefficients précédemment calculés.
,

bonjour,
si ton problème est en 3D , tu ne peux pas le décomposer en 3 pb séparés à 1D ,
tout simplement parce que les mi doivent être les mêmes.

comme l'a fait remarquer gg0 : tu peux déjà simplifier en partant de sigma(mi)=1

tu as 3 équations pour n points.
xg=sigma(xi*mi)
yg=sigma(yi*mi)
zg=sigma(zi*mi)

tu devine très vite que si n>3 tu as plus d'inconnues que d'équations. ( donc une infinité de solutions )
si n=4 en fixer 1 te permet de déduire les autres.
si n=5 en fixer 2 , etc....

mais je ne suis pas sur d'avoir compris ta finalité.
pourquoi doit tu t'imposer G , et non pas calculer un barycentre qui te permet ensuite de déformer ?
je ne sais pas non plus si tu peux préparer un maillage structuré ( points équidistants par exemple, ou autre structure régulière ) ?

dans l'inconnu j'imagine une piste peut être farfelue.
tu remets d'abord tout dans un repère avec G comme centre.
tu projettes depuis G tous les points sur une sphère de rayon R , donc en introduisant un coeff de dilatation pour chaque point.
là tu cherches un algo qui attribue des poids à chaque point inversement proportionnels à la densité locale de points .
( je ne sais pas exactement comment faire , mais c'est une idée )
le but est que G devienne barycentre de ce nuage sphérique.( le nuage est déjà plus structuré )
tu ramène les points à leur position d'origine en divisant les poids obtenus par les coeff initiaux.

vu l'heure, et que j'ai fait ma petite insomnie, j'espère ne pas partir dans du n'importe quoi.
cordialement.

[ansset]

autre démarche pour G soit barycentre de ta sphère.
tu attribues d'abord des poids identiques 1 par exemple à chaque point.
tu obtient un barycentre G' à l'intérieur de la sphère.
il faut ensuite ramener G' vers G.
pour cela tu modifies les poids en fonction des cos( GG', GP )
ce qui revient à modifier surtout les poids des points dans l'axe GG' en baissant si le cos est positif et en augmentant si le cos est négatif.
et progressivement ne pas toucher au points perpendiculaires à l'axe GG' pour ne pas dévier de l'axe. ( leur cos est nul )

bon, tout ce que je raconte est assez intuitif, après tout.

[ansset]

ce qui revient à modifier surtout les poids des points dans l'axe GG' en baissant si le cos est positif et en augmentant si le cos est négatif.
et progressivement ne pas toucher au points perpendiculaires à l'axe GG' pour ne pas dévier de l'axe. ( leur cos est nul )
.

il fallait lire l'inverse , suis dyslexique la nuit !

[invitef0706432]

Hello,

si ton problème est en 3D , tu ne peux pas le décomposer en 3 pb séparés à 1D ,
tout simplement parce que les mi doivent être les mêmes.

... Pas bête

comme l'a fait remarquer gg0 : tu peux déjà simplifier en partant de sigma(mi)=1

tu as 3 équations pour n points.
xg=sigma(xi*mi)
yg=sigma(yi*mi)
zg=sigma(zi*mi)

tu devine très vite que si n>3 tu as plus d'inconnues que d'équations. ( donc une infinité de solutions )
si n=4 en fixer 1 te permet de déduire les autres.
si n=5 en fixer 2 , etc....

Alors ça veut dire que si j'ai n=300 000 points en 3D, j'en fixe 300 000 - 3 = 299 997 !?

mais je ne suis pas sur d'avoir compris ta finalité.

J'ai un maillage tétraédrique non structuré (3D). Je connais la position de tous les noeuds du maillage.

Puis arrive une déformation de la forme extérieure du maillage. Je connais donc la position des noeuds périphériques après déformation.

Je veux ensuite déduire la nouvelle position des noeuds à l'intérieur du maillage. Pour ça je veux utiliser les coefficients m_i calculés avant déformation...

Donc avant déformation je connais x_G et je veux déduire les coefficients m_i par rapport au nuage de points formé par les noeuds en périphérie du maillage, et après déformation j'applique les coefficients m_i pour trouver la nouvelle position des noeuds internes par rapport à la nouvelle forme du maillage périphérique...

Mais peut-être n'est-ce pas réaliste... Il me semblait que c'était une bonne idée...

dans l'inconnu j'imagine une piste peut être farfelue.

Eeeeeeeh, je crois que je ne vais pas m'aventurer là dedans parce que j'espère trouver quelque chose de plus direct !

Et aussi et surtout parce que je dois optimiser le temps de calcul de tout ça sur des maillages très lourds... Donc je cherche aussi à minimiser le nombre d'opérations...

Mais j'apprécie l'idée

[ansset]

quelle est la nature de ta déformation : homogène? , en fonction du rayon et des coord polaires ? ...?

[invitef0706432]

quelle est la nature de ta déformation : homogène? , en fonction du rayon et des coord polaires ? ...?

Ça peut être du maillage assez complexe de ce style :



Et la déformation n'est pas du tout homogène...

En réfléchissant au fait qu'il faut fixer n-3 coefficients, je finis par trouver ça logique... Et me dis que le coup du barycentre n'est pas viable.

Ou alors je peux imposer un coefficient qui décroit avec la distance pour les n-3 points et déduire les 3 derniers. Mais c'est un peu brouillon comme approche et je ne pense pas que le résultat soit très propre...

Je vais voir ça...

[ansset]

je saisi mieux la problématique , je crois.
passer par un seul point G à la structure ne me semble pas adapté.
donc même mon idée de passer par une sphère homogène n'est pas bonne.
fixer le poids de N-3 points encore moins si tu en a 300 000.

il me semble qu'il faut trouver une démarche plus heuristique tenant compte de la topologie globale de la structure.
ici par exemple tu as en gros 2 pseudo cylindres reliés par une structure pseudo-plane.
il faut peut être traiter séparément les 3 éléments de structure et les "recoller" à la fin.
je suppose que la déformation envisagée conserve la topologie de l'ensemble;
auquel cas peut on imaginer prendre l'axe d'un cylindre et sa longueur et affecter 2 coeff : un pour l'élargissement, un pour l'élongation, ou bien les déformations envisagées sont plus "tordues" que ça. ?

autre question : s'agit il au final d'un pb de modélisation d'aérodynamique par exemple ? et donc d'écoulement le long de la surface ?