Calculer le point de Fermat d'un triangle
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
Calculer le point de Fermat d'un triangle
Bonjour, :D
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 = ((xM - xP)2 + (yM - yP)2)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: SM = 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):
S1(x+h, y) , S2(x-h, y) , S3(x, y+h) , S4(x, y-h) - comparaison entre elles et avec la valeur centrale SM = S0(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 (h0 = 1, 0.1, ...) très inférieure aux dimensions du triangle : h0 <~ 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) ;(1)
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)║2 < 0 .
(1): la notation (.|.) représente le produit scalaire de deux vecteurs.
# Le second procédé (2a) est le plus simple à mettre en oeuvre.
