Discussion :

[darkman19320]

Bonjour tout le monde,

J'ai 3 points (A, B, C) dont je connais leurs coordonnées dans le repère 1. Un utilisateur doit sélectionner ces points dans un autre repère 2 (A', B', C'). Pour ce faire, l'utilisateur voit une zone autour des 3 points.
Au début, j'ai essayé de comparer la longueur entre les 3 segments du triangle (qui ne sera jamais isocèle ou équilatéral) à l'aide des coordonnées des 3 points dans les deux repères puis de trier les segments en fonction de leur longueur.

Le problème est que la zone d'incertitude autour de chaque point influence grandement la comparaison des longueurs.

J'ai essayé en utilisant des ratios entre les longueurs des segments mais comme je m'y attendais, je n'obtiens pas le résultat attendu: à savoir que le point A' doit correspondre au point A, B' au point B, C' au point C.

Voici un petit schéma pour résumer un peu la situation.



Je n'ai pour le moment pas les dimensions de la zone d'incertitude autour de chaque point (en vert).

Quelqu'un aurait-il des conseils à me donner?

Merci d'avance

[wiwaxia]

Bonjour,

Pour caractériser les sommets d'un triangle scalène, il suffit de leur associer la longueur du côté opposé; par exemple dans le triangle (UVW), le sommet (U) sera caractérisé par la distance (u = VW), (V) par (v = WU) et (W) par (w = UV).
D'où une reconnaissance instantanée des images (A', B', C') de l'objet de départ (ABC): (U) s'identifiera ainsi à (A') si (u = a), les deux autres égalités - (u = b) et (u = c) - étant alors obligatoirement fausses, selon ce que tu as indiqué:

Au début, j'ai essayé de comparer la longueur entre les 3 segments du triangle (qui ne sera jamais isocèle ou équilatéral)

Cependant la prudence s'impose toujours quant à la vérification de l'égalité des réels en cause (les distances), et de fortes incertitudes viennent encore compliquer la comparaison des longueurs.

... Le problème est que la zone d'incertitude autour de chaque point influence grandement la comparaison des longueurs.
... Je n'ai pour le moment pas les dimensions de la zone d'incertitude autour de chaque point (en vert).

L'égalité hasardeuse (u = a) de deux réels positifs doit être remplacée par la condition dépourvue d'ambiguïté:
Abs(u - a) < e * (u + a) ,
dans laquelle (e) représente l'incertitude relative affectant les calculs. Et puisque dans le cas d'un triangle (UVW) de périmètre (p = u + v + w) la même incertitude absolue affecte chacun des côtés, on pourra recourir à la condition encore plus sûre:
Abs(u - a) < e * p .

# Dans le cas le plus favorable, (e) correspond au "epsilon machine" , valeur plancher liée au codage des réels et dépendant du logiciel utilisé - e = 10^-16 il me semble, selon les standards actuels (Scilab), e = 10^-18 dans le cas du Turbo Pascal (publicité gratuite). Il sera d'ailleurs prudent de choisir un seuil plus élevé, par exemple: e = k * e_machine , avec k = 10 ou 100 .

# Une valeur plus élevée s'impose, si des incertitudes plus importantes affectent les données (ce que l'énoncé semble supposer). Il faut alors partir de l'expression analytique du carré de la distance:
r² = (x_j - x_i)² + (y_j - y_i)² + (z_j - z_i)² et la différencier, pour en tirer une borne majorée de l'incertitude.

# Si tu travailles sur un ensemble de points ou de triangles, tu aurais intérêt à te référer au plus grand d'entre eux:
Abs(u - a) < e * P_max
ou - condition encore plus large - à la longueur de la diagonale du plus petit parallélogramme contenant l'ensemble des points:
Abs(u - a) < e * D_max , avec D_max² = (x_max - x_min)² + (y_max - y_min)² + (z_max - z_min)².

# Dernière précaution: s'assurer qu'aucun des triangles envisagés n'ait le mauvais goût d'être "presque" isocèle ou équilatéral, en vérifiant de la condition:
Min(Abs(u - v), Abs(v - w), Abs(w- u)) > Seuil d'égalité .
Ce bloc d'instructions s'incorpore facilement à la procédure d'identification des sommets.

[wiwaxia]

Approche probabiliste: tout triangle (ABC) peut être représenté, indépendamment de son orientation spatiale, par un point de coordonnées (a, b, c) dans un repère orthonormé.
La "proximité" d'un autre triangle (UVW) y est alors mesurée par la distance euclidienne:
d = ((u - a)² + (v - b)² + (w - c)²)^1/2
et la "probabilité de coïncidence" des deux figures P(s, d) = Exp(-d²/s²) est égale au produit des probabilités de superposition des chacune des trois arêtes:
P(s, d) = Exp(-(u - a)²/s²) * Exp(-(v - b)²/s²) * Exp(-(w - c)²/s²) = P(s, (u - a)) * P(s, (v - b)) * P(s, (w - c)) .

Un tel calcul permet donc de discerner, parmi les six arrangements possibles (UVW, VWU, WUV, etc ...), celui conduisant à la meilleure superposition au triangle initial (ABC).
Peut-être s'agit-il là d'un vain habillage analytique du problème, le critère binaire (vrai/faux) y étant remplacé par une fonction continue (la loi de Gauss); le cas litigieux d'un rectangle quasi -isocèle en (U) se traduit en effet par deux probabilités fortes, mais très proches (P_UVW = P_UWV) et ne permettant plus de faire un choix.

L'avantage réside en la possibilité d'étendre la recherche à quatre points: l'énoncé n'interdisant pas des triangles à arêtes communes, on peut envisager un tétraèdre (ABCD) d'arêtes (a, b, c, a', b', c'), caractérisable par un point dans un espace euclidien de dimension 6; la probabilité de coïncidence d'un autre tétraèdre (UVWX) s'y exprime cette fois par le produit de six termes:
P(s, d) = = P(s, (u - a)) * P(s, (v - b)) * P(s, (w - c)) * P(s, (u' - a')) * P(s, (v' - b')) * P(s, (c' - w')) ,
et le calcul doit être fait pour les 4! = 24 arrangements possibles.

Les cas d'indétermination (2 probabilités voisines, et très supérieures à toutes les autres) sont maintenant plus rares, d'autant qu'il intervient désormais un nouveau critère: les tétraèdres objet (ABCD) et image (UVWX) présentent la même orientation intrinsèque, ce que l'on vérifie par l'identité de signe des déterminants correspondants: ⁽¹⁾
Det_ABCD = (AB, BC, CD) et Det_UVWX = (UV, VW, WX) .
⁽¹⁾ si bien sûr les repères employés (R₁, R₂) sont tous deux directs (ou indirects).