Vecteurs et matrices: outils graphiques utiles

Télécharger le projet
Commenter

Description

En commençant à écrire quelques codes graphiques 3D basés sur l'axonométrie et la perspective, j'ai rapidement constaté qu'il me fallait un ensemble de procédures de calcul vectoriel et matriciel de dimension 1,2,3 et même 4 (certaines transformations 2D sont déjà compris dans le contexte 2D de <canvas>).
Plutôt que de créer ou copier une flopée de petites méthodes selon toutes les combinaisons ces dimensions, je me suis finalement décidé d'écrire (en POO, OOP) quelque chose de beaucoup plus général et plus simple d'utilisation et de documentation.
Les vecteurs y sont considérés comme des matrices dont l'une des dimensions est 1 (vecteur 'ligne' ou vecteur 'colonne').

Voici le mode d'emploi de la 'library' élémentaire de calcul matriciel, basée sur l'objet MatWV, contenu dans le fichier 'MatWV.js' et écrit entièrement en Javascript:

Objet MatWV: Utilisation: Signification: Conditions:
¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯
Constructeur:
MatWV m = new MatWV(nC,nL) Crée une matrice nC*nL
avec des valeurs indéfinies

Méthodes:
Str str=m.Str(sep,eol) Crée un string de m avec
séparateurs et fins de ligne
Const m.Const(k) Multiplie m par la constante k
Norm len=m.Norm() Norme (longueur) du vecteur m (nC==1)||(nL==1)
Det m.Det() Retourne le déterminant de m m carrée
Invert m.Invert() Inverse m, return det m carrée
EcartI m.EcartI() Retourne l'écart abs max par m carrée
rapport à la matrice unité

Les méthodes suivantes créent une nouvelle matrice:
Copy c=m.Copy() Crée une copie (Clone) de m
Transp t=m.Transp() Crée la matrice transposée de m
Sum s=m.Sum(a) Crée la somme m + a dimensions égales
Prod p=m.Prod(r) Crée le produit m * r m.nC==r.nL
Inv i=m.Inv() Crée la matrice inverse de m m carrée

Méthodes statiques:
Uni I=MatWV.Uni(n) Crée la matrice unité n*n (n>0)
Rnd m=MatWV.Rnd(C,L,b,d) Crée une matrice 'aléatoire' C*L, (0<=d<=5)
valeurs bornées par -b et +b,
avec d chiffres après la virgule

(Ce mode d'emploi gagne à être affiché avec une police à chasse fixe, p.ex.: 'Courier New').

La méthode 'Invert()' de l'inversion de matrice que je propose est 'rare', surtout en Javascript !
Elle correspond à une version non récursive, simplifiée et optimisée du code 'C'
donné chez Wikipédia sous forme de deux fonctions:
(http://fr.wikipedia.org/wiki/Matrice_inversible).
Les différences sont les suivantes:
- On opère sur la matrice elle-même.
- Pour augmenter la précision du calcul, on choisit à chaque étape le
meilleur pivot possible (méthode de Gauss-Jordan).
- La boucle la plus intérieure est particulièrement optimisée.
- On retourne le déterminant qui est calculé en même temps.

Le fichier 'Determinant.rtf' (dans le zip) montre comment on peut 'créer' un code de calcul du déterminant en se basant sur trois règles du calcul matriciel.

Le code HTML montre par quelques exemples comment utiliser l'objet MatWV.
A la fin, on mesure le temps nécessaire pour inverser une matrice M de 200*200 (c.-à-d. 40000 éléments remplis aléatoirement) !
Puis on mesure aussi la précision de la matrice unité I obtenue par M * M.Inv().

Attention: Pour le déterminant, l'inversion et le produit, le temps de calcul augmente avec le cube de la dimension: donc pour un N deux fois plus grand, il faut ~ huit fois plus de temps.

Notez qu'avec l'utilisation de MatWV.Rnd(...), vous obtenez chaque fois une matrice différente.
Remarquez également qu'une matrice de déterminant nul ne s'inverse pas; et plus ce déterminant s'approche de 0, moins l'inversion est précise.

Les méthodes Str(), Rnd() et EcartI() ne sont pas strictement nécessaires, elles ont été ajoutées pour faciliter les tests.

Source / Exemple : 


function MatWV(nCol,nLin) { // Constructeur: Matrice à coefficients réels
   this.nC=nCol;                // nombre de colonnes
   this.nL=nLin;                // nombre de lignes
   this.M=new Array(nCol*nLin); // valeurs ligne par ligne
} // http://fr.wikipedia.org/wiki/Matrice_(math%C3%A9matiques)

//============================================================================
// Méthodes d'instance qui ne modifient pas la matrice concernée:

MatWV.prototype.Copy=function() { // Crée une copie (clone) de la matrice
   var m=new MatWV(this.nL,this.nC),NN=this.M.length;
   for (var i=0;i<NN;i++) m.M[i]=this.M[i];
   return m;
}

MatWV.prototype.Det=function() { // Calcule le déterminant de la matrice
   var d=1,e,h,hN,k,kN,i,j,jN,N=this.nC,p,m=this.M.slice(0);
   if (N!=this.nL) return 0; // seulement pour matrices carrées
   for (k=N-1,kN=k*N;k>0;k--,kN-=N) {
      for (j=0,h=k,p=0;j<=k;j++) if ((e=Math.abs(m[k+j*N]))>p) {h=j; p=e;}
      if (h!=k) { // permutation des linges h et k
         hN=h*N; d=-d; // inversion du signe;
         for (i=0;i<=k;i++) {e=m[i+hN]; m[i+hN]=m[i+kN]; m[i+kN]=e;}
      }
      if ((!isFinite(d*=(e=m[k+kN])))||(d==0)) return d;
      for (j=0,jN=0;j<k;j++,jN+=N) // pour chaque ligne (sauf la dernière)
         for (i=0,f=m[k+jN]/e;i<k;i++) m[i+jN]-=f*m[i+kN];
   }
   return d*m[0];
} // http://fr.wikipedia.org/wiki/D%C3%A9terminant_(math%C3%A9matiques)

MatWV.prototype.EcartI=function() { // Ecart abs max de this par rapport à la matrice unité
   var a,e=0,m=this.M,N=1+this.nC,NN=m.length;
   for (var i=0;i<NN;i++) if ((a=Math.abs(((i%N)==0)?1-m[i]:m[i]))>e) e=a;
   return e;
}

MatWV.prototype.Inv=function() { // Crée la matrice inverse de this
   var mi=this.Copy(); return (mi.Invert()!=0)?mi:null;
}

MatWV.prototype.Norm=function() { // Norme d'un vecteur
   if ((this.nC>1)&&(this.nL>1)) return 0; // seulement pour vecteurs
   var i,NN=this.M.length,s=0;
   for (i=0;i<NN;i++) s+=this.M[i]*this.M[i];
   return Math.sqrt(s);
}

MatWV.prototype.Prod=function(r) { // Crée la matrice produit: Prod = this * r
   var m=this.M,tC=this.nC,tL=this.nL,rC=r.nC,rL=r.nL;
   if (tC!=rL) return null;
   var i,l,lt,k=0,c,p=new MatWV(rC,tL),s;
   for (l=0;l<tL;l++) {
      for (c=0,lt=l*tC;c<rC;c++) {
         for (i=0,s=0;i<tC;i++) s+=m[lt+i]*r.M[c+i*rC];
         p.M[k++]=s;
      }
   }
   return p;
} // http://fr.wikipedia.org/wiki/Produit_matriciel

MatWV.prototype.Str=function(sep,eol) { // Crée un string de la matrice 'arrondie'
   var i,q=this.nC,NN=q*this.nL,s=eol;  // avec séparateurs de valeurs et de lignes
   for (i=0;i<NN;i++) s+=Math.round(this.M[i]*1000000)/1000000+(((i+1)%q)?sep:eol);
   return s; // sans arrondi: ... s+=this.M[i]+(((i+1)%q)?sep:eol);
}

MatWV.prototype.Sum=function(a) { // Crée la matrice somme: Sum = this + a
   if ((this.nC!=a.nC)||(this.nL!=a.nL)) return null;
   var m=new MatWV(this.nC,this.nL);
   for (var i=0;i<this.M.length;i++) m.M[i]=this.M[i]+a.M[i];
   return m;
} // http://fr.wikipedia.org/wiki/Addition_matricielle
 
MatWV.prototype.Transp=function() { // Crée la matrice transposée
   var m=new MatWV(this.nL,this.nC);
   for (var l=0;l<this.nL;l++) 
      for (var c=0;c<this.nC;c++) m.M[l+c*this.nL]=this.M[c+l*this.nC];
   return m;
} // http://fr.wikipedia.org/wiki/Matrice_transpos%C3%A9e
//============================================================================
// Méthodes d'instance qui modifient la matrice concernée:

MatWV.prototype.Const=function() { // Multiplie this par la constante k
   for (var i=0;i<this.nC*this.nL;i++) this.M[i]*=k;
}

MatWV.prototype.Invert=function() { // Inverse la matrice this sur elle-même
   var d=1,e,h,hh,ii,j,k,kk=0,m=this.M,N=this.nC,NN=N*N,p,idx=new Array(N);
   if (N!=this.nL) return 0; // Seulement pour matrice carrée
   for (k=0;k<N;k++,kk+=N) {
      for (j=k,p=0;j<N;j++) if ((e=Math.abs(m[j*N+k]))>p) {p=e; h=j;}
      if (p==0) return 0; // meilleur pivot = 0 ==> déterminant = 0
      idx[k]=h; hh=h*N; p=m[hh+k]; d*=(h==k)?p:-p; m[hh+k]=m[kk+k]; m[kk+k]=1;
      for (ii=k;ii<NN;ii+=N) m[ii]/=p;
      for (j=0;j<N;j++) if (k!=j) {
         e=m[hh+j]; m[hh+j]=m[kk+j]; m[kk+j]=0;
         if (e!=0) for (ii=0;ii<NN;ii+=N) m[ii+j]-=e*m[ii+k];
      }
   }
   for (j=N-1;j>=0;j--) // on réarrange les colonnes
      for (ii=0,h=idx[j];ii<NN;ii+=N) {e=m[ii+h]; m[ii+h]=m[ii+j]; m[ii+j]=e;}
   return d; // retourne le déterminant
} // http://fr.wikipedia.org/wiki/Matrice_inversible

//============================================================================
// Les méthodes suivantes sont 'statiques':

MatWV.Rnd=function(nC,nL,lim,dig) { // Crée une matrice 'aléatoire' à valeurs entre -lim et lim
   var m=new MatWV(nC,nL),lim2=2*lim,d=[1,10,100,1000,10000][dig];
   for (var i=0;i<nC*nL;i++) m.M[i]=Math.round(d*(lim-lim2*Math.random()))/d;
   return m; // valeurs arrondies à 'dig' chiffres après la virgule (0<=dig<4)
}

MatWV.Uni=function(n) { // Crée la matrice unité n*n
   var m=new MatWV(n,n);
   for (var i=0;i<n*n;i++) m.M[i]=(i%(n+1))?0:1;
   return m;
} // http://fr.wikipedia.org/wiki/Matrice_unit%C3%A9

// William Voirol, Switzerland, Sep 2011

Conclusion :


Jusqu'à présent, il était conseillé d'envoyer les calculs lourds au serveur et de récupérer les résultats, ce qui implique pas mal de programmation, de tests et de synchronisation.
Si votre processeur n'est pas trop ancien, vous constaterez que tout cela est de moins en moins nécessaire et beaucoup de calculs peuvent se faire localement.
L'inversion d'une matrice 200x200 (ce qui est déjà assez extrème) prend chez moi entre un quart et deux secondes (le dernier temps avec un tout petit portable 10" à ~160 euros)
Ce programme permet aussi de tester l'efficacité des différents navigateurs.

J'admets que tout cela est assez 'technique' et pas très intéressant pour celui qui n'a pas ou peu de connaissances en calcul vectoriel et matriciel. Mais mes prochains articles montreront qu'il est très pratique d'utiliser les notions de vecteurs et de matrices, surtout pour le graphique 2D et 3D.
Les 'librairies' de calcul matriciel (écrits en différents langages) qui dévoilent leur code ont souvent des 'désagréments' tels que:
- calcul peu précis ou même incorrect !
- généralisation de la méthode de Sarrus (calcul du déterminant), alors qu'elle est limitée à 3*3 !
- choix direct de l'élément diagonal comme pivot, ce qui 'bloque'
souvent inutilement le calcul (inversion, déterminant, ...).
- ils n'utilisent pas la programmation objet.
- manque d'un ensemble de tests de précision et de temps de calcul.

Faites directement un test: (observez la remarque ci-dessous)
http://www.william-voirol.ch/Prog/Transformations/Matrices

Remarque: de temps en temps, des espaces (caractères blancs) s'immiscent
dans certains textes. (CodeS-SourceS est au courant du problème).
Si c'était le cas ici, enlevez les espaces avant d'utiliser l'adresse Web ci-dessus.

L'exemple complet se trouve sur le fichier zip.
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (William VOIROL)