bonjour,
(dans le cadre d'un programme sous matlab)
je souhaite trouver les mi (coef. de ponderations) qui caractérisent un point au milieu de n autres sommet d'une figure .(n sera compris entre 3 et 6)
je sais deja que les mi doivent etre < 1 et que leur somme doit etre egale à 1 pour que mon point ce situe DANS ma figure.
je sais comme retrouver les coordonnés de mon point connaissants les sommets et leur coefficients de pondération.
Je ne sais pas comment calculer ces coefficients.
J'avais essayé avec la distance (euclidienne) separant mon point des sommets de ma figure, puis en la normalisant, mais le resultat n'est pas bon ( sans bouger les sommet, les coordonnés de mon point ne sont pas les memes avant et apres le calcul.)
J'ai verifié avec 3 points si le reste de mon algorithme fonctionnait et c'est le cas.
Donc seul mes coefficients sont mauvais.
Quelqu'un a une idée ?
d'avance merci
Bonjour,
Je n'ai peut-être pas compris ton problème, mais il me semble que les coordonnées barycentriques d'un point au milieu de n autres ne sont pas uniques. Prends par exemple le centre O d'un carre ABCD (avec les sommets dans cet ordre). On peut à la fois écrire, en vecteurs :
1/4.0A + 1/4.OB + 1/4.OC + 1/4.OD = 0
1/2.OA + 1/2.OC = 0
1/2.OB + 1/2.OD = 0
Nicolas
>Nicolas
si on veut les n points dans la relation vectorielle, les coeff ne sont pas uniques ?
Philoux
Philoux,
Dans mon exemple, j'ai bien à chaque fois les 4 points dans ma relation vectorielle, avec les coefficients suivants :
1/4, 1/4, 1/4, 1/4
1/2, 0, 1/2, 0
0, 1/2, 0, 1/2
Enfin, je crois
Nicolas
Oui nicolas 16:45
je n'avais pas pas envisagé que les coefs pouvaient être nuls
Merci
Philoux
De toute façon, tout se calcule...
Soit Ai les n points, de coordonnées (xi, yi).
Soit M (x,y) le point à placer.
On cherche les ai tels que :
* (en vecteurs) a1.MA1 + ... + an.MAn = 0
* a1 + ... + an = 1
C'est-à-dire :
* a1.(x1-x) + ... + an.(xn-x) = 0
* a1.(y1-y) + ... + an.(yn-y) = 0
* a1 + ... + an = 1
On a un système de 3 équations à n inconnues a1, ... an.
Pour n=3, la solution est en général unique (regarder les déterminants pour voir les cas particuliers).
Pour n>=4, la solution n'est pas unique.
Sauf erreur.
Nicolas
ok ... j'avais vu que la solution n'etait pas unique, seuleument, je veux pas mettre n-(n-3) coef a 0 et calculer les deux autres car ca voudrait dire que certain sommets n'ont pas d'importance dans le placement du point.
Je voudrais que plus un sommet soit proche de mon point, plus il a de l'influence sur celui ci.
du coup je doit inclure la notion de distance dans le calcule des poids de ponderation.
si je bouje un sommet, le point bouge avec lui plus ou moins selon ce poids.
Mon probleme c'est que actuellement, lorsque je place ce point, je calcul les coef et lorsque je re-affiche avec la transposition de coordonnée barycentrique vers coordonnées initiale, mon point bouge.
Lorsque je selectionne trois sommets (n=3) (donc un triangle) comme influencant mon point, je ne retrouve pas les meme valeur de coef que lorsque je fais avec le calcule que propose Nicola_75.
Je me suis pris au jeu avec mon exemple de carré :
n=4, A1(0,0), A2(2,0), A3(2,2), A4(0,2)
et M au centre : M(1,1)
Le système s'écrit :
(1) - a1 + a2 + a3 - a4 = 0
(2) - a1 - a2 + a3 + a4 = 0
(3) + a1 + a2 + a3 + a4 = 0
Soit :
(1)+(3) a2 + a3 = 1/2
(3)-(1) a1 + a4 = 1/2
(2)+(3) a3 + a4 = 1/2
(3)-(2) a1 + a2 = 1/2
En posant a4 = t, il vient les solutions :
a1 = 1/2 - t
a2 = t
a3 = 1/2 - t
a4 = t
Il y en a une infinité.
En particulier, pour t=0, t=1/4, t=1/2, on retrouve les 3 solutions particulières proposées ci-dessus.
Nicolas
Bonjour,
Dans le plan, le repere affine doit avoir 3 points affinement indépendants (et non 4 dans l'exemple du rectangle). Dans ce cas, les systemes de coordonnées barycentrique sont proportionnels
Sanders
Nicola tu as compris mon probleme ......... c'est ca, avec plus de trois points, il doit bien y avoir une solution unique qui correspond a mes contraintes de distance ! je ne peux pas me permettre de choisir arbitrairement un coef.
dans l'exemple de ton CARRé, imagine le point M dans le coin superieur droit, du coup le coin sup. droit doit exercé plus d'attraction que les autres, la valeur du poind associé doit etre plus grande que les autres.
(tout en respectant que la sommes des coef. soit =1)
"je sais deja que les mi doivent etre < 1 et que leur somme doit etre egale à 1 pour que mon point ce situe DANS ma figure"
ci-dessous, 6 points (4 auraient suffit) avec :
et pourtant ... chaque coefficient est <1 et la somme vaut 1 ces deux conditions ne sont donc pas suffisantes
>NN
vassili doit vouloir dire à l'intérieur du polynôme de plus grande surface.
par ailleurs, si tu permutes E et F, G est à l'intérieur
Philoux
hein ? rien ne précise que son polygone n'a pas le droit de ne pas être convexe
polygone et non polynôme
Effectivement : rien ne précise...
Philoux
D'ailleurs, la notion "de milieu d'une figure" ...
Si l'on veut un point qui est toujours (sauf si le polygone est croisé) à l'intérieur et qui satisfait les deux conditions mentionnées, il suffit de considérer l'isobarycentre de trois sommets consécutifs (on ignore les autres points) par exemple, avec ma figure :
Vassily,
Il faut peut-être essayer de traduire en langage mathématique ce que tu veux.
Voici un exemple, qui ne résoudra probablement pas ton problème, mais qui peut donner des idées.
Tu sembles souhaiter que :
(1) Si le point à placer M est proche d'un sommet Ai, alors le coefficient ai soit proche de 1
(2) Si le point à placer M est loin d'un sommet Ai, alors le coefficient ai soit proche de 0
D'où l'idée que ai soit proportionnel à :
ai = beta * 1 / ( 1 + ||MAi|| )
où beta ne dépend pas de i, et se calcule avec a1 + ... + an = 1
Evidemment, de tels coefficients ne "fonctionnent" pas, car rien ne prouve que a1.MA1 + ... + an.MAn = 0 (en vecteurs).
Néanmoins, on peut essayer de minimiser ;
somme sur i { [ai - beta/(1+||MAi||)]^2 }
pour trouver les "meilleurs" ai parmi les solutions de l'équation de 3 équations à n inconnues ci-dessus.
Pour l'exemple de mon carré, on obtient, après calculs t=1/4, c'est-à-dire les coefficients 1/4, 1/4, 1/4, 1/4, ce qui était intuitivement la solution à ton problème.
Bon courage,
Nicolas
Une piste ? Je ne sais pas comment marche Matlab, mais dans un triangle ABC par ex. les coordonnées barycentriques de M (encore une fois, il faut 3 pts et non pas 4 pour parler de coordonneés barycentriques) sont les Aires des MAB, MAC, MBC. Je ne sais pas ce que ça fait si on augmente le nombres de pts, mais comme alors, ils ne sont plus indépendants, il faut pouvoir trouver les coef des pts supplémentaires dans le repere affine d'origine et pondérer les points petit à petit. Est-ce que tu peux calculer l'aire avec Matlab ?
pas mal Nico je vais essayer ca.
j'explique mieux mon probleme pour Philoux et NN,
j'ai plein de points sur une image, j'en rajoute 1 puis je selectionne les points que je trouve interressant et qui pourraient influencer le nouveau point. puis je calcule les coordonées barycentrique de ce nouveau point avec les points que j'ai selectionné. comme ca si jamais un des sommets bouge, alors le point suivra.
exemple sur un visage je determine des point caracteristiques fixe (mes sommets) et lorsque je place un autre point celui ci bouge si le visage bouge. ainsi si le visage ouvre la bouche, plusieurs points bougent et pas seulement les sommets.
je sais pas si je suis clair ?
Vassily,
Une solution simple, qui ne va probablement pas te contenter : choisis uniquement 3 points de référence auxquels raccrocher le nouveau point. Tu dois absolument pouvoir choisir 4, 5 ou 6 points de référence ?
Nicolas
ca serais plus simple mais mon maitre de stage veut plus ! quand tu ouvre la bouche, il n'y a pas que trois points qui font ta joue bouge.
en fait il y en a une infinité. je pense que ta methode de minimiser est pas mal. je vais essayer ca demain je te tient au courant !
Pour continuer sur ma piste (peut-être en impasse) de rapprocher les ai de 1/(1+||MAi||), il faut en fait procéder à la...
minimisation de l'expression du second degré en a1, ..., an :
somme sur i { [ai - beta/(1+||MAi||)]^2 }
où les 1/(1+||MAi||)]^2 sont connus
où beta = 1 / { somme sur i de 1/(1+||MAi||) } est connu (et fixé arbitrairement en partant de l'idée que a1 + ... + an = 1 [ce qui est vrai] et ai = beta/(1+||MAi||) [ce qui est faux])
sous les 3 contraintes linéaires :
* a1.(x1-x) + ... + an.(xn-x) = 0
* a1.(y1-y) + ... + an.(yn-y) = 0
* a1 + ... + an = 1
Mes souvenirs ne me permettent pas de pousser la piste plus loin. Mais n'existe-il pas des théorèmes pour avancer ?
Nicolas
je ressort mes cour d'optimisation .........;;
quoi que matlab doit savoir me faire ca tout seul !
par contre il y aune question que je me pose !
Vaut il mieux avoir tous mes coef. proches de ce qui m'arrange sauf 1 tres different ou
Tous un peu differents ? (pour une minimisation identique !)
une explication sur les barycentres
bonjour,
"(dans le cadre d'un programme sous matlab)
je souhaite trouver les mi (coef. de ponderations) qui caractérisent un point au milieu de n autres sommet d'une figure .(n sera compris entre 3 et 6)"
précise stp ce que tu entends par "au milieu": c'est un peu vague...
tes n points forment-ils un polygone convexe (c'est-à dire si tu prends 2 points à l'intérieur de ce polygone, le segment formé par ces deux points est à l'intérieur de ce polygone).
si tu as un polygone régulier, au milieu sera clair, et ton point sera l'isobarycentre (tous les points ont la même masse), toutes les masses seront égales (et on n'a pas besoin que la somme de ces masses soient égales à 1: pour avoir une somme égale à 1, si ça t'arrange, tu divises chaque masse par la somme).
dans le cas d'un polygone convexe, il suffit que tous les coefficients soient de même signe (positif ou négatif, mais positif sera plus simple) pour que leur barycentre soient à l'intérieur du polygone.
l'idée de ramener ton problème à trois points ne me semble pas mauvaise: tout point du plan pouvant s'exprimer comme barycentre de trois points non alignés.
avec les barycentres partiels, ça devrait pouvoir marcher (il me semble). le barycentre partiel te permet de remplacer deux ou plusieurs points par le barycentre de ces points (le coefficient dont tu affecteras ce nouveau point étant la somme des coefficients).
donc tu te ramènes à trois points (en prenant par exemple les milieux de segments) tu trouves les coeff avec ton algo qui marche pour trois points:
tu trouves (A,a), (B,b) (C,c) (a, b, c ne seront pas nécéssairement de même signe, puisque pas forcément à l'intérieur du triangle que tu auras construit avec les barycentres partiels)
tu remplaces ensuite les milieux que tu as pris par les extremités affectées chacune du coefficient divisé par deux, et ça roule.
autre remarque pour trois points, plutôt que de considérer l'aire des triangles qui ne permet de caractériser le barycentre de ces trois points que si celui ci est intérieur au triangle, tu peux considérer cette caractérisation, qui doit bien marcher en informatique:
étant donné trois points A,B,C non alignés, tout point M du plan est le barycentre de {(A,det(MB,MC))(B,det(MC,MA))(C,det(MA,MB))}.si tu as les coordonnées de tous les points, on peut pas faire plus simple...
bon courage, et si tu comprends pas tout, n'hésite pas à poster, j'essaierai avec un exemple.
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :