Ajouter un commentaire

willbback
Une petite dernière....

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

Filtered HTML

Plain text

CAPTCHA
Cette question permet de vérifier que vous n'êtes pas un robot spammeur :-)
 ZZZZZ  K  K  ZZZZZ  K  K  X   X 
Z K K Z K K X X
Z KK Z KK X
Z K K Z K K X X
ZZZZZ K K ZZZZZ K K X X