========================================


R={r_1,...,r_N}: liste de rectangles qui se font enchaînés pour former une "rangée"

a(r_i): aire du (i)ième rectangle dans R, telle que déterminée par le poids associé avec r_i

l: la longueur de la rangée

s: l'aire totale de la rangée

La rangée a une largeur de s/l,
donc le (i)ième rectangle r_i a les dimensions a(r_i)l/s et s/l
et a la proportion ("aspect ratio") lambda( a(r_i) l^2 / s^2 ) >= 1,
où on définit lambda(x) = max(x,1/x) >= 1

On définit ensuite une fonction qui donne la pire proportion des
rectangles dans R:

   float worst(R,l) {
      return max_i lambda( a(r_i) l^2 / s^2 )
   }

Ensuite, on fait le layout en partie avec une fonction qui ressemble la suivante:


// Cette fonction est pour faire le layout des enfants d'un seul noeud.
// Avant d'appeler cette fonction, tous les enfants sont mis dans la liste
// "enfantsRestants", en ordre décroissant de poids (aire).
// Pour faire le layout d'une arborescence complète, il faut appeler
// cette fonction récursivement pour chacun des noeuds qui a des enfants.
// Notez aussi que cette fonction est seulement une ébauche et ne
// contient pas les tous détails nécessaires.
void squarify(
   // Liste des noeuds qui n'ont pas encore été assignés une position.
   // Cette liste devrait être déjà triée du plus gros au plus petit noeud.
   list<node> enfantsRestants,

   // Liste des noeuds qui sont dans la "rangée" actuelle,
   // qu'on est en traîn de construire
   list<node> rangee,

   // La longueur de la rangée actuelle
   float l
) {
   // On enlève le premier noeud (c.-à-d. le plus gros)
   n = enfantsRestants.pop_front();

   // Si le fait de rajouter cet enfant à la rangée améliore la pire proportion ...
   if ( worst( rangee+[ n ], l) <= worst(rangee,l) ) {
      // ... on continue
      squarify( enfantsRestants, rangee+n, l );
   }
   else {
      // ... autrement, on recule ("backtrack"):

      // On fixe les positions des noeuds dans la rangée actuelle (sans "n")
      layout(rangee);

      // On commence une nouvelle rangée, perpendiculaire à la précédente
      squarify( enfantsRestants, [ n ], dimensionPlusPetiteDuSousRectangleRestant );
   }
}