Discussion :

[Djakisback]

Bonjour,
je suis sur un problème intéressant mais j'ai du mal à penser un algo pour le régler.

Je compare 2 nuages de points A et B en calculant la somme des distances euclidiennes des points pour obtenir un degré de différence (plus la somme est basse, plus les 2 nuages sont similaires).
(Pour rappel, un nuage de points 2D est simplement un ensemble de points de coordonnées x,y dans un repère orthonormé)

ex :
nuage A
point a (12, 8)
b(1, 3)

nuage B
point a (10, 8)
b(-10, 2)

Ce que j'appelle distance euclidienne est en fait la norme de la soustraction des vecteurs, ex : pour comparer A et B je fais la somme des vecteurs soustractions et j'en récupère la norme :
Somme = ||(Ba - Aa) + (Bb - Ab)||

(D'ailleurs est-ce c'est bien cela que l'on appelle distance euclidienne ?)

Le but est de redresser le nuage B en y appliquant des symétries sur l'ensemble de ses points pour qu'il soit le plus proche possible de A : symétries sur x, y et des axes arbitraires de 45° que j'appellerai xy et -xy, .

J'essaie de trouver un algo optimum pour cela mais je peine un peu.
Ma première idée est de générer toutes les situations possibles et de comparer tous les nuages états finaux (A vs B, A vs B', A vs B'', etc.). A priori il n'y en a pas beaucoup, sachant que 2 symétries s'annulent.
Pensez-vous que l'idée soit bonne ?
Sinon pensez-vous que l'arbre peut se construire au fur et à mesure et que la meilleure solution peut-être trouvée sans parcourir ou créer tout l'arbre (parcours en largeur) ? A priori je dirais que non car une position optimum semble pouvoir passer par une position très mauvaise, les symétries changeant les coordonnées des points de façon absolument radicale.

Toute piste ou suggestion est donc la bienvenue
Merci d'avance.

(J'essaie déjà de faire un algo pour des nuages 2D mais l'algo final gèrera les nuage 3D.)

[souviron34]

de ce que je comprend, ton problème a (comme toute chose de ce type en géométrie), 3 éléments :

• rotation
• translation
• zoom

Donc, dans l'ordre, ce que je ferais c'est trouver la rotation et l'appliquer
puis trouver le zoom et l'appliquer

[Nebulix]

Il y a eu un débat sur les nouveaux métiers de l'informatique : Redresseur de nuages aurait mérité d'y figurer.
Utiliser les différents moments de tes nuages (barycentres, axes principaux,etc.) permettrait de simplifier le pb

[souviron34]

Il y a eu un débat sur les nouveaux métiers de l'informatique : Redresseur de nuages aurait mérité d'y figurer.

pendant 10 ans j'étais "afficheur de coups de foudre"

[Djakisback]

Merci pour les suggestions

Pour ce qui est des barycentres, je n'ai pas de "recentrage" (ou contre-balancement, je ne connais pas le terme ) à faire sur les nuages car justement la position relative des points en fonction de l'origine est importante à conserver. Pour les axes principaux je ne vois pas ce que tu veux dire.

Au sujet des rotations je pensais faire cela dans un 2e temps, d'ailleurs à ce sujet je crois que je pourrais décliner ensuite l'algo pour générer des symétries sur un nombre d'axes arbitraires plus important, car il me semble que toutes rotations peut se représenter par une succession de symétries, mais je n'en suis pas sûr.

Par contre, j'avais effectivement oublié le scaling mais cela ne posera pas de problème, l'algo pour ça est très simple. On arrête de scaler en positif ou négatif dès que le degré de différence augmente.

Pour l'instant je crois que je vais donc rester sur cette idée de successions de symétries sachant que je ne vois pas trop comment poser des conditions d'arrêts pour ne pas tourner en boucle et revenir sur des états déjà générés. Il faudrait sans doute que je conserve tous les états du nuage B. A la base je ne pensais pas les conserver mais ne conserver que les degrés de différences entre les nuages.

[souviron34]

Pour les axes principaux je ne vois pas ce que tu veux dire.

il y a deux "axes" privilégiés équivalents à des axes X,Y.. forcément.. quel que soit le nuage de points..

[Djakisback]

En fait, les coordonnées des points sont dans un repère orthonormé basique x(1,0), y(0,1) d'origine (0,0) et il me semble que les axes principaux sont simplement x et y.

[souviron34]

En fait, les coordonnées des points sont dans un repère orthonormé basique x(1,0), y(0,1) d'origine (0,0) et il me semble que les axes principaux sont simplement x et y.

sans doute pas...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
  *
 *      *            **
          *  **            *
                *    **
                             *
                          * *

on voit bien qu'il y a deux axes diagonaux par rapport à x,y..

[Nebulix]

Si ton nuage est en forme d'ellipse, ses axes principaux sont le grand axe et le petit axe de cette ellipse. Ils se coupent à angle droit au centre de gravité.

[Djakisback]

D'accord, merci je comprends mieux (enfin, je crois ^^).

Je pense que dans mon cas ça n'a pas lieu d'être car je ne compare pas des ensembles de points mais chaque point 2 par 2. Le degré de similitude/différence se fait sur les différences de positions de chaque point du nuage A et de son "image" dans le nuage B :
A = {a,b,c,...}
B = {a',b',c',...}
Somme = ||(a - a') + (b - b') + (c - c') + ...||

(a, b, c, a', b', c' sont des vecteurs)

[Graffito]

Peux-tu confirmer les bases du problème:

1. On ne cherche pas parmi un ensemble de points à trouver 2 nuages optimaux, mais il y a 2 ensembles de points, chacun définissant un nuage.
2. Les 2 nuages A et B comportent le même nombre de pioints n.
3. On peut redresser un nuage en lui appliquant des déformations.
4. ensuite, compte tenu du "redressement" opéré, on a une fonction de comparaison qu'on peut appliquer à toutes les combinaisons pour déterminer la meilleure correspondance, soit n! calculs pour avoir le "degré de différence".

Quels sont les "redressements/déformations" que tu es autorisé à appliquer sur le nuage B ?

[Djakisback]

Salut,
et merci pour l'intérêt porté au problème
Oui c'est bien cela 1, 2 et 3.
Pour le 4, n! c'est la factorielle ? Si c'est le cas en fait non il y a seulement n calculs/comparaison entre A et B, puis n calculs entre A et B', etc.

J'ai effectivement une méthode me permettant de comparer donc 2 nuages et de retourner un degré de différence qui est en fait la somme de toutes les distances entre les points du nuage A et les points similaires du nuage B.
Si on compare 2 nuages identiques on obtient donc 0.
Par exemple si j'ai 3 nuages A, A', A'' contenant un seul point a,a',a'' chacun :
A = {a(10, 12)}
A' = {a'(8, 12)}
A'' = {a''(9, 12)}

La comparaison de A et A' donne :
a' - a = 2
La comparaison de A et A'' donne :
a'' - a = 1
A et A'' sont donc "plus similaires" que A et A'.

Pour que le nuage B reste valide je peux appliquer des symétries sur n'importe quel axe arbitraire, du scaling homogène, et des rotations sur l'origine.

[Graffito]

J'ai effectivement une méthode me permettant de comparer donc 2 nuages et de retourner un degré de différence qui est en fait la somme de toutes les distances entre les points du nuage A et les points similaires du nuage B.

Veux-tu dire que si A est composé de {a1,a2, .. an} et B de {b1,b2,...,bn}, ai correspond forcément à bi et que tu n'as pas à envisager toutes les correspondances possibles ai<->bj (d'où le factoriel n de ma question) ?

je peux appliquer des symétries sur n'importe quel axe arbitraire

Axes devant tous passer par l'origine qui est "fixe" ?

[Djakisback]

Oui c'est tout à fait ça. Un point a1 a son équivalent b1. Si j'ai 5 points dans chaque nuage, je compare donc 10 points par couple, ce qui fait 5 calculs.

Pour les symétries c'est bien cela également, n'importe quel axe passant par l'origine qui est toujours en (0,0). Au début je pensais me cantonner uniquement aux axes x,y et 2 axes à 45 degrés (-x,y) et (x,y) pour simplifier l'algo.

[Graffito]

Somme = ||(a - a') + (b - b') + (c - c') + ...||

Si on utilise Somme = ||(a - a')**2 + (b - b')**2 + (c - c')**2 + ...||
et, pour une rotation et une symétrie donnée, le scaling seul peut être résolu en exprimant la norme ainsi ainsi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
// k = facteur de scaling
Norme = f(k) =
(a1x-k*b1x)**2 + (a1y-k*b1y)**2 +
(a2x-k*b2x)**2 + (a2y-k*b2y)**2 +

Ainsi Norme est un polygon du 2nd degré en k, ce qui permet de trouver la valeur de k minimisant la Norme (valeur annulant la dérivée f'(k)).

Pour les rotations et symétrie, on peut tester un ensemble fini d'angles de rotation et d'angles pour la droite de symétrie.
Si on prend par exemple des angles tous les degrés, ça fera 360 x 180 calculs . Pas brillant intellectuellement , mais jouable !

En pratique, on pourrait peut-être optimiser par une technique s'apparentant à la dichotomie, par exemple en prenant des angles de 10° en 10°, puis en affinant tous les 1° dans l'intervalle de 20° autour du(es) meilleur(s) résultat(s).

[Jean Dumoncel]

Bonjour,

si j'ai bien compris, tu cherches à faire une Analyse procustéenne?

[Djakisback]

Merci pour vos réponses
@Graffito :
Je ne suis pas sûr de bien comprendre ton calcul en particulier le **2, est-ce que tu aurais des précisions ?
Effectivement pour les symétries cela semble difficile mais pour les rotations il devrait y avoir moyen d'appliquer le même principe que pour le scaling ? en exprimant la rotation et une différence/soustraction ?
rotated(a1)

Je précise que le scaling, n'est a priori pas une priorité car les nuages générés sont généralement de tailles très proches.

@magelan
Merci pour le lien, ça semble être exactement cela que je veux faire, je regarde en détail

(Juste quand j'allais dire : "analyse procustéenne, quel nom barbare", je vois que Procuste avait d'ailleurs l'air particulièrement sympathique ^_^)

[Graffito]

Je ne suis pas sûr de bien comprendre ton calcul en particulier le **2, est-ce que tu aurais des précisions ?

Mon idée se basait sur une définition de norme calculée ainsi :

• Points du nuage A : ai(aix,aiy)
• Points du nuage B : bi(bix,baiy)
• Norme(i) = (aix-bix)*(aix-bix) + (aiy-biy)*(aiy-biy)
• Norme_totale = Norm(0)+norm(1)+...+Norme(n)

[Djakisback]

Ah ok, merci bien.
Tu parles donc bien de la norme vectorielle, je manipule les vecteurs avec des méthodes depuis tellement longtemps que je n'avais pas fait le rapprochement
Oui effectivement, je vais voir cela.
Pour l'instant je factorisais tout pour le calcul du degré de différence mais je ne peux pas en déduire k :
Norme = norme(diff(a0,b0) + diff(a1,b1) + ...)

En fait, si, si k est un vecteur mais là je m'embrouille un peu. Je vais réfléchir à tout ça

[Graffito]

En fait, si, si k est un vecteur

?
k est un réel positif (facteur de scaling)