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.