Discussion :

[zeine77]

Bonjour,

Je travaille dans le cadre d'un projet sur la localisation de robots au sein d'une habitation. Le but est de savoir la position du robot dans une salle. Pour ce faire trois capteurs ont été placés dans des endroits bien connus. Chaque capteur i doit calculer la distance di qui le sépare de l'objet (robot). En suite, sachant les coordonnées des trois capteurs et les distances i l'objet est localisé à travers la technique de trilatération (dans l'espace).

Le problème se ramène alors au calcul d'intersection de trois sphères (S1, S2 et S3) de centres les capteurs i et de rayons di.

Après quelques recherches j'ai procédé comme suit: Trouver l'intersection de S1 et S2 qui est un cercle C1, ensuite l'intersection de S1 et S3 ce qui donne un cercle C2 puis calculer l'intersection des cercles C1 et C2.
Et là je suis tombé dans une erreur car la méthode de calcul d'intersection de cercles que j'ai appliquée ( Cette méthode) ne s'applique que dans le cas où les deux cercles se trouvent dans le même plan. (Dans l'espace un cercle n'est pas défini par son équation mais plutôt par son centre, son rayon et le plan dans lequel il se trouve. )

Ma question est alors la suivante:
- Comment calculer l'intersection des deux cercles dans ce cas,

OU si c'est plus facile

- Comment calculer l'intersection du cercle C1 avec la sphère S3 ?

Merci d'avance

[Alexis.M]

Bonjour,

A mon avis tu n'auras jamais des distances assez précises pour que test équations d'intersection aient une solution.

A ta place j'essaierais plutôt une approche par minimisation d'une fonction de coût comme la somme des différences quadratiques entre les distances mesurées et la distance effective:

E = sum_i ( || pi - x || - di )^2
avec pi tes points de référence, di la distance mesurée et x la position à trouver. (cela ressemble à l'énergie d'un système à base de ressorts).

En faisant attention au fait que cette fonction aura des minima locaux. Pour initialiser la minimisation tu peux calculer l'intersection de deux cercles (2 points) et tu choisis comme point de départ le point d'intersection dont la distance au troisième point de référence et la plus proche de la distance annoncée.

[zeine77]

Merci pour ta réponse,

Ce que tu as dit est très intéressant pour moi, à tu me donnes une piste pour traiter un autre problème que j'ai. En fait, j'avais choisi de laisser le problème de la précision des distances mesurées pour le traiter ultérieurement en supposant que les distances sont données avec précision.

Tu dis:

En faisant attention au fait que cette fonction aura des minima locaux. Pour initialiser la minimisation tu peux calculer l'intersection de deux cercles (2 points) et tu choisis comme point de départ le point d'intersection dont la distance au troisième point de référence et la plus proche de la distance annoncée.

Malgré que je n'ai pas bien compris l'approche que tu expliques ici, mais je vois que j'aurai besoin d'un calcul d'intersection de cercles, alors que c'est ça exactement qui me pose un problème (intersection deux cercles dans l'espace).


Merci

[Alexis.M]

fais une simple recherche sur Google

[zeine77]

fais une simple recherche sur Google

J'ai déjà fait cette recherche, les résultats que j'ai trouvés (par exemple ici ) concernent l'intersection de deux cercles dans le plan pas dans l'espace.

J'ai trouvé ce lien intéressant mais je n'est pas su comment prendre en compte la troisième dimension. C'est à dire caculer z de la même manière qu'il a calculé x et y.

x3 = x2 +- h ( y1 - y0 ) / d

y3 = y2 -+ h ( x1 - x0 ) / d

[FR119492]

Salut!

Le problème se ramène alors au calcul d'intersection de trois sphères

Tu écris les équations de tes 3 sphères, qui sont du deuxième degré en X, Y et Z. Tu as donc un système non linéaire de 3 équations à 3 inconnues. Pour le résoudre, tu trouveras diverses méthodes dans les sections 9.6 et 9.7 de Numerical Recipes. Personnellement, comme on ne dispose pas de la matrice jacobienne, j'essaierais d'abord avec la méthode de Broyden.
Jean-Marc Blanc

[Alexis.M]

Si ton robot est sur le sol, tu peux ramener ton problème à l'intersection de cercles dans le plan en projetant le problème au niveau du sol.

Si ton détecteur est à une hauteur h, tu appliques juste Pythagorre:

d_sol = sqrt( r^2 - d^2)

[edfed]

la recherche sur google donne comme premier resultat un bon article sur wiki en anglais.
http://en.wikipedia.org/wiki/Trilateration

puis c'est de l'anglais facile, 80% des mots sont comme en français, les autres c'est les mots de base qu'on apprend tous au college.

[zeine77]

Merci pour toutes vos réponses.

la recherche sur google donne comme premier résultat un bon article sur wiki en anglais.
http://en.wikipedia.org/wiki/Trilateration

puis c'est de l'anglais facile, 80% des mots sont comme en français, les autres c'est les mots de base qu'on apprend tous au college.

Effectivement l'article de Wikipedia en anglais est très bon. J'avais regardé l'article en français qui ne correspond pas à ce que je cherche.

Sur la page de discussion de l'article anglais il y a même un programme en C.


@FR119492 : Merci pour le bouquin, ça me servir certainement un jour.
@Alexis.M : Merci de me donner une piste pour l'autre problème (précisions des mesures).

@+