Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Point dans l'espace par triangulation

Posté par
carmic
29-08-11 à 23:10

Bonsoir à tous,

Cela fait maintenant 10 ans que je travaille dans l'informatique industrielle après un BTS électronique et mes connaissance de maths ont malheureusement besoin d'être rafraichi.
J'ai eu beau chercher sur Internet ce cas surement connu de triangulation dans divers sujet mais je ne trouve pas l'indice qu'il me manque, aussi, peut être pourriez vous me donner quelques piste de réflexion sur ce problème.

Voici l'énoncé avec un petit dessin en support.
Je dois déterminer si un objet "C" est à l'intérieur ou à l'extérieur d'un cube. J'ai pour m'aider 3 capteurs électroniques A1, A2 et A3 qui me donne les distances dA1C, dA2C et dA3C. Les distances entre les capteurs dA1A2, dA2A3 et dA1A3 sont aussi connu.

Je cherche donc à déterminer la position x,y,z de C.
Je veux donc projeter C à mon repère x,y,z pour connaître la hauteur h. (Axe y) puis les autres positions en x et z à partir de celle ci.

Sur un plan 2D (x,y), j'arrive sans problème à déterminer h (Qui touche alors l'axe A1A2) grâce à:

dA1C/Sin A2 = dCA2/Sin A1 = dA1A2 / Sin C

et le fait que

x = dA1C * cos A1
y = dA1C * sin A1


Mais sur 3 plans, mon h ne touche plus mon axe A1A2 et la je suis perdu dans les calculs.
Je me retrouve avec beaucoup d'inconnu et des calculs dépassant plusieurs lignes sans que je puisse les résoudre.

Pensez vous que le le problème est soluble et que trouver h est la bonne solution?

Et au cas ou, auriez vous une piste pour simplifier les équations ou mieux existe t'il un théorème qui simplifie les équations?  

Merci de votre aide.

Point dans l\'espace par triangulation

Posté par
LeHibou
re : Point dans l'espace par triangulation 29-08-11 à 23:35

Bonsoir,

Tu cherches l'intersection de 3 sphères de rayons respectifs dA1C, dA2C, dA3C, et de centres respectifs A1, A2, A3.
Fais une recherche Google sur "intersection de 3 sphères", tu verras que le sujet a déjà été abondamment traité...

Posté par
carmic
re : Point dans l'espace par triangulation 30-08-11 à 21:07

Bonsoir,
En effet, ça correspond tout à fait. Merci beaucoup

Posté par
carmic
re : Point dans l'espace par triangulation 20-09-11 à 21:26

Alors pour aider les futurs membres, voila le fruit de mes recherches:

Quand on a les angles, c'est la triangulation.
et quand on a les distances, Il s'agit de la trilatération.
C'est très bien expliqué sur wikipedia: http://en.wikipedia.org/wiki/Trilateration

Ensuite, pour ceux qui veulent programmer en C, voici un exemple qui marche très bien.
Par contre, il faut penser à rajouter une 4eme antenne si on ne peut éliminer un point négatif: (Cas des GPS sur la terre)

A+
Carmic

/*
* File: trilateration.c
* AUthor: doug@neverfear.org
*
* Implements an approach to trilateration
*
*/




#include <stdio.h>
#include <string.h>
#include <math.h>

#define PLUS_MINUS '�'
#define PI 3.1415926535897932384626433832795

struct coordinate {
double x;
double y;
double z;
double r;
};

struct transformation {
double x;
double y;
double z;
double alpha;
char zyswapped;
};

#define TRUE  1
#define FALSE 0

#define DEG2RADs(x) ((PI / 180.0) * x)
#define RAD2DEGs(x) ((180.0 / PI) * x)

#define SQR(x) (x * x)

#define PRECISION_F "%.3f"

unsigned int last_random = 1;


/* Generate a random number 0 -> highest */
unsigned int GenerateRandom(unsigned int highest) {
srand(time(NULL) + last_random);
last_random = rand() % highest;
return last_random;
}


/* Generate 3 points in the vector space around target for testing purposes */
void GeneratePoints(struct coordinate target, struct coordinate * terms) {
double alpha;
int i;

for(i = 0; i < 3; i++) {
alpha = DEG2RADs(GenerateRandom(360));

terms[i].x = target.x + (target.r * cos(alpha));
terms[i].y = target.y + (target.r * sin(alpha));
terms[i].z = target.z;
terms[i].r = target.r;

/*
printf("Generated Term %d {\n", i);
printf("  x = " PRECISION_F "\n", terms[i].x);
printf("  y = " PRECISION_F "\n", terms[i].y);
printf("  z = " PRECISION_F "\n", terms[i].z);
printf("}\n");
*/
}

}

/* Perform the trilateration for the given 3 terms */
struct coordinate Trilaterate(struct coordinate * terms) {

struct coordinate result;
double i = terms[2].x - terms[0].x;
double j = terms[2].y - terms[0].y;
double d = terms[1].x;

result.x = (SQR(terms[0].r) - SQR(terms[1].r) + SQR(d)) / (2 * d);

result.y = ( (SQR(terms[0].r) - SQR(terms[2].r) + SQR(i) + SQR(j) ) / (2 * j) ) - ((i / j) * result.x);

result.z = sqrt(abs(SQR(terms[0].r) - SQR(result.x) - SQR(result.y)));

return result;
}


/*
   Modify our coordinate system and apply the new system to the given terms.
   The modifications leave the following state to be true:
   terms[0].x == 0 && terms[0].y == 0 && terms[0].z == 0
   terms[1].y == 0
  
   Returns information about the alterations used to restore the coordinate system later.
*/
struct transformation CoordinateTransformation(struct coordinate * terms) {
int i;
double temp;
struct transformation map;
map.x = -terms[0].x;
map.y = -terms[0].y;
map.z = -terms[0].z;

// Center coordinate system
for(i = 0; i < 3; i++) {
terms[i].x += map.x;
terms[i].y += map.y;
terms[i].z += map.z;
}

// Rotate coordinate system such that terms[1].y == 0
double a; // width
double b; // height
double c; // hypotenuse

a = (terms[1].x);
b = (terms[1].y);
c = sqrt(SQR(a) + SQR(b));

map.alpha = acos(((SQR(a) + SQR(c)) - SQR(b)) / (2.0 * a * c));

if ((a > 0 && b > 0) || (a < 0 && b > 0)) {
map.alpha *= -1;
}

for(i = 0; i < 3; i++) {
// Rotate x and y
double x, y;
x = terms[i].x * cos(map.alpha) - terms[i].y * sin(map.alpha);
y = terms[i].x * sin(map.alpha) + terms[i].y * cos(map.alpha);
terms[i].x = x;
terms[i].y = y;

/*
printf("Rotated Term %d {\n", i);
printf("  x = " PRECISION_F "\n", terms[i].x);
printf("  y = " PRECISION_F "\n", terms[i].y);
printf("  z = " PRECISION_F "\n", terms[i].z);
printf("}\n");
*/
}


if (terms[2].y - terms[0].y == 0) { // TODO: What is this for? - I forgot! Whoops
// Swap z with y
for(i = 0; i < 3; i++) {
temp = terms[i].y;
terms[i].y = terms[i].z;
terms[i].z = temp;
}
map.zyswapped = TRUE;

} else {
map.zyswapped = FALSE;
}

return map;

}

/* Reverse and restore the coordinate system for the given coordinate */
struct coordinate InverseCoordinateTransformation(struct coordinate coord, struct transformation map) {
double temp;

if (map.zyswapped) { // TODO: What is this for? - I forgot! Whoops
temp = coord.y;
coord.y = coord.z;
coord.z = temp;
}

double x = coord.x * cos(-map.alpha) - coord.y * sin(-map.alpha);
double y = coord.x * sin(-map.alpha) + coord.y * cos(-map.alpha);

coord.x = x;
coord.y = y;

coord.x -= map.x;
coord.y -= map.y;
coord.z -= map.z;


return coord;
}


/* Executable entry label */
int main(int argc, char ** argv) {

unsigned long distance;
struct coordinate terms[3];
struct coordinate result;
struct coordinate target;
struct transformation restore;
int i;

// Here you specify the distance the target is from all points
distance = 50;

// Here you specify the target
target.x = 123.0;
target.y = 567.0;
target.z = -10.0;
target.r = distance;

for(i = 1; i <= 20; i++) {
printf("\n** TEST %d ** \n", i);

// Generate a triplet of test points
GeneratePoints(target, terms);

// Alter the coordinate system to center terms[0] and rotate the plane to ensure terms[1].y == 0
restore = CoordinateTransformation(terms);

// Trilaterate the 3 points and get the intersection
result = Trilaterate(terms);

// Restore the previous coordinate system
result = InverseCoordinateTransformation(result, restore);

// Dance or something
printf("Result = (" PRECISION_F ", " PRECISION_F ", %c " PRECISION_F ")\n", result.x, result.y, PLUS_MINUS, result.z);

}
}





Posté par
Bachstelze
re : Point dans l'espace par triangulation 20-09-11 à 21:31

Citation :
#define DEG2RADs(x) ((PI / 180.0) * x)


Attention ! Que se passe-t-il si je fais DEG2RADs(2+2) ?

Posté par
carmic
re : Point dans l'espace par triangulation 20-09-11 à 21:34

En effet, le code n'est pas du tout robuste.
C'est juste pour montrer comment coder le calcul matricielle, c'est ce qui m'avait un peu bloqué




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

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 !