calcul de la position d'un point équidistant de 4 autres
Sébastien de Mapias
Mettons 4 villes: Paris, Bruxelles, Zürich et Marseille, j'aimerais
savoir OÙ se trouve l'endroit à -plus ou moins- égale distance
de chacune de ces 4 villes...
En faisant un printscreen d'une carte d'Europe, et en baladant
ensuite mon curseur sur l'image dans un programme qui m'en
donne les coordonnées en pixels, j'ai à peu près les positions
suivantes pour les 4 (Paris est sur l'ordonnée et Marseille sur
l'abscisse, et ATTENTION avec ce soft l'origine 0,0 est en haut
à gauche -!!-):
Paris: 0,60
Bxl: 43,6
Marseille: 54,230
Zürich: 94,123
C'est difficile à calculer ? (j'ai tout oublié en maths, et de toute
manière je n'étais pas un champion...)
Merci mille fois...
Sébastien
Philippe 92
> Bonjour,
>
> Mettons 4 villes: Paris, Bruxelles, Zürich et Marseille, j'aimerais
> savoir OÙ se trouve l'endroit à -plus ou moins- égale distance
> de chacune de ces 4 villes...
> C'est difficile à calculer ? (j'ai tout oublié en maths, et de toute
> manière je n'étais pas un champion...)
>
Tu cherches donc le centre d'un cercle qui passe par 4 points...
Par exemple
.
. A
.
.
. D
.
. B C
.
Il va être difficile de faire passer un cercle par ces 4 points !
Même "à peu près".
Amicalement.
--
Philippe C., mail : chephip
avec free.fr comme domaine
site : http://mathafou.free.fr/ (divertissements mathématiques)
Sébastien de Mapias
suivante:
> . B
> . P
> .
> . Z
> .
> . M
Olivier Miakinen
> Non car avec ces 4 villes on a +/- la config
> suivante:
>> . B
>> . P
>> .
>> . Z
>> .
>> . M
autre trio de points).
de suite pour tout
pas par B (et ainsi
et Z ne passera
passant par P, M
pareil : un cercle
Eh bien c'est
P.-S. :
http://www.usenet-fr.net/fur/usenet/repondre-sur-usenet.html
Philippe 92
> Le 11/03/2009 19:32, Sébastien de Mapias a écrit :
>> de chacune de ces 4 villes...
>
> Eh bien c'est
;-)
Bonjour,
Comme deja dit il n'y a aucune chance que 4 points quelconques
soient sur un même cercle.
Reste que Sébastien a dit "plus ou moins" c'est à dire qu'il faut
envisager qu'il s'agit d'un problème d'optimisation :
trouver un point P tel que les distances de P aux 4 villes soient
les plus proches possibles.
Si on appelle r la valeur moyenne de la distance de P au 4 villes,
on peut prendre ce r comme rayon du cercle (qui n'a aucune chance
de passer par une des villes, a fortiori par les 4).
La qualité du choix de P peut alors être mesurée ici par sigma,
racine carrée de la moyenne des carrés des différences
entre les distances réelles et la valeur moyenne r
(moindres carrés).
Si les 4 points sont sur un même cercle, en plaçant P au centre
de ce cercle, on obtient bien entendu sigma = 0.
L'optimum (ici expérimental 1er dessin, sigma = 11.014) ne semble
pas satisfaisant "à l'oeil", c'est pourtant meilleur que si on
cherche au pif un cercle qui "semble le plus voisin" (2eme dessin
sigma = 12.132) et bien meilleur que si on place P au centre de
gravité des 4 points (3eme dessin sigma = 14.679).
De toute façon l'optimum ne se calcule pas par une formule,
mais par un algorithme d'optimisation.
On devrait trouver ça sur le Web : recherche de la sphere la plus
représentative d'un nuage de points (ici on est en 2D, mais il
y a plus de billes en 3D). Que notre nuage ne comporte que 4 points
ne devrait pas déranger l'algorithme général.
Le principe le plus général est de choisir un point au hasard
(le centre de gravité est facile à calculer et c'est un point
de départ comme un autre) Puis de faire évoluer ce point pour
améliorer la solution (simplexe, gradient, recuit simulé etc...).
claude
ac49-295...@40g2000yqe.googlegroups.com:
> C'est difficile à calculer ?
Tu cherche le centre de gravité d'un quadrilatère.
claude
Olivier Miakinen
>
> Tu cherche le centre de gravité d'un quadrilatère.
Non, pas du tout ; cf. la dernière réponse de Philippe 92.
Pour te prouver à quel point ça peut être faux, considère un cercle de
centre O, et quatre points situés exactement sur ce cercle, mais tous
les quatre très près les uns des autres (mettons par exemple des points
distants de moins d'un mm sur un cercle d'un m de rayon) : le centre de
gravité sera lui aussi très près de ces points, soit à un mètre du
centre du cercle cherché, O.
martin68
Pour 3 points c'est le centre du cercle circonscrit (point
d'intersection des médiatrices) et non le centre de gravité qu'il faut
chercher.
Or rien ne garantie que le centre de gravité d'un quadrilatère
corresponde au centre du cercle circonscrit à un triangle formé avec 3
des sommets de ce quadrilatère.
Pour pouvoir répondre au problème il faudrait commencer par redéfinir
cette phrase: "j'aimerais savoir OÙ se trouve l'endroit à -plus ou
moins- égale distance de chacune de ces 4 villes"
L'idéal serait que l'auteur de la question nous précise ce qu'il cherche
à faire exactement, si c'est pour choisir l'emplacement de son futur
domicile la question n'a aucun intérêt pour plusieurs raisons, la plus
importante étant qu'il est plus important de tenir compte des trajet par
les voies de communication existantes vu que l'on ne se déplace pas par
vol d'oiseau. Une autre raison serait que la recherche du secteur
optimal pour minimiser les déplacements ne dépend absolument pas du fait
que le point de relais (domicile ou entreprise) soit situé à égal
distance des points à rejoindre.
Martin
claude
@free.fr:
> bien meilleur que si on place P au centre de
> gravité des 4 points (3eme dessin sigma = 14.679).
>
> http://cjoint.com/?dokUVXzDPy
Que représente le PA,PB,PC et PD du 3e dessin.
Pouquoi mes résultats des distance sont ... ?
GA = 77.08
GB = 109.55
GC = 115
GD = 40.79
claude
news:Xns9BCF9F3CB85...@216.196.97.131:
> Que repr‚sente le PA,PB,PC et PD du 3e dessin.
> Pouquoi mes r‚sultats des distance sont ... ?
> GA = 77.08
> GB = 109.55
> GC = 115
> GD = 40.79
Il y a une erreur dans la macro que j'ai utilisé.
claude
Philippe 92
>> Philippe :
>>> PA = 65.795 (sur le dessin)
>>
>> Que représente le PA,PB,PC et PD du 3e dessin.
>> Pourquoi mes résultats des distance sont ... ?
>> GA = 77.08
>
> Il y a une erreur dans la macro que j'ai utilisé.
Bonjour,
Mes dessins ont été fait par un logiciel de géométrie
en lui demandant d'afficher les mesures à partir de P, point
libre déplaçable. J'avais positionné P en G "à la main" pour le 3ème
dessin.
A la calculette cela donne :
Xg = (0+43+54+94)/4 = 47.75
Yg = (60+6+230+123)/4 = 104.75
GA = sqrt( (0 - 47.75)^2 + (60 - 104.75)^2 ) = 65.44176...
En mettant P en G par le programme (move P to G), j'obtiens bien
PA = 65.442 affichés.
Sinon entre temps j'ai trouvé des infos intéressantes sur le cercle
passant au mieux par n points (hélas en anglais) :
<http://www.orbitals.com/self/least/least.htm>
Et une applet :
<http://cauchy.math.colostate.edu/Applets/BestCircle/bestcircle.html>
claude
@free.fr:
> A la calculette cela donne :
> Xg = (0+43+54+94)/4 = 47.75
> Yg = (60+6+230+123)/4 = 104.75
Le centre de gravité n'est plutot (47.931526 , 109.120877)
Aire = 10181,5
claude
claude
news:Xns9BD05A817A6...@216.196.97.131:
C'est un polygone irrégulier.
Philippe 92
> "Philippe 92" <nos...@free.invalid> :
>
>> A la calculette cela donne :
>> Xg = (0+43+54+94)/4 = 47.75
>> Yg = (60+6+230+123)/4 = 104.75
>
> Le centre de gravité n'est plutot (47.931526 , 109.120877)
>
Je parle du centre de gravité (isobarycentre) des SOMMETS, pas de
celui de la surface du quadrilatère.
L'objectif était de choisir un point de départ facile à calculer,
pour les itérations.
L'isobarycentre de la surface du quadrilatère est aussi peu
représentatif que l'isobarycentre des sommets en ce qui concerne le
"meilleur" cercle, et même moins !
Il est par contre plus compliqué à calculer.
claude
@free.fr:
> Il est par contre plus compliqué à calculer.
La commande CentreGravité de GeoGebra calcule le centre de gravité d'une
surface d'un polygone.
http://cjoint.com/data/dsrWBeQjkM.htm
claude
Olivier Miakinen
>
>> Il est par contre plus compliqué à calculer.
>
> La commande CentreGravité de GeoGebra calcule le centre de gravité d'une
> surface d'un polygone.
Il reste que ça ne répond nullement à la question initiale dans laquelle
il était question de points et pas de surface.
Déjà, pour pouvoir transformer un ensemble de points en un polygone, tu
dois leur attribuer un certain ordre : si tu as les points A, B, C, D et
E, pourquoi décider de considérer le polygone ABCDE plutôt que ACEDB ou
ABDEC par exemple ? Le centre de gravité des points ne dépend nullement
de cet ordre, alors que celui du polygone, oui.
zwim
Philippe 92 a écrit
A vue de nez le centre de gravité des 4 centres des cercles
circonscrits des villes prises 3 par 3 ne devrait pas donner de trop
mauvais résultats.
En gros l'idée étant que le meilleur point pour 3 villes est le centre
du cercle circonscrit, que ces 4 centres sont "à priori plus
rapprochés que les 4 points de départ" (en fait j'en suis pas du tout
certain), donc que leur barycentre doit être un compromis pas vilain à
la question posée.
Et l'avantage c'est qu'on peut trouver une formule explicite (quoique
compliquée, mais rien de bien méchant pour un ordi) pour le calculer.
C'est possible de programmer ça facilement dans ton logiciel ?
--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...
Philippe 92
> Le Thu, 12 Mar 2009 11:29:41 +0100
> Philippe 92 a écrit
>>>> Mettons 4 villes: Paris, Bruxelles, Zürich et Marseille, j'aimerais
>>>> savoir où se trouve l'endroit à -plus ou moins- égale distance
>>>> de chacune de ces 4 villes...
>>
>> les plus proches possibles.
>>
>> mais par un algorithme d'optimisation.
>
> circonscrits des villes prises 3 par 3 ne devrait pas donner de trop
> mauvais résultats.
> C'est possible de programmer ça facilement dans ton logiciel ?
Bonjour,
Mon logiciel est un programme de dessin, il ne sait pas calculer des
Jacobien et autres régressions non linéaires, donc ne sait pas trouver
l'optimum. L'optimum est obtenu "à la main" en déplaçant P pour réduire
l'erreur.
Quant à ton centre de gravité des centres des cercles circonscrits...
Prenons 3 points B,C,D relativement proches et presque alignés,
Le cercle le plus proche de A,B,C,D est un cercle en gros de
diamètre A-(B,C,D).
Alors que le cercle circonscrit à ABC a un rayon énorme (infini),
son centre est très éloigné, et le centre de gravité avec 3 points
à distances finies est malgré tout très loin :
(infini + x2 + x3 + x4)/4 = infini (heu sans rigueur particulière
sur "infini = ")
<http://cjoint.com/?ebnQvuMr6z>
Comme mon applet ne sait pas tracer des points à l'infini et
des cercles qui soient des droites, le centre de gravité G1 des
centres des cercles circonscrits n'est ici pas si loin que ça,
mais suffisemment loin du théatre des opérations pour que ce soit
visiblement un mauvais candidat !
Les points cyan sont les centres des cercles circonscrits, l'un
est en dehors de la figure. P est le centre du cercle optimal
et presque confondu avec le centre du cercle (ABC).
zwim
Philippe 92 a écrit
Ah oui, je n'avais pas pensé à ce cas là.
Merci d'avoir fait la figure.
Cela dit le centre de gravité des 3 centres restant est pas mal, mais
ça reste une approche pifométrique...
>Comme mon applet ne sait pas tracer des points à l'infini et
>des cercles qui soient des droites, le centre de gravité G1 des
>centres des cercles circonscrits n'est ici pas si loin que ça,
>mais suffisemment loin du théatre des opérations pour que ce soit
>visiblement un mauvais candidat !
>Les points cyan sont les centres des cercles circonscrits, l'un
>est en dehors de la figure. P est le centre du cercle optimal
>et presque confondu avec le centre du cercle (ABC).
>
>Amicalement.
--
Valeri Astanoff
[...]
Bonjour,
Ce qui suit est juste pour montrer que,
si on minimise la variance des distances
aux 4 points, ce cas pathologique ne
pose pas de problème à un logiciel comme
Mathematica ou équivalent :
In[1]:= points={{0,0},{1,0.001},{1,0},{1,-0.001}};
In[2]:= $Assumptions = (x|y) \[Element] Reals;
In[3]:= v = Variance[Norm[#-{x,y}]& /@ points]//Simplify;
In[4]:= Minimize[v,{x,y}]//N//Chop
Out[4]= {0, {x -> 0.5, y -> 0}}
V.Astanoff
arno...@gmail.com
Nicolas de la Ruelle
C'est le terme "à peu près" qui me dérange. Peut-être le but serait de
trouver le point dont la somme des distances aux quatre villes est minimum.
Sinon, en termes d'égalité stricte, par trois points non alignés passe
un seul cercle, dont le centre est l'intersection de deux médiatrices
des segments entre ces points, donc aucun choix possible, pour 3 villes,
c'est le centre de ce cercle.
ensuite, il reste à croiser les doigts et espérer un "gros coup de pot"
improbable, que la 4ème ville soit également sur ce cercle.
L'absence de virus dans ce courrier électronique a été vérifiée par le logiciel antivirus Avast.
https://www.avast.com/antivirus
Nicolas de la Ruelle
G[(1/4)(x1+x2+x3+x4);(1/4)(x1+x2+x3+x4)] , et pour s'amuser un peu plus,
en pondérant les coordonnées par un coefficient selon la difficulté pour
atteindre ces villes, au delà de simplement la distance.