Discussion :

[Taupin21]

Bonjour à tous,

Je suis en deuxième année de prépa scientifique et travaille en binôme pour l'épreuve de TIPE sur l'optimisation des réseaux d'irrigation.
Nous travaillons avec Python et connaissons des difficultés.

A ce stade, nous disposons d'une liste de sources et de puits (départ et arrivées d'eau) avec leurs coordonnées. Notre problématique actuelle est d'écrire un algorithme nous permettant de trouver le point de Fermat de 3 points afin de minimiser la longueur des canaux nécessaires.

Au cours de notre recherche, nous avons essayé de résoudre le problème par des équations de droites, mais cela semble bien compliqué !
Nous avons ensuite étudié cet algorithme qui revient très souvent lors de nos recherches :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
def median_approx(X):
    (x,y) = (0,0)
    n = len(X)
    W = 0
    for k in range(n):
        dx = (x - X[k][0])**2
        dy = (y - X[k][1])**2
        dist = math.sqrt(dx + dy)
        w = 1.0 / dist
        W += w
        x += X[k][0]*w
        y += X[k][1]*w
    return x/W, y/W

(où X est la liste des coordonnées des 3 points)

Mais il semblerait que cet algorithme calcule les coordonnées du barycentre, ce qui ne correspond pas exactement au point de Fermat...

Quelqu'un pourrait-il nous éclairer ?

Merci d'avance

[picodev]

Bonjour

https://mgje.github.io/presentations...rmat-Weber.pdf

[Taupin21]

Merci pour votre réponse,

Ce lien fait partie de ceux que nous avons trouvé et l'algorithme en question est un de ceux sur lesquels nous avons le plus travaillé mais nous ne le comprenons pas...

L'algorithme "distance(A,B)" calcule la distance entre 2 points A et B
L'algorithme Schwerpunkt calcule comme son nom l'indique le centre de gravité...

Mais alors quelle est la différence avec l'algorithme "median_approx" et en quoi permet-il de trouver le point de Fermat ??

[picodev]

Alors il y a aussi la présentation interactive.

Le point de Fermat est ce qui est appelé la médiane géométrique (geometric median en anglais).
Dans le cas N=3 on peut trouver le PF (je reprends les notations de la présentation) facilement avec un des algorithmes qu'on trouve sur la page wikipedia.
Pour le cas N=4 si un des points est à l'intérieur d'un triangle formé par les trois 3 autres alors il est le PF sinon c'est l'intersection des diagonales.

Dans la présentation, le centre de gravité CM (Schwerpunkt) n'est là que pour illustrer les propos, montrer que non seulement CM est différent de PF mais qu'il réagit aussi différemment lorsqu'on déplace un des N points.

L'algorithme de Weiszfeld est donc un algorithme d'approximation. On commence par choisir un point P «au hasard», ici on prend comme abscisse la moyenne des abscisses des N points et comme ordonnée la moyenne des ordonnées des N points. Ensuite on applique à ce point l'algorithme d'approximation jusqu'à ce que distance(P_avant,P_après) < 𝜀. Il peut ne pas converger tout le temps.

Il y a une liste d'algorithmes dans Geometric Median in Nearly Linear Time.

[tbc92]

Le point de Fermat n'est pas le centre de gravité.
Sur la page Wikipédia, on parle du cas particulier où un des angles fait plus de 120°. Dans ces triangles, le point de Fermat est le sommet en question.

Par contre le centre de gravité n'est jamais un des sommets. Je ne sais pas si tu "visualises" ce qu'est le centre de gravité, mais de façon évidente, il n'est jamais sur la frontière du triangle.

Edit :
Allons plus loin.
Dans le cas de n points ( avec n > 3), la rechercher du point de Fermat passe par un algorithme récursif , ok.
Mais dans le cas du triangle, on doit pouvoir bâtir un système de 2 équations à 2 inconnues qui nous donne les coordonnées du point en question en une seule étape.

Si on suit la construction du point telle que décrite ici http://www-irem.univ-fcomte.fr/downl...torricelli.pdf dans le 1er schéma , les points A', B' et C' sont faciles à calculer ; les équations des droites A A' , B B' et C C' sont faciles à calculer, et l'intersection de ces 3 droites donne le point recherché. Magie des triangles, les 3 droites se croisent en un seul et même point.
Et dans le cas particulier où un des sommets fait plus de 120°, la solution est encore plus simple.

Ce problème a donc une solution 'algorithmique', ou une solution 'mathématique', au choix.

Edit : Ce que j'ai ajouté correspond exactement à la suggestion de Anapurna

[anapurna]

salut

pour trouver le point de Fermat il aurait été peut être plus facile d'utiliser la méthode de TORRICELLI

c'est a dire définir des triangles équilatéraux pour chaque coté définir le cercle circonscrit a chaque nouveau triangle
et le point d'intersection de ces cercles correspond au point de Fermat

[Prof]

Bonjour.

Si j'ai bien compris la problématique du TIPE, il s'agit de trouver le réseau le plus court reliant n points.

Dans ce cas, le problème est connu et s'appelle le problème de Steiner,
plus précisément le "Steiner tree problem", soit en français le "problème de l'arbre de Steiner".

Voir Wikipédia en français : https://fr.wikipedia.org/wiki/Probl%...bre_de_Steiner
mais les sites en anglais sont plus nombreux et plus complets,
par exemple : http://www.math.ucsd.edu/~ronspubs/14_02_Steiner.pdf

Pour n = 3, le réseau le plus court utilise le point de Fermat.

Mais c'est faux pour n >= 4.
La page Wikipédia citée plus haut montre le cas n = 4 : le réseau le plus court utilise 2 points de Steiner.
( dans le cas d'un carré, le réseau utilisant le point de Fermat a une longueur d'environ 2.828,
alors que le réseau utilisant les 2 points de Steiner a une longueur d'environ 2.732 )

Le problème de l'arbre de Steiner est NP-difficile ( Garey 1977).
Il est donc exclu d'en chercher la solution exacte lorsque n est grand.

L'algorithme de Melzak (1961) réduit le problème à n points en sous-problèmes comportant moins de points,
que l'on relie ensuite par un ou plusieurs points supplémentaires.

Cet algorithme a été amélioré par Cokayne (1967) puis d'autres chercheurs dont Warme (1998).
Voir une présentation du GeoSteiner algorithm : http://www.geosteiner.com/papers/JWW...-Challenge.pdf
qui permet d'obtenir en temps polynomial une solution approchée du problème de Steiner.

En résumé, le point de Fermat pour 3 points n'est que la première étape d'une randonnée plutôt longue ...

[Taupin21]

Merci beaucoup Picodev, j'ai enfin compris la différence entre le CM et le PF et l'algorithme de Weiszfeld !

Tbc92 et Anapurna, ma partenaire est en train de travailler avec les équations de droites pour résoudre le problème de cette manière et je vais de ce pas me pencher également dessus. Merci de votre aide !

[Taupin21]

Oups...

Bon le problème est résolu pour 3 points, nous allons maintenant nous concentrer sur le problème de l'arbre de Steiner, merci beaucoup pour la documentation nous allons nous pencher dessus au plus vite !