Décidément, mon patron va finir par me virer à force de jouer avec ce merveilleux algorithme.
Voici le code que j'ai mis en place
package test;
class Geotest {
// n = nombre de points
// m = dimension de l'espace
private int n = 10;
private int m = n - 1;
// Matrice des positions initiales
public double[][] positionInit = new double[n][m];
// Matrice des positions reconstruites par l'algorithme
public double[][] position = new double[n][m];
// Matrice des distances
public double[][] distance = new double[n][n];
// petite methode pour calculer un carre
double SQR(double x) {
return x * x;
}
// Calcul de la distance euclidienne pour la matrice de position
double dist(double[][] position, int a, int b) {
double sum = 0;
for (int i = 0; i < m; i++) {
sum = sum + SQR(position[a][i] - position[b][i]);
}
return Math.sqrt(sum);
}
public void executeTest() {
// On crée une matrice triangulaire aléatoire
System.out.println("Matrice Initiale");
for (int i = 0; i < n; i++) {
System.out.print(i + "=> ");
for (int j = 0; j < i; j++) {
positionInit[i][j] = (int)(Math.random() * 10);
System.out.print(positionInit[i][j] + " ");
}
System.out.println();
}
// On calcul les distances euclidiennes entre les points
System.out.println("Matrice distance");
for (int i = 0; i < n; i++) {
System.out.print(i + "=> ");
for (int j = 0; j < i; j++) {
distance[i][j] = dist(positionInit, i, j);
distance[j][i] = dist(positionInit, i, j);
System.out.print(distance[i][j] + " ");
}
System.out.println();
}
System.out.println("Matrice Résultat (intermediaire)");
System.out.print("1=> ");
// Le premier point a tout ces coordonnées nulles
// Le deuxième n'a qu'une seule coordonnée nulle
position[1][0] = distance[1][0];
System.out.println(position[1][0] + " ");
/* On lance notre algorithme pour trouver les coordonnées des points 3 à n */
double zero = 0;
for (int WichPoint = 2; WichPoint < n; WichPoint++) {
int i = WichPoint; // je met i juste pour simplifier le code, et Wichpoint pour comprendre de
// quoi je parle
System.out.print(i + "=> ");
// La norme du vecteur sera sa distance au point 1
double norme = SQR(distance[0][i]);
// On calcul d'abord les n-2 premières coordonnées du point courant
for (int p = 0; p < i - 1; p++) {
position[i][p] = norme - SQR(distance[p + 1][i]) + SQR(distance[p + 1][0]);
double sumCoord = 0;
for (int j = 0; j <= p - 1; j++) {
sumCoord += position[i][j] * position[p + 1][j];
}
position[i][p] = position[i][p] - 2 * sumCoord;
position[i][p] = position[i][p] / (2 * position[p + 1][p]);
System.out.print(position[i][p] + " ");
}
System.out.println();
// On calcul enfin la dernière coord du point courant en utilisant les coord calculés à
// l'instant
double sumSQR = 0;
for (int j = 0; j < i - 1; j++) {
sumSQR += SQR(position[i][j]);
}
// Le dernier calcul devrait tjs etre vrai car norme > sumSQR (mathematiquement j'entend)
position[i][i - 1] = (float)Math.sqrt(norme - sumSQR);
// Or y'a du NaN ???? donc norme < sumSQR et c pas normal !!!
// On test le dernier calcul voir quand apparait ce NaN
if (Double.isNaN(position[i][i - 1]) == true && zero == 0) {
zero++;
System.out.println("Nan a " + i);
}
}
System.out.println("Matrice resultat");
for (int i = 0; i < n; i++) {
System.out.print(i + "=> ");
for (int j = 0; j < i; j++) {
System.out.print(position[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
Geotest test = new Geotest();
test.executeTest();
}
}
J'ai fait plusieurs éxécutions avec n=10 pour ne pas faire trop apparaître de résultat.
J'ai transformé l'affectation aléatoire pour donner un nombre entier compris entre 0 et 9 afin de limiter l'influence d'une imprécision de calcul.
J'ai fait également afficher les différentes matrices produites (avec un joli effet de mise en page pour bien tout voir :lol: )
Voici le résultat :
Matrice Initiale
0=>
1=> 3.0
2=> 0.0 0.0
3=> 1.0 3.0 1.0
4=> 9.0 7.0 3.0 5.0
5=> 1.0 2.0 5.0 9.0 0.0
6=> 3.0 3.0 7.0 9.0 6.0 3.0
7=> 5.0 0.0 4.0 4.0 6.0 0.0 2.0
8=> 9.0 3.0 6.0 7.0 6.0 2.0 3.0 4.0
9=> 6.0 4.0 9.0 7.0 3.0 1.0 1.0 5.0 1.0
Matrice distance
0=>
1=> 3.0
2=> 0.0 3.0
3=> 3.3166247903554 3.7416573867739413 3.3166247903554
4=> 12.806248474865697 10.908712114635714 12.806248474865697 10.44030650891055
5=> 10.535653752852738 10.677078252031311 10.535653752852738 9.899494936611665 10.44030650891055
6=> 13.892443989449804 13.564659966250536 13.892443989449804 12.884098726725126 11.357816691600547 7.3484692283495345
7=> 9.848857801796104 8.717797887081348 9.848857801796104 9.486832980505138 10.344080432788601 9.273618495495704 7.745966692414834
8=> 15.491933384829668 13.96424004376894 15.491933384829668 14.247806848775006 9.695359714832659 11.61895003862225 8.18535277187245 7.681145747868608
9=> 14.798648586948742 13.856406460551018 14.798648586948742 13.2664991614216 9.746794344808963 9.273618495495704 7.615773105863909 9.38083151964686 5.916079783099616
Matrice Résultat (intermediaire)
1=> 3.0
2=> 0.0
3=> 1.0 NaN
Nan a 3
4=> 9.000000000000002 NaN NaN
5=> 0.9999999999999977 NaN NaN NaN
6=> 2.999999999999995 NaN NaN NaN NaN
7=> 4.999999999999996 NaN NaN NaN NaN NaN
8=> 9.000000000000005 NaN NaN NaN NaN NaN NaN
9=> 6.000000000000004 NaN NaN NaN NaN NaN NaN NaN
Matrice resultat
0=>
1=> 3.0
2=> 0.0 0.0
3=> 1.0 NaN NaN
4=> 9.000000000000002 NaN NaN NaN
5=> 0.9999999999999977 NaN NaN NaN NaN
6=> 2.999999999999995 NaN NaN NaN NaN NaN
7=> 4.999999999999996 NaN NaN NaN NaN NaN NaN
8=> 9.000000000000005 NaN NaN NaN NaN NaN NaN NaN
9=> 6.000000000000004 NaN NaN NaN NaN NaN NaN NaN NaN
La lecture de se résultat montre que :
le test du NaN ne reporte pas toutes les erreurs
le NaN se trouve gentiellement réparti après le 2ème colonne de la matrice
Quote:
Et les calculs je l'es ai verifié 20 fois ... (d'ou les presque 1mois de recherche de bug=verif calcul + verif divergence quelconque + c quoi ce bordel putain)
Je pense qu'il est peut-être nécessaire de revérifier l'algorithme d'implémentation. Un petit problème de déplacement dans la Matrice peut-être ?
Quote:
Pour reparler du bug, j'avais deja vu ouais que norm devenait plus petit que sumCoord vers la fin, mais je n'en ai pas trouvé la raison.
sur d'autres forum on me parle de la precision, et d'utiliser BigDecimal . Je vais tester ca j'ai rien a perdre...
Juste pour info, Math.sqrt fonctionne qu'avec des doubles, donc la précision restera égale à l'imprécision des doubles, quoi que tu fasses
Décidément, mon patron va finir par me virer à force de jouer avec ce merveilleux algorithme.
Voici le code que j'ai mis en place
package test; class Geotest { // n = nombre de points // m = dimension de l'espace private int n = 10; private int m = n - 1; // Matrice des positions initiales public double[][] positionInit = new double[n][m]; // Matrice des positions reconstruites par l'algorithme public double[][] position = new double[n][m]; // Matrice des distances public double[][] distance = new double[n][n]; // petite methode pour calculer un carre double SQR(double x) { return x * x; } // Calcul de la distance euclidienne pour la matrice de position double dist(double[][] position, int a, int b) { double sum = 0; for (int i = 0; i < m; i++) { sum = sum + SQR(position[a][i] - position[b][i]); } return Math.sqrt(sum); } public void executeTest() { // On crée une matrice triangulaire aléatoire System.out.println("Matrice Initiale"); for (int i = 0; i < n; i++) { System.out.print(i + "=> "); for (int j = 0; j < i; j++) { positionInit[i][j] = (int)(Math.random() * 10); System.out.print(positionInit[i][j] + " "); } System.out.println(); } // On calcul les distances euclidiennes entre les points System.out.println("Matrice distance"); for (int i = 0; i < n; i++) { System.out.print(i + "=> "); for (int j = 0; j < i; j++) { distance[i][j] = dist(positionInit, i, j); distance[j][i] = dist(positionInit, i, j); System.out.print(distance[i][j] + " "); } System.out.println(); } System.out.println("Matrice Résultat (intermediaire)"); System.out.print("1=> "); // Le premier point a tout ces coordonnées nulles // Le deuxième n'a qu'une seule coordonnée nulle position[1][0] = distance[1][0]; System.out.println(position[1][0] + " "); /* On lance notre algorithme pour trouver les coordonnées des points 3 à n */ double zero = 0; for (int WichPoint = 2; WichPoint < n; WichPoint++) { int i = WichPoint; // je met i juste pour simplifier le code, et Wichpoint pour comprendre de // quoi je parle System.out.print(i + "=> "); // La norme du vecteur sera sa distance au point 1 double norme = SQR(distance[0][i]); // On calcul d'abord les n-2 premières coordonnées du point courant for (int p = 0; p < i - 1; p++) { position[i][p] = norme - SQR(distance[p + 1][i]) + SQR(distance[p + 1][0]); double sumCoord = 0; for (int j = 0; j <= p - 1; j++) { sumCoord += position[i][j] * position[p + 1][j]; } position[i][p] = position[i][p] - 2 * sumCoord; position[i][p] = position[i][p] / (2 * position[p + 1][p]); System.out.print(position[i][p] + " "); } System.out.println(); // On calcul enfin la dernière coord du point courant en utilisant les coord calculés à // l'instant double sumSQR = 0; for (int j = 0; j < i - 1; j++) { sumSQR += SQR(position[i][j]); } // Le dernier calcul devrait tjs etre vrai car norme > sumSQR (mathematiquement j'entend) position[i][i - 1] = (float)Math.sqrt(norme - sumSQR); // Or y'a du NaN ???? donc norme < sumSQR et c pas normal !!! // On test le dernier calcul voir quand apparait ce NaN if (Double.isNaN(position[i][i - 1]) == true && zero == 0) { zero++; System.out.println("Nan a " + i); } } System.out.println("Matrice resultat"); for (int i = 0; i < n; i++) { System.out.print(i + "=> "); for (int j = 0; j < i; j++) { System.out.print(position[i][j] + " "); } System.out.println(); } } public static void main(String[] args) { Geotest test = new Geotest(); test.executeTest(); } }J'ai fait plusieurs éxécutions avec n=10 pour ne pas faire trop apparaître de résultat.
J'ai transformé l'affectation aléatoire pour donner un nombre entier compris entre 0 et 9 afin de limiter l'influence d'une imprécision de calcul.
J'ai fait également afficher les différentes matrices produites (avec un joli effet de mise en page pour bien tout voir :lol: )
Voici le résultat :
La lecture de se résultat montre que :
le test du NaN ne reporte pas toutes les erreurs
le NaN se trouve gentiellement réparti après le 2ème colonne de la matrice
Je pense qu'il est peut-être nécessaire de revérifier l'algorithme d'implémentation. Un petit problème de déplacement dans la Matrice peut-être ?
Juste pour info, Math.sqrt fonctionne qu'avec des doubles, donc la précision restera égale à l'imprécision des doubles, quoi que tu fasses