calcul de la position d'un point équidistant de 4 autres

[Sébastien de Mapias]

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...

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]

Post by Sébastien de Mapias
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...
[exemple]
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.

[Sébastien de Mapias]

Non car avec ces 4 villes on a +/- la config

. B
. P
.
. Z
.
. M

Post by Sébastien de Mapias
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...
[exemple]
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)

[Olivier Miakinen]

Post by Sébastien de Mapias
Non car avec ces 4 villes on a +/- la config

. 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]

Post by 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...

pareil : un cercle ...
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).

http://cjoint.com/?dokUVXzDPy

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...).

Amicalement.

[claude]

Post by Philippe 92
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]

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]

Post by claude

Post by claude

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>

Amicalement.

[claude]

Post by Philippe 92
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:mn.823c7d9389886cde.22155

Post by claude

Post by Philippe 92
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

C'est un polygone irrégulier.

http://pagesperso-orange.fr/math.15873/page9.htm

[Philippe 92]

Post by claude

Post by Philippe 92
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.

Amicalement.

[claude]

Post by Philippe 92
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]

Post by claude

Post by Philippe 92
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]

Le Thu, 12 Mar 2009 11:29:41 +0100
Philippe 92 a écrit

Post by Sébastien de Mapias

Post by 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...

pareil : un cercle ...
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
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).
http://cjoint.com/?dokUVXzDPy
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...).
Amicalement.

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 ?

[Philippe 92]

Post by zwim
Le Thu, 12 Mar 2009 11:29:41 +0100
Philippe 92 a écrit

Post by Philippe 92

Post by 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...

trouver un point P tel que les distances de P aux 4 villes soient
les plus proches possibles.
De toute façon l'optimum ne se calcule pas par une formule,
mais par un algorithme d'optimisation.

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.
...
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).

Amicalement.

[zwim]

Le Mon, 30 Mar 2009 13:49:15 +0200
Philippe 92 a écrit

Post by Sébastien de Mapias

Post by zwim
Le Thu, 12 Mar 2009 11:29:41 +0100
Philippe 92 a écrit

Post by Philippe 92

Post by 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...

trouver un point P tel que les distances de P aux 4 villes soient
les plus proches possibles.
De toute façon l'optimum ne se calcule pas par une formule,
mais par un algorithme d'optimisation.

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.
...
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
(infini + x2 + x3 + x4)/4 = infini (heu sans rigueur particulière
sur "infini = ")
<http://cjoint.com/?ebnQvuMr6z>

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...

Post by Sébastien de Mapias
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]

On 30 mar, 13:49, "Philippe 92" <***@free.invalid> wrote:
[...]

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

[claude]

Post by Sébastien de Mapias
C'est difficile à calculer ?

Tu cherche le centre de gravité d'un quadrilatère.

claude

[Olivier Miakinen]

Post by claude
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]

Post by claude

Post by Sébastien de Mapias
C'est difficile à calculer ?

Tu cherche le centre de gravité d'un quadrilatère.

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

[a***@gmail.com]

Post by Sébastien de Mapias
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...
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
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

tu prends tout simplement les deux plus grandes distances entre chaque ville et tu traces la médiane de chacune des deux droites et tu auras le point que tu cherches. les autres seront forcement plus prés car moins éloignés au départ.

[Nicolas de la Ruelle]

Bonjour,
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.

Post by a***@gmail.com

Post by Sébastien de Mapias
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...
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
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

tu prends tout simplement les deux plus grandes distances entre chaque ville et tu traces la médiane de chacune des deux droites et tu auras le point que tu cherches. les autres seront forcement plus prés car moins éloignés au départ.

---
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]

Une autre approche pourrait être le centre de gravité des 4 villes
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.

Post by a***@gmail.com

Post by Sébastien de Mapias
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...
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
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

tu prends tout simplement les deux plus grandes distances entre chaque ville et tu traces la médiane de chacune des deux droites et tu auras le point que tu cherches. les autres seront forcement plus prés car moins éloignés au départ.

---
L'absence de virus dans ce courrier électronique a été vérifiée par le logiciel antivirus Avast.
https://www.avast.com/antivirus