Discussion :

[hyust]

Bonjour,
Je poste ce message dans le but de recevoir de l'aide sur un projet. A l'aide de 3 Raspberry je dois localiser un émetteur de signaux (box wifi, émetteur bluetooth, ...). Je dispose de la fréquence et de la puissance du signal reçue par chaque Raspberry ainsi que des coordonnées GPS (en degré décimal) de celles-ci.
A l'aide de la formule suivante, on détermine la distance Raspberry-Emetteur:
distance = 10 ^ ((27.55 - (20 * log10(fréquence)) + |puissance|)/20)
Avec la distance en mètres, la fréquence en MHz et la puissance en dBm.
Jusque là je n'ai pas de soucis. On obtiens donc 3 cercles (chaque cercle a pour centre une des Raspberry et pour rayon la distance entre cette Raspberry et l'émetteur).
Je précise que les
Mon problème est là. Comment déterminer l'intersection de ces 3 cercles.
J'ai vu qu'il existe des formules mathématiques, mais aucune ne marche.
Merci d'avoir pris le temps de me lire.

[dourouc05]

Comment déterminer l'intersection de ces 3 cercles.
J'ai vu qu'il existe des formules mathématiques, mais aucune ne marche.

Qu'as-tu essayé comme formule ? À tout hasard, ne s'agirait-il pas d'intersection de cercles dans un cas idéalisé, alors que tu te bases sur des mesures physiques (donc les rayons des cercles sont connus à une certaine précision, pas infinie) ? (Sans oublier d'autres problèmes de propagation qui arrivent dans le monde réel, comme le multitrajet.)

Par exemple, dans http://www.nbmg.unr.edu/staff/pdfs/b...20of%20gps.pdf, section 4, on parle de trouver une position à l'aide d'une minimisation d'erreur : cela part du principe que tes cercles n'ont pas d'intersection au sens strict, mais qu'ils s'intersectent "presque".

Vu ton application, je pense effectivement que trois mesures devraient suffire, vu que tu travailles dans une zone assez réduite que l'on peut approcher par un plan (contrairement à la Terre : avec trois mesures, tu as parfois deux intersections plausibles de trois cercles).

[wiwaxia]

Bonjour,

Etant donnés les 3 cercles de rayons (d₁, d₂, d₃) centrés aux points (C₁, C₂, C₃) où se trouvent les détecteurs Raspberry, tu pourrais envisager de repérer à l'intérieur du triangle formé le minimum de la somme des carrés:

S(x, y) = (C₁M - d₁)² + (C₂M - d₂)² + (C₃M - d₃)² ;

La position ainsi détectée est la plus proche de chacun des cercles précédemment définis.

Si tu disposes de plus des incertitudes (∆₁, ∆₂, ∆₃) affectant chacune des distances, tu peux travailler sur la somme (cette fois sans dimension):

T(x, y) = (C₁M - d₁)²/∆₁² + (C₂M - d₂)²/∆₂² + (C₃M - d₃)²/∆₃² .

[wiwaxia]

Le minimum est encore plus net si l'on s'intéresse à la racine carrée de la somme:

S'(x, y) = S(x, y)^1/2 .

[hyust]

Qu'as-tu essayé comme formule ? À tout hasard, ne s'agirait-il pas d'intersection de cercles dans un cas idéalisé, alors que tu te bases sur des mesures physiques (donc les rayons des cercles sont connus à une certaine précision, pas infinie) ? (Sans oublier d'autres problèmes de propagation qui arrivent dans le monde réel, comme le multitrajet.)

Merci pour ta réponse, j'ai testé cette méthode:
http://math.15873.pagesperso-orange.fr/IntCercl.html
Elle semble marcher avec des données comme (2;3) r=2, (4;5) r=3, r=5(8;9) mais dès que je me sert de données réelles ça ne marche plus.
Sonde 1 (-0.502321;47.490327)
Sonde 2 (-0.50245;47.490287)
Sonde 3 (-0.502439;47.490378)
distS1: 5.4476845467318m
distS2: 4.8552539629314m
distS3: 1.5353661141422m

J'ai pensé au fait que ces valeurs étaient des arrondis, donc que les cercles ne se coupent pas forcément, est ce ça?
Je n'ai pas compris la marge d'erreur dont tu parles.

[hyust]

Bonjour,

Etant donnés les 3 cercles de rayons (d₁, d₂, d₃) centrés aux points (C₁, C₂, C₃) où se trouvent les détecteurs Raspberry, tu pourrais envisager de repérer à l'intérieur du triangle formé le minimum de la somme des carrés:

S(x, y) = (C₁M - d₁)² + (C₂M - d₂)² + (C₃M - d₃)² ;

La position ainsi détectée est la plus proche de chacun des cercles précédemment définis.

Si tu disposes de plus des incertitudes (∆₁, ∆₂, ∆₃) affectant chacune des distances, tu peux travailler sur la somme (cette fois sans dimension):

T(x, y) = (C₁M - d₁)²/∆₁² + (C₂M - d₂)²/∆₂² + (C₃M - d₃)²/∆₃² .

Merci pour ta réponse,
Dans ton message, à quoi correspondent les points C1, C2 et C3? Sont ils de la forme (x;y)? Et qu'est ce que M?

[wiwaxia]

... Dans ton message, à quoi correspondent les points C1, C2 et C3? Sont ils de la forme (x;y)? Et qu'est ce que M?

Les points (C₁, C₂, C₃₎) représentent les positions des 3 détecteurs; ils sont définis par leurs coordonnées (X_c1, Y_c1), (X_c2, Y_c2), (X_c3, Y_c3) qui font partie des 9 données du problème, avec les distances (D₁, D₂, D₃).

(M) est un point quelconque du domaine rectangulaire envisagé, et de ses coordonnées (x, y) dépend la somme S(x, y) dont on recherche le minimum:

S(x, y) = (C₁M - d₁)² + (C₂M - d₂)² + (C₃M - d₃)² ;

avec

C₁M² = (x - X_c1)² + (y - Y_c1)² ,
C₂M² = (x - X_c2)² + (y - Y_c2)² ,
C₃M² = (x - X_c3)² + (y - Y_c3)² .

[hyust]

C₁M² = (x - X_c1)² + (y - Y_c1)² ,
C₂M² = (x - X_c2)² + (y - Y_c2)² ,
C₃M² = (x - X_c3)² + (y - Y_c3)² .

Je ne vois toujours pas ce qu'est M. Il peut être n'importe quel point du plan? Comme (0;5) par exemple? Et les coordonnées x et y sont elles celles de S ou de M? Dernière chose, dans ton équation S= ... il y a C₂M, or en dessous tu as C₂M². Comment revenir à la forme attendue dans l'équation S= ?

[wiwaxia]

Je ne vois toujours pas ce qu'est M. Il peut être n'importe quel point du plan? Comme (0;5) par exemple? Et les coordonnées x et y sont elles celles de S ou de M? ...

(M) est un point quelconque du domaine bidimensionnel étudié, qu'il faut explorer si l'on veut trouver l'extremum de la fonction S(x, y).
Dans le cas de l'image donnée plus haut (#04), représentant les variations de la fonction 5(x, y), le couple de coordonnées (x, y) est une paire d'entiers (au format Word ou LongInt) appartenant au domaine de l'image, soit:

[0..(Largeur - 1)]×[0..(Hauteur - 1)] ;

dans le cas de la recherche analytique du minimum (que l'image précédente permet de cerner en en donnant une solution approchée), (x, y) sont des nombres décimaux au format Extended dont on cherche la limite avec une précision arbitraire (compatible avec celle du processeur).

... Dernière chose, dans ton équation S= ... il y a C₂M, or en dessous tu as C₂M². Comment revenir à la forme attendue dans l'équation S= ?

Il faut prendre la racine carrée des expressions correspondantes, par exemple:

C₂M = [C₂M²]^1/2 = [(x - X_c2)² + (y - Y_c2)²]^1/2 .

Il s'agit des distances euclidiennes, données par la relation de Pythagore.

[hyust]

Je suis vraiment désolé mais je ne comprends vraiment pas .

[tbc92]

Quand tu écris : Sonde 1 (-0.502321;47.490327), est ce que tu comprends ce que tu écris ?
Quelle est l'unité de ces 2 nombres ?
Quel est le nom de ces 2 nombres ?

Réponse (en blanc sur fond blanc... pour te laisser réfléchir quelques instants) :
L'unité de ces 2 nombres est le degré
Ces 2 nombres s'appellent respectivement longitude et latitude.

Et du coup, pour mettre en place les formules que tu as trouvées, la manipulation à faire est ...

[hyust]

Oui je sais que les 2 coordonnées sont longitude et latitude, mais je ne vois pas la manipulation à faire.

[tbc92]

Il faut convertir longitude et latitude en mètres.
Le rayon de la Terre est de 6371000 mètres

y=latitude * 6371000 * 3.1415927/180
x=longitude * 6371000*cos(latitude)* 3.1415927/180

Et dans ce calcul, il faut s'assurer que la calculatrice utilisée fonctionne en degrés et pas en radians ni en grades.
Par exemple, pour la valeur 47.490327, la calculatrice utilisée doit dire : cos(47.490327)=0.67571467
Si elle donne par exemple -0.933, ça veut dire que la calculatrice fonctionne en radians, et donc il faut adapter la formule : x = longitude * 6371000*cos(latitude * 3.1415927/180) * 3.1415927/180

Si tu fais ces opérations, tu vas constater que sur ton exemple, les sondes sont à peu près à 10m les unes des autres, et que c'est globalement compatible avec les 3 mesures.

[hyust]

Le rayon de la Terre est de 6371000 mètres

y=latitude * 6371000 * 3.1415927/180
x=longitude * 6371000*cos(latitude)* 3.1415927/180

Ahhhh d'accord, donc y= la distance entre un point et l'équateur (en m) et x= la distance entre un point et le méridien de Greenwich (en m). Je testerais ça demain, mais merci pour ton aide.

[tbc92]

C'est bien ça.
On considère ici que la terre est une sphère, on fait l'impasse sur ce qui se passe au voisinage des pôles.

[wiwaxia]

Une donnée essentielle me paraît absente de cette discussion: la portée des récepteurs, dont je suppose (faute de toute cindication technique) qu'elle est de l'ordre de quelques centaines de mètres; cependant quand bien même elle atteindrait une dizaine de kilomètres, on reste très en-dessous du rayon terrestre.
La courbure de la surface est par conséquent négligeable, et l'on doit pouvoir simplifier les calculs d'une manière drastique, et se ramener à un problème de géométrie plane, dans un plan tangent à la sphère au voisinage des récepteurs considérés.

J'ai tenté ci-dessous de présenter le changement de repère en cause, en allant à l'essentiel par le chemin le plus court et le plus simple, donc en zappant toute considération d'analyse vectorielle.

Il serait bon que tu donnes à titre d'exemple les coordonnées (φ, λ) de trois positions rencontrées.

[tbc92]

Il y a un jeu d'exemple, avec 3 points à une dizaine de mètres les uns des autres, latitude 49° ; donc tout va bien.
Ici, tu proposes de travailler en 3D. Ca peut être utile.
Si les 3 sondes sont au niveau du plancher, si le point M est au niveau du plafond, voire du 2ème étage, on peut avoir des biais.
Je chipote, je chipote.
Je suis quand même en attente, parce que sur les données d'exemple, ça marchait moyennement. Je pense que mes formules sont bonnes, mais j'en viens à douter.
Ici, les 3 points tombaient à Angers, vers le parc des expositions. Tu confirmes ?

[wiwaxia]

Il y a un jeu d'exemple, avec 3 points à une dizaine de mètres les uns des autres, latitude 49° ; donc tout va bien ...

Ces données m'avaient échappé, je vais regarder ce à quoi elles conduisent. Je ne m'attendais pas à des distances aussi faibles

Sonde 1 (-0.502321;47.490327)
Sonde 2 (-0.50245;47.490287)
Sonde 3 (-0.502439;47.490378)
distS1: 5.4476845467318m
distS2: 4.8552539629314m
distS3: 1.5353661141422m

... Ici, tu proposes de travailler en 3D. Ça peut être utile.
Si les 3 sondes sont au niveau du plancher, si le point M est au niveau du plafond, voire du 2ème étage, on peut avoir des biais.
Je chipote, je chipote. ...

Il y a malentendu: il s'agissait simplement de montrer, avec le maximum de concision, le passage d'un trièdre trirectangle (CX_TY_TZ_T) à un autre (u, v, w); la figure géométrique étudiée reste cependant dans un plan, le plan contenant le point (M) et orienté par les deux vecteurs orthoradiaux (u, v).
La méthode des moindres carrés peut être transposée dans l'espace, mais je n'ai pas du tout envisagé cela: la question de l'intersection commune à 3 cercles est déjà suffisamment compliquée !

Je me suis laisser emporter par un désir excessif de simplification, en oubliant les distances renvoyées par les détecteurs:
On se ramène ainsi à un simple calcul de distances dans un repère orthonormé, où l’introduction du rayon terrestre (R T ) est inutile, de même que toute conversion d’unité d’angle ...
C'est faisable, mis amène finalement des complications inutiles, et risque de dérouter des lecteurs qui seraient peu familiers des changements d'unité. Mieux vaut s'en tenir aux relations classiques, impliquant des distances exprimées en mètres, et des angles en radians:

x_j = R_TCos(λ₀).∆φ_j = R_TCos(λ₀).(φ_j - φ₀) , y_j = R_T.∆λ_j = R_T.(λ_j – λ₀) .

Un facteur d'échelle approprié pourra être défini au niveau de l'algorithme.

[wiwaxia]

Le programme est nettement plus lourd en raison de la nécessité de calculer un double système de coordonnées, l'un pour la figure géométrique et l'autre pour l'image.

Les données ne sont guère cohérentes, notamment la dernière distance (Dist3) dont la valeur apparaît manifestement trop faible (à moins bien sûr d'une erreur de calcul).
La méthode des moindres carrés conduit toujours à un résultat (croix blanche), mais qui ne présente guère de sens.

[tbc92]

Oui, même résultat. On est à l'intersection des 3 cercles, sauf qu'il n'y a pas d'intersection, même pas en prenant les cercles 2 à 2 !