Discussion :

[eminatta]

Bonjour,
J'aurais besoin d'aide pour réaliser un algorithme permettant de trouver le point de Fermat d'un triangle ABC quelconque;
J'ai essayé à plusieurs reprises d'en créer un sans succès.. En effet je ne vois pas comment faire du tout!
Je voulais utiliser la formule AG=√(xB−xA)2+(yB−yA)2. avec G ,point de Fermat
Il faudrait trouver la somme des distances AG+BG+CG minimale or je me retrouve avec deux boucles for parcourant seulement des entiers.. ce qui ne fonctionne pas!

Avez vous des idées ?
Merci de votre aide

Mathilde

[wiwaxia]

Bonjour,

Quelques remarques:
a) Il vaut mieux noter F (ou I) le point de Fermat, et réserver la lettre (G) à l'isobarycentre, dont on peut avoir besoin.
b) Il est indifférent que les coordonnées de (A, B, C) soient entières; par contre celles du point recherché sont nécessairement réelles.
c) Tu devras exprimer trois distances par une relation de la forme: PM = ((x_M - x_P)² + (y_M - y_P)²)^1/2 .

Plusieurs méthodes sont envisageables, par exemple:
1°) Un calcul de coordonnées partant de la construction géométrique de (F), donné comme point de concours de 3 droites.

2°) La recherche par un calcul itératif du point limite correspondant au minimum de la somme des trois distances: S_M = MA + MB + MC .
Là aussi, deux possibilités:
a) la recherche "aveugle" de la plus basse valeur de S(x, y) au voisinage d'un point donné (M), en partant de l'isobarycentre (G), par comparaison des 4 valeurs observées aux sommets d'un petit carré centré en (M):
S₁(x+h, y) , S₂(x-h, y) , S₃(x, y+h) , S₄(x, y-h) - comparaison entre elles et avec la valeur centrale S_M = S₀(x, y) ;
si la valeur minimale ne se trouve pas au centre (M), passer au point voisin correspondant, sinon rester en (M), et prendre un incrément plus petit (h' = h / 10);
poursuivre l'opération jusqu'à ce que l'on passe en-dessous du seuil de précision demandé (h < 10^-8 ? 10^-12 ? 10^-16 ?) - cela dépend du format des variables Float employées;
on prendra pour le pas initial une valeur simple (h₀ = 1, 0.1, ...) très inférieure aux dimensions du triangle : h₀ <~ 0.1 * Min(GA, GB, BC) .

b) le calcul de petits déplacements successifs dans le plan (qui fait implicitement intervenir le vecteur gradient Grad(S)), sachant qu'une variation élémentaire de la somme S(x, y) admet pour expression:
dS = d(AM) + d(BM) + d(CM) = ((1/AM)*AM + (1/BM)*BM + (1/CM)*CM)|dOM) = (Grad(S)|dOM) ;⁽¹⁾
un rapprochement systématique vers le minimum de (S) à partir de la position courante (M) sera obtenu par un petit déplacement de la forme:
MM' = -k * Grad(S) , avec un coefficient suffisamment faible (k > 0 , k ~ 0.01 ? 0.001 ? ...) pour que là encore le déplacement effectué soit petit devant les dimensions du triangle (MM' << Min(GA, GB, BC) ;
chaque étape s'accompagne dans ce cas d'une diminution de la somme des distances: dS = -k * (Grad(S)|Grad(S)) = -k * ║Grad(S)║² < 0 .

(1): la notation (.|.) représente le produit scalaire de deux vecteurs.

# Le second procédé (2a) est le plus simple à mettre en oeuvre.

[eminatta]

Merci beaucoup de votre aide j'ai ENFIN réussi !