Discussion :

[Drakaon]

Bonjour,

le suis à la recherche d'un programme de triangulation 2D simple, mais malheureusement pour moi jene trouve que les théories des sieurs Delaunay et Voronoi, ou bien des add-on à des programmes comme autocad ... Alors que ce que je cherche est tellement plus simple !

je vais toujours préciser ma recherche ce n'en sera que plus simple :

A partir des points 1, 2 et 3 je cherche à localiser le point 4

je connais :
X1, Y1, distance de 1 à 4
X2, Y2, distance de 2 à 4
X3, Y3, distance de 3 à 4

La surface totale est un carré de 100 x 100 unités

et je recherche
X4, Y4

Ce n'est pourtant pas compliqué et je suis sûr que ça doit exister sur le net mais pour l'instant, j'ai fait choux blanc :s

est-ce que l'un d'entre vous aurait une idée de l'endroit ou je serais susceptible de trouver tout ça, ou bien pourrait m'aider à composer ce petit programme ?

d'avance merci beaucoup

[nouknouk]

salut,

j'ai du mal à comprendre ce que tu veux au juste:

- tu parles de triangulation (tri=trois) mais dans ton énoncé on a quatre points en jeu.

- tu parles de couples de valeurs qui définissent une distance (normalement 1 valeur)

- tu parles d'une surface sous forme d'un carré, mais on ne sais pas si c'est un carré que tu désires à la fin.

Bref - c'est peu être moi qui ai rien compris - mais j'imagine qu'un ptit schéma aidra à la compréhension.

[Drakaon]

Coucou, et merci d'avoir pris la peine de lire ^^ bon voici un schéma :



je connais les coordonées ( abscisses et ordonnées ) des points orangés

je connais les distances qui séparent les poins orangés du point vert

je cherche les coordonnées du point vert

J'ignore si je peux être plus précis mais l'idée c'est ça ^^

les coordonnées vont de 0 à 100 au maximum sur X et Y d'ou la mention du carré

[nouknouk]

Re,

dans ce cas c'est plus un problème de mathématique que d'informatique.

Ton schéma, version 2:



L'idée de base:

on connait les coordonnées des trois points P1(x1, y1), P2(x2, y2) et P3(x3, y3) et leur distance au point vert, respectivement d1, d2, d3).
On va donc avoir un système de trois équations à 2 deux inconnues, les deux inconnues étant l'abcisse (notée x') et l'ordonnée (notée y') du point vert qu'on va appeler P'.

Tout d'abord, on a la première équation qui part du principe que le point (x',y') est situé à une distance d1 de (x1, y1). On connait la formule pour calculer la distance entre deux points du plan, ici entre P1 et P':

d1² = (x1 - x')² + (y1 - y')²

Même principe pour les deux autres distances aux deux autres points:

d2² = (x2 - x')² + (y2 - y')²
d3² = (x3 - x')² + (y3 - y')²

On se retrouve donc bien avec un système de 3 équations avec nos deux inconnues (x' et y')

Logiquement, en n'utilisant que les deux premières équations (et donc en les mixant ensemble), on trouvera deux solutions possibles.
Graphiquement parlant, chaque équation peut être représentée sur le plan par un cercle (de centre le point P[1,2,3] orange et de rayon d[1,2,3]. Avec deux équations, tu auras deux cercles qui s'entrecoupent en deux points (cf. les deux solutions). Par exemple pour P1 et P2, tu te retrouves avec les cercles c1 et c2 et leur intersection est formée par deux points, P' et P''

La troisième équation permettra de sélectionner la bonne solution parmi les deux trouvées (entre P' et P''). Toujours graphiquement parlant, en ajoutant le troisième cercle c3, l'intersection des trois cercles ne te donnera plus qu'un seul des deux points précédents (on élimine donc P'' pour ne garder que P').

A toi de prendre une feuille de papier et de résoudre le système d'équations avant de le coder dans une petite fonction qui ne devrait pas être bien méchante.

[plegat]

Pour compléter ce qu'a dit Nouknouk, plus simplement ça consiste en une intersection de deux cercles de rayons d1 et d2, ce qui te donne deux points (ou un dans le cas particulier de tangence), le choix étant fait grace à la troisième distance. Pour les détails, il a tout dit

[nouknouk]

ça consiste en une intersection de deux cercles de rayons d1 et d2

Exact, j'avais entre temps edité et complété mon post ci-dessus

A noter que si tu écris une fonction pour résoudre le système d'équation, tu vas devoir utiliser des nombres en virgule flottante (des float ou double) pour stocker tes valeurs (coordonnées et valeurs intermédiaires).

Comme les nombres en virgule flottante ne représentent pas exactement la valeur, mais une approximation de la valeur, le test final (une fois que tu as trouvé les deux possibilités et que tu le confrontes au troisième 'cercle') ne doit pas se faire sur une égalité.

A la place, tu choisiras la valeur "la plus proche" parmi les deux valeurs trouvées.

[Drakaon]

oulà, jusqu'à ce que tu te mettes à parler de virgule flottante je suivais mais plus après ^^'

Et pourquoi une réponse de calcul approximative ? l'intersection de deux cercle ne donne que deux points, non ?

[nouknouk]

Pourquoi une réponse de calcul approximative ? l'intersection de deux cercle ne donne que deux points, non ?

En mathématiques, oui. Mais en informatique, il faut bien stocker la valeur dans une zone mémoire qui ne peut pas avoir une taille infinie. Donc si la zone mémoire n'a pas une taille infinie, on ne pourra stocker dans un float qu'une partie de l'ensemble des nombres réels existant (R), pas tous ceux possibles (il y a un nombre infini de nombres réels dans R).

Il en résulte que certaines valeurs seront stockées non pas de façon exacte, mais légèrement approximée.

Une test simple en Java pour s'en convaincre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
    public static void main(String[] args) {
        float value = 1.0f;
        float sameValue = value / 3000000.f / 37.f / 24.f / 42.f * 3000000.f * 37.f * 24.f * 42.f;
 
        System.out.println("sameValue = "+sameValue);
    }

Ici je prends une valeur de départ (1.0) que je divise par quatre nombres (3 millions, 37, 24 et 42) avant de les remultiplier ensuite par ces mêmes nombres.

En mathématiques, le résultat vaut évidemment 1.0 pour sameValue, car pour n'importe quels réels a,x,y,z,t on a bien : a/x/y/z/t*x*y*z*t = a.

Pourtant, si tu lances ce programme, il t'affichera non pas 1.0, mais "sameValue = 0.99999994".
Cela est en effet du à la perte d'un petit poil de précision lors des calculs intermédiaires.

L'idée est la même pour ton algorithme: dans certains cas, il se pourra qu'un calcul intermédiaire entre deux float ou deux double te fasse perdre un peu de précision (mais pas toujours, ça dépend des calculs, de leur ordre et des valeurs utilisées).

D'où l'idée de ne pas faire un test d'égalité (dans notre exemple, (value == sameValue) te retournera 'faux' alors que tu t'attendais à ce qu'il te retourne 'vrai'), mais un test de 'la solution la plus proche'.

Concrètement dans ton problème ça veut dire:

1- je calcule les coordonnées des points P' et P'' à partir de P1 et P2, d1 et d2 (cf. ci-dessus).

2- je calcule ensuite la distance dist1 = (entre P' et P3) d'une part et la distance dist2 = (entre P'' et P3) d'autre part.

3- je retiens alors la distance parmi dist1 et dist2 qui est la plus proche de d3:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
if ( abs(dist1 - d3) < abs(dist2 - d3) ) {
    //c'est le point P' la solution
}
else 
{
    // c'est le point P'' la solution
}

A noter:
1/ wikipédia l'explique mieux que moi
2/ tu n'as vraiment pas posté dans le bon forum pour ton souci ; essaie de mieux cibler l'endroit où tu postes la prochaine fois.

[Drakaon]

humm oui je vois mieux, mais dans le sens ou ce sont pour des coordonnées "simple" je devrais m'en tirer en ne prenant que les entiers sans décimale ( de ce fait je retrouverai le 1.0 au lieu de 0.99999999994...

Pour le moment j'en suis à relire des cours de math, ça fait 9 ans que j'ai pas retouché à des équations à deux inconnues, et même si je me souviens que c'était simple à faire, j'avoue que le temps à effacé de ma mémoire ces résidus de cours de math ^^ ( et oui, quand on ne travaille plus sa mémoire ... )

Pour ce qui est de la section, désolé ^^' j'ai hésité entre 4 endroits, et comme à la base je visais plus un petit programme de calcul automatique, j'ai pensé que cet endroit était le meilleur ^^

Un modérateur pourrait-il le déplacer dans un endroit plus adapté siouplait ?

merci ^^