point central d'un nuage de points (barycentre?)

jl.virmoux

XLDnaute Nouveau
Bonjour,
Je cherche comment trouver le point qui se situe le plus près possible de tous les points d'un nuage de points.(barycentre)
Soit x(1,1), x1(1,3), x2(3,1), x4(3,3) y sera en (2,2).
Mes points (environ 400) sont des coordonnées en latitude et longitude, et la question est de savoir ou se trouve le lieu qui est au plus proche de tous les autres.
Pour bien faire le calcul devrait être fait en fonction des routes et non en ligne droite en utilisant google maps mais ça c'est une autre histoire.

Je vous remercie par avance pour vos réponses
 

ROGER2327

XLDnaute Barbatruc
Re : point central d'un nuage de points (barycentre?)

Bonsoir
À Risleure
(...) les coordonnées du barycentre ne sont-elles pas les cordonnées moyennes des abscisses et des ordonnées ?
Certainement, si tous les points sont affectés du même coefficient (souvent appelé "poids").
Mais, si les points sont affectés de poids différents, les coordonnées du barycentre sont les moyennes pondérées des coordonnées des points.​
À jl.virmoux
Mes points (environ 400) sont des coordonnées en latitude et longitude, et la question est de savoir ou (où) se trouve le lieu qui est au plus proche de tous les autres.
Facile à dire ! Mais qu'entendez-vous par "le lieu qui est au plus proche de tous les autres" ? S'il s'agit de minimiser la somme des distances du point cherché à chacun des 400 points (!) que vous envisagez, le barycentre n'est (sauf cas très particulier) certainement pas le bon candidat. Considérez, par exemple, les points de coordonnées
( 0 ; 4 )
( 12 ; 0 )
( 12 ; 4 )
( 12 ; 8 )​
Leur barycentre équipondéré a pour coordonnées
( 9 ; 4 )​
La somme des distances de ce point au quatre autres est 22.
Or il existe une infinité de points globalement plus proches des quatre autres : le point de coordonnées ( 12 ; 4 ), par exemple. La somme des distances de ce point au quatre autres est 20.
En vérité, vous vous attaquez à un problème extrêmement difficile dès lors que le nombre de points devient important. Si vous trouvez une solution explicite (i.e. une formule, même compliquée) à ce problème, je pense que votre fortune est faite.
Bon chance !​
ROGER2327
 

jl.virmoux

XLDnaute Nouveau
Re : point central d'un nuage de points (barycentre?)

Bonjour Roger2327,
Merci de votre intérêt. Je ne suis effectivement pas sûr du barycentre, c'est pourquoi j'y avais mis un point d'interrogation.
Je pense aussi à la fonction vectorielle de Leibniz, mais là c'est bien trop fort pour moi.
Il y aussi la possibilité de travailler sur la droite de régression de ces points, ou de plusieurs droites non?
Comment faites vous pour calculer la somme des distances et trouver la plus petite somme?
Le problème est de trouver le positionnement idéal d'une plateforme logistique agricole en fonction de l'emplacement de 400 petits producteurs bio.
Objectif: limiter les déplacements et le nombre de kilomètres parcourus afin de réduire les émissions de Co2. Développement durable
Et il y a évidement à prendre en compte des éléments qui ne peuvent pas être traduits mathématiquement, comme la disponibilité d'un terrain pour construire aux alentours de ce point, s'il existe.
Merci en tous cas
 

ROGER2327

XLDnaute Barbatruc
Re : point central d'un nuage de points (barycentre?)

Bonjour à tous
À jl.virmoux
Je trouve votre problème fort intéressant, et, quoi que n'étant pas capable de le résoudre, j'apporte ici une contribution qui, peut-être, vous permettra d'avancer. Dans le classeur que je joins, j'ai installé les coordonnées de quatre cents points. J'ai calculé les coordonnées de l'équibarycentre (point B) et j'ai calculé les coordonnées d'un point M tel que la somme des distances de ce point au quatre cents points choisis soit minimum. En l'absence d'une formule explicite, j'ai utilisé le résoluteur (appelé "solveur" par Microsoft®) livré avec Excel®. Vous verrez que ce point ne coïncide généralement pas avec l'équibarycentre.​
Pour observer ce qui se passe, j'ai fabriqué un générateur arbitraire pour engendrer les coordonnées des quatre cents points. Les formules employées sont dans les cellules A1 et B1. On peut les modifier à volonté. Un jeu de points s'obtient en cliquant sur GÉNÉRATEUR.​
Le bouton RÉSOLUTEUR permet de calculer les coordonnées du point M.​
Le bouton ESSAI combine les deux autres : il crée un jeu de points et calcule les coordonnées du point M associé.​
Une représentation graphique permet de visualiser les points.​
Vous pouvez utiliser ce modèle avec vos propres données (à placer sous X et Y). Une fois les données installées, cliquez sur RÉSOLUTEUR.​
Veuillez noter que, sous certaines conditions, le résoluteur peut donner un résultat erroné. En effet, il cherche le point M au voisinage du point B. Mais rien ne dit a priori qu'il n'existe pas, loin du point B, un point donnant un meilleur résultat. On dit que le résoluteur cherche un minimum "relatif" qui n'est pas nécessairement un minimum "absolu". Pour donner une analogie, imaginez une surface bosselée sur laquelle on laisse tomber des gouttes d'eau. Par gravité, chaque goutte va se loger au plus profond d'un creux ; elle atteint un minimum d'altitude. Mais, si les creux n'ont pas tous la même profondeur, ce minimum dépend de l'endroit où elle est tombée. Le résoluteur a un comportement semblable : à partir des coordonnées qu'on lui donne (ici celle du point B) il "glisse" vers un point donnant un meilleur résultat (le point M). En partant des coordonnées d'un autre point que l'équibarycentre, peut-être "glisserait"-t-il vers un point donnant un meilleur résultat. Prudence, donc...​
Vous pouvez éventuellement mettre des valeurs quelconques sous MX et MY et actionner le résoluteur. Si, répétée de nombreuses fois avec des valeurs très différentes, la manipulation vous donne toujours le même point M, vous pouvez espérer avoir trouvé le "bon" point M...
Enfin, le modèle que je vous fourni n'est pas très élaboré. On peut facilement l'améliorer en pondérant chaque point en fonction du volume de transfert attendu de chaque point au point M, ou en fonction d'autres paramètres liés à vos contraintes. À vous de voir...​
C'est tout ce que je peux vous proposer à partir des informations en ma possession. Bon courage pour la suite.​
ROGER2327
__________________
P.S. : ce travail prenant un certain temps, voire un temps certain, veuillez me faire savoir s'il vous intéresse. Si vous décidiez de vous orienter vers une autre solution, merci de me le faire savoir.
 

Pièces jointes

  • Optimiser_les_distances.zip
    15.8 KB · Affichages: 906
Dernière édition:

jl.virmoux

XLDnaute Nouveau
Re : point central d'un nuage de points (barycentre?)

Bonsoir Roger2327,
Quel travail!! Vous avez vraiment bossé sur mon problème et c'est proche de ce que je cherche.
j'ai juste un problème je crois qu'il me manque le solveur dans Excel 2007 car j'ai une erreur "projet ou bibliothèque introuvable" et le déboggeur s'arrête sur "solver".
je vais chercher.
Vous avez raison je dois aussi je pense pondérer chaque point sur le volume de transfert attendu et le temps réel de trajet.
je vous remercie beaucoup de votre participation.
je vous tiendrai informé de mes recherches
cordialement.
 

ROGER2327

XLDnaute Barbatruc
Re : point central d'un nuage de points (barycentre?)

Re...

Avec la version 2003, il y a effectivement une "bibliothèque" à activer pour disposer des fonctionnalités du "solveur", mais j'ignore comment procéder avec la version 2007.

ROGER2327
 

achambily

XLDnaute Nouveau
Re : point central d'un nuage de points (barycentre?)

Bon ben je vais devenir riche alors ?!

Le point que vous cherchez n'est pas le barycentre (celui-la minimise néanmoins la somme des carrés des distances - la fonction scalaire de Leibniz -).

La solution, c'est le point qui minimise la variance de l'ensemble des distances possibles.
J'ai tout bien expliqué ça ici :

www.chambily.com, le site d'Axel Chambily - Casadesus

;-)
 

XLVERSI

XLDnaute Nouveau
Re : point central d'un nuage de points (barycentre?)

Salut jl.virmoux je pense que je recherche la même chose que toi.
Mon probleme c'est que j'ai une carte sur google maps avec différents membres et j'aimerais bien trouver le point central.
Par la route c'est sur que ça paraitrait le mieux mais ça demandrait une puissance de calcul phénoménale pour trouver le point central.
Ce que je vais faire c'est extraire le fichier KML de la carte, récupérer les coordonées comme je peux, et faire la moyenne des latitude et la moyenne des longitudes. J'arriverai à un point géographique central.

Sinon, t'en es tu sorti ? de quelle manière ?

Merci
 

XLVERSI

XLDnaute Nouveau
Re : point central d'un nuage de points (barycentre?)

Alors je me suis occupé de ma carte et ça a marché. Je pense que le barycentre est le meilleur compromis
Il correspond bien à un point moyen (latitude du barycentre = latitude moyenne, et longitude du barycentre = longitude moyenne).

Un exemple pour étayer tout ça:
Dans un triangle le barycentre est le centre de gravité, c'est à dire le le plus juste milieu.
Mais ce n'est pas le point équidistant aux trois sommets. Celui là est représenté par les médiactrices. Ce sera un point équidistant mais c'est un point qui peut être très loin aussi (donc pas toujours intéressant au final).

Une fois un barycentre trouvé avec la méthode plus il faudrait choisir une série de villes autour de ce barycentre et trouver celle qui donne la moyenne la plus faible entre tous les points du nuage et ce "barycentre arrangé"

Voilà la macro finale qu'on cherchait; on rentre une série de points et nous calcules les distances sous google maps:
Ce lien n'existe plus

J'ai donc extrait toutes mes coordonnées GPS du fichier KML, je les ai mises dans la feuille excel et j'ai fait des tests avec toute une série de ville (plus ou moins proche de mon barycentre, ou plus ou moins proche de ma médiane, et après plus loin).
Le plus intéressant est donc à la fin de calculer une moyenne de la distance de tous ces points par rapport au barycentre choisi et de calculer aussi l'écart type.
Pour comparer avec l'exemple du triangle. Le point qui a la moyenne la plus faible est le "barycentre". Le point qui a l'écart type le plus faible est l'intersection des médiatrices. Il faut trouver un compromis entre les deux.

Mon barycentre géographique se trouvait dans la Nièvre.
Mon barycentre routier était Beaune.
Ma médiane était vers Troyes.
C'est à Moulins (ou Montluçon je ne sais plus) que j'ai l'écart-type le plus faible.

Le meilleur compromis jusque là est Autun. C'est une ville dont la somme de la moyenne et de l'écart type est le plus faible, ça fait un peu bricolage mais je suis plutôt content de mes résultats au final.
Ce qui est intéressant c'est qu'une ville comme Courtenay (un peu après Nemours) bien que très loin d'Autun a eu de très bons résultats aussi.
 
Dernière édition:

Discussions similaires

Statistiques des forums

Discussions
311 720
Messages
2 081 910
Membres
101 837
dernier inscrit
Ugo