Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... École ingénieur AlgèbreTopics traitant de algèbre [tout]Lister tous les topics de mathématiques
Niveau école ingénieur
Partager :

Intersection de trois cercles - Trilatération 2D

Posté par
uterpendragon 19-05-09 à 09:48

Bonjour,

j'ai une petite question d'interprétation (même pas de calcul ) à vous poser.

Soient trois cercles :
\begin{eqnarray} \\ \left(x-x_1\right)^2+\left(y-y_1\right)^2=d_1^2\\ \\ \left(x-x_2\right)^2+\left(y-y_2\right)^2=d_2^2\\ \\ \left(x-x_3\right)^2+\left(y-y_3\right)^2=d_3^2 \\ \end{eqnarray}

Pour calculer leur intersection, on peut résoudre le système de cette façon : soustraire la troisième équation à la première et soustraire la troisième équation à la deuxième, ce qui donne :
\begin{eqnarray} \\ \left(x-x_1\right)^2-\left(x-x_3\right)^2+\left(y-y_1\right)^2-\left(y-y_3\right)^2=d_1^2 - d_3^2\\ \\ \left(x-x_2\right)^2-\left(x-x_3\right)^2+\left(y-y_2\right)^2-\left(y-y_3\right)^2=d_2^2 - d_3^2 \\ \end{eqnarray}

On calcule alors les ()^2 et on met x et y en évidence, on trouve alors :
\begin{eqnarray} \\ 2\left(x_3-x_1\right)x+2\left(y_3-y_1\right)y=d_1^2 - d_3^2 + x_3^2 - x_1^2 + y_3^2 - y_1^2\\ \\ 2\left(x_3-x_2\right)x+2\left(y_3-y_2\right)y=d_2^2 - d_3^2 + x_3^2 - x_2^2 + y_3^2 - y_2^2 \\ \end{eqnarray}

qui est donc un système linéaire !!

On a donc un système de deux équations à deux inconnues Ax=b dont la solution est x=A^{-1}b :

\begin{eqnarray} \\ \left(\begin{array}{c} x \\y \end{array} \right) = \left(\begin{array}{cc} 2(x_3-x_1) & 2(y_3-y_1) \\ 2(x_3-x_2) & 2(y_3-y_2)\end{array} \right)^{-1}\left(\begin{array}{c} d_1^2 - d_3^2 + x_3^2 - x_1^2 + y_3^2 - y_1^2 \\ d_2^2 - d_3^2 + x_3^2 - x_2^2 + y_3^2 - y_2^2\end{array} \right) \\ \end{eqnarray}

On peut par exemple l'appliquer à un exemple :
Cercle 1 : centre de coordonnées (2,1) et de rayon \sqrt 10
Cercle 2 : centre de coordonnées (5,4) et de rayon 2
Cercle 3 : centre de coordonnées (8,2) et de rayon 3

Ces 3 cercles ont effectivement une intersection COMMUNE et la résolution du système nous mène bien à cette solution : (5,2).

MAIS quand il n'y a PAS d'intersection commune, par exemple, les deux mêmes premiers cercles et le troisième légerement modifié :
Cercle 1 : centre de coordonnées (2,1) et de rayon \sqrt 10
Cercle 2 : centre de coordonnées (5,4) et de rayon 2
Cercle 3 : centre de coordonnées (8,2) et de rayon 4

Le système possède une solution qui est (4.3, 2.7). Cette solution est une approximation de "l'intersection" des trois cercles (du triangle formé par les intersections deux à deux).

Ma question est (enfin ) simplement : pourquoi ce système possède une solution quand il n'y a pas d'intersection commune et surtout, pourquoi la solution fournie est-elle une bonne approximation de la position de l'intersection des trois cercles ??
Est-ce une linéarisation du système, est-ce la solution au moindre carrés, ... ??

Merci d'avoir pris votre temps !! si vous avez une idée ...

Posté par
pythamedere : Intersection de trois cercles - Trilatération 2D 19-05-09 à 12:51

Si l'équation de C1 est
f1(x,y)=0  [1],
si l'équation de C2 est
f2(x,y)=0  [2],
si l'équation de C3 est
f3(x,y)=0  [3].

Lorsque tu fait la soustraction membre à membre de [1] et de [2] tu es en fait en train de dire :

Si [1] est vérifié et si [2] est vérifié, alors :

f1(x,y)-f2(x,y)=0    [12]

Alors [12] est vérifié. Donc si les cercles ont une intersection, forcément les points d'intersection vérifient [12].

Mais la réciproque n'est pas vraie !

Les solutions de [12] sont les coordonnées des points d'une droite. Pour tous les points de cette droite, f1(x,y) est égal à f2(x,y), mais ces deux expressions ne sont pas nécessairement nulles !

Par contre le couple d'équations [1] et [12] est équivalent au couple d'équations [1] et [2], car de même que de [1] et [2] tu as pu déduire [12], de [1] et [12] tu peux déduire [2].

Pour trois cercles c'est pareil. Si les trois cercles ont des points communs, alors, nécessairement les coordonnées des points en question vérifient ton système à deux équations. Mais la réciproque n'est pas vraie.

Pour avoir un système équivalent, c'est-à-dire un système qui a les mêmes solutions, il faut garder l'une des trois équations.

La quantité (x-x1)²+(y-y1)²-d1² s'appelle la puissance du point (x,y) par rapport au cercle C1 On peut noter PC1(x,y)=0 pour l'équation de C1.
La quantité (x-x3)²+(y-y3)²-d3² s'appelle la puissance du point (x,y) par rapport au cercle C3. On peut noter PC3(x,y)=0 pour l'équation de C3.

Dire PC1(x;y)-PC3(x,y)=0 c'est dire que les puissances sont égales, mais c'est oublier l'exigence selon laquelle en plus, elles doivent être nulles !

Posté par
uterpendragonre : Intersection de trois cercles - Trilatération 2D 19-05-09 à 15:00

Merci beaucoup !

Effectivement, je sais maintenant pourquoi c'est une "bonne" approximation : c'est l'intersection de deux droites reliant l'intersection de deux cercles.
J'ai tracé tout cela pour l'exemple que j'avais cité au-dessus.

Mais en fait, j'avais besoin de cela car mon but est d'approximer l'intersection des 3 cercles. Les centres des 3 cercles représentent 3 capteurs qui mesurent (avec erreurs) la position d'un objet dans un plan 2D.
Si tu as meilleur moyen d'approximer "au mieux" ce point en connaissant les 3 mesures et les positions des 3 capteurs, cela peut toujours m'intéresser !

Intersection de trois cercles - Trilatération 2D

Edit jamo : Image recadrée pour éliminer des zones inutiles et gagner de la place.

Posté par
vincesdfre : Intersection de trois cercles - Trilatération 2D 24-05-09 à 22:00

Bonjour,

je travail justement sur ce problème et j'ai trouvé la "meilleure" approximation de l'intersection en reprenant l'idée de la méthode des moindres carrés de Gauss.

Selon lui il faut minimiser la somme des erreurs au carré pour trouver la meilleure solution donc j'ai étudié la fonction r:(x,y)->f1(x,y)²+f2(x,y)²+f3(x,y)² pour trouver ses points critiques et enfin son minimum global.

J'espère que ça t'aidera, par contre moi j'aurais besoin de savoir à quoi ça peut servir pour illustrer mon étude.

Posté par
ghabri Intersection de trois cercles - Trilatération 2D 14-02-14 à 12:04

Bonjour ,
Je suis entrain de travailler sur le même sujet ,déterminer la position d'un point a partir de la puissance du signal reçu d'un point d'accès. Avez vous essayé cette méthode ,et vos recherches ont elles aboutit à un bon résultat ? j'ai lu beaucoup d'articles à propos de ces méthodes ,mais ils m'ont rendu encore plus confuse.
Merci bien de lire mes question et d'y répondre ,ça me serais très utile.  


Rechercher
Menu
Espace membre
7 visiteurs
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1724 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !