Le calcul de la surface

Pour calculer la surface d'une image, on pose Chaque variable de l'image voit donc sa surface s'exprimer par une équation linéaire sur la surface de ses fils. Pour calculer la surface de l'image, on doit résoudre le système linéaire ainsi formé. Chaque ligne représente l'équation associée à une variable, et il est nécessaire de les indexer, ce qui aurait été simplifié dans le cas de la représentation en tableaux. On commence donc par associer à chaque variable un entier en parcourant simplement l'arbre, puis on remplit la matrice en regardant l'indice des fils de chaque variable et les termes constants proviennent des éventuels fils Noir. Le système est ensuite résolu par la méthode du pivot de Gauss sur les matrices réelles.

Cependant, on peut remarquer que la matrice ne comporte au plus que cinq coefficients non nuls (le terme diagonal et les quatre fils) par ligne en comptant le terme constant. C'est pourquoi la procédure vérifie si le coefficient est non nul et différent de 1 avant d'effectuer un calcul coûteux. On obtient ainsi la surface de toutes les variables, ce qui s'avère très utile pour l'affichage, comme on le verra par la suite.

Une autre méthode avait tout d'abord été implémentée qui tirait parti de la structure en arbre et consistait à simplifier le système à chaque nud. En effet on implante une fonction récursive equation_surface qui prend pour argument la variable X dont on veut la surface et un ensemble de variables qui sont celles situées au dessus de X dans l'arbre, et qui renvoie la surface de X comme combinaison linéaire des .

surface X {Yi} =
  si X=Blanc renvoie 0
  si X=Noir renvoie 1
  si il existe i tq X=Yi alors renvoie Yi
  sinon 
    combinaison_lineaire=0
    pour chaque    fils Z de X
      ajoute 1/4(surface Z {Yi}UX} a combinaison_lineaire
    match combinaison_lineaire with aX+b+Somme(aiYi) 
          et renvoie b+Somme(aiYi)/(1-a)

(en effet on a d'où le résultat renvoyé, qui est la surface de X en fonction des seules variables qui sont au dessus de lui.)

Malheureusement, cet algorithme ne fonctionne plus dès que l'on autorise les variables utilisées à ne pas se trouver uniquement au dessus dans l'arbre, il a donc été abandonné ; il avait également le défaut de ne calculer, dans un premier temps, que la surface de l'image toute entière (on pouvait tout de même calculer simplement les surfaces des variables en parcourant l'arbre à nouveau, ce qui revenait à résoudre le système en cascade).

Toutefois, étant donné la spécificité de la matrice (une majorité de 0, et uniquement des coefficients et 1 !), la matrice peut très certainement être inversée de manière plus élégante et plus juste, malheureusement, cette possibilité n'a pu être exploitée faute de temps.