Distance la + grande d'un polygone variable à 3 branches
Bonjour,
Soit un parcours defini par un ensemble de points dans un plan.
Pd=(Xd, Yd) et Pa=(Xa, Ya) étant les points de Départ et d'Arrivée.
Je cherche à trouver 2 points P1=(X1, Y1) et P2=(X2, Y2) tels que la somme des distances PdP1, P1P2 et P2Pa soit la plus grande possible.
Mes souvenirs en math datent de plus de 15 ans et même la bicyclette s'oublie...
bonsoir
pour répondre à la question il faudrait peut être la forme et les limites du plan. sinon on peut placer n'importe où les points à l'infini. enfin il me semble.
C'est un parcours, donc la projection des points P1 et P2 sur l'axe passant par Pd et Pa est dans le segment PdPa.
je cherche le max de
(X1-Xd)^2+(X2-X1)^2+(Xa-X2)^2+(Y1-Yd)^2+(Y2-Y1)^2+(Ya-Y2)^2
Bonsoir,
D'abord une petite remarque : ce que tu a développé, c'est la somme du carré des distances et non la somme des distances. Leur max ne seront pas exactement les mêmes.
Encore qu'avec la condition que tu poses...
Comme l'a fait remarquer manup, on peut trouver un mini mais le maxi, c'est l'infini.
Pour préciser un peu plus, plaçons les projetés de P1 et P2 sur la droite PdPa et notons h1 et h2 les distances des deux points à leur projetés respectifs.
On voit bien que plus h1 et h2 seront grands, plus la distance totale le sera.
Et ta condition ne fixe aucune limite à ces distances..
Dans la mesure où c'est un parcours (sur terre je présume), il faudrait placer h1 à 13 300 Km de distance selon un grand cercle et h2 à 26 700Km (dans le même sens). Reste le problème du passage des autoroutes et des océans
Bonjour,
1)Bonne remarque Zinia, en effet on s'intéresse à la somme des distances et pas à celle de leur carré.
2)Je me suis mal exprimé: le parcours est fixé. Le nombre (N) et la position (X,Y) des points sont connus. On est sur un plan euclidien. Donc tout ce qu'il y a de plus simple.
3)La réponse simple est :
Pour chaque point du parcours fixé on prend les (m-1) autres points, on calcule la somme des distances et l'on garde en mémoire la somme max. (m variant de N à 2.)
N'y a-t-il pas un moyen d'optimiser cet algo sachant qu'il y a peu de distance entre 2 points du parcours (les max locaux sont insignifiants pour une premiere approx)?
Je pensais au mm algo en prenant 1 point/4 ou 1/16 pour faire une premiere approximation, puis refaire le calcul avec tous les points autour des candidats.
Merci de vos réponses
