Le problème du treemap

C’est un rectangle. Dedans, il y a des rectangles plus petits. Qu’est-ce qui peut être si compliqué ?

Un treemap est une idée simple. On a un canevas et un ensemble de fichiers, chacun avec une taille. On veut tous les afficher simultanément, avec pour chaque élément une surface proportionnelle à la taille du fichier. Le canevas est toujours entièrement rempli. Rien n’est gaspillé.

Ben Shneiderman a décrit le concept en 1992, à l’Université du Maryland. L’idée est élégante parce qu’elle résout un problème de densité : on peut afficher des milliers d’éléments dans un espace fixe, et les tailles relatives sautent aux yeux. Un camembert devient illisible au-delà de six ou sept parts. Un treemap peut montrer cinq mille fichiers et on repère encore les plus gros au premier coup d’œil.

L’invariant fondamental : la surface est égale à la taille.

L’approche naïve

L’implémentation naïve est un simple découpage récursif. On prend un rectangle. On le découpe horizontalement en N bandes, une par enfant, chacune avec une hauteur proportionnelle à sa taille. Si un enfant possède ses propres enfants, on découpe sa bande verticalement. Et ainsi de suite, récursivement.

Ça fonctionne : les surfaces sont justes, le calcul tient en trois lignes.

Le résultat est aussi visuellement désastreux.

Un répertoire contenant dix fichiers de tailles à peu près égales produit dix bandes horizontales, chacune d’environ cinq cents pixels de large et douze pixels de haut. Impossible de lire les étiquettes, impossible de cliquer précisément sur un élément. Les rectangles ne sont plus des formes, ce sont des traits. Des rapports d’aspect de 40:1 sont monnaie courante.

Découpage naïf : 10 fichiers de taille égale dans un canevas 500×200 :

┌──────────────────────────────────────────────────┐ ← 500 px de large
│ file-01.dmg (20 px de haut)                      │
│ file-02.mp4                                      │
│ file-03.zip                                      │
│ file-04.pkg                                      │
│ ...                                              │
└──────────────────────────────────────────────────┘
  Rapport d'aspect par bande : 25:1. Illisible.

Une bande fine a la bonne surface mais la mauvaise géométrie. Il faut les deux.

L’algorithme squarified

L’algorithme squarified s’attaque directement à ce problème. Il a été publié par Mark Bruls, Kees Huizing et Jarke van Wijk en 2000 : l’article, « Squarified Treemaps », est assez court pour être lu en un après-midi. L’objectif : maintenir des rapports d’aspect proches de 1. Pas exactement 1, parce que les surfaces doivent toujours être correctes, mais aussi proches que les mathématiques le permettent.

L’algorithme traite les enfants par taille décroissante. Il maintient une « rangée » courante d’éléments disposés le long d’un bord de l’espace restant. Pour chaque nouvel élément, il pose la question : si j’ajoute cet élément à la rangée courante, le pire rapport d’aspect de la rangée s’améliore-t-il ou se dégrade-t-il ? S’il s’améliore, on ajoute l’élément. S’il se dégrade, on valide la rangée courante, on alloue sa bande dans l’espace restant, et on en démarre une nouvelle.

graph TD
    accTitle: Squarified treemap algorithm
    accDescr: Sort children by size descending, then repeatedly try adding the next child to the current row. If the worst aspect ratio improves, keep it; otherwise commit the row and start a new one. Continue until all children are placed.
    A[Trier les enfants par taille décroissante] --> B[Démarrer une nouvelle rangée]
    B --> C[Essayer d'ajouter l'enfant suivant]
    C --> D{Le pire rapport d'aspect s'améliore-t-il ?}
    D -->|oui| E[Ajouter à la rangée courante]
    E --> C
    D -->|non| F[Valider la rangée courante en rectangles disposés]
    F --> B
    E --> G{Reste-t-il des enfants ?}
    G -->|non| H[Valider la rangée finale]

Essayez : déplacez les curseurs pour modifier les tailles relatives des fichiers et observez les deux dispositions se mettre à jour en temps réel.

Le résultat est une disposition où la plupart des rectangles sont raisonnablement carrés. Jamais les bandes 40:1 de l’approche naïve.

C’est un algorithme vieux de vingt-cinq ans. Il fonctionne toujours, parce que les rectangles n’ont pas changé.

D’autres variantes de treemap existent : les diagrammes en rayon de soleil (sunburst, secteurs radiaux), les diagrammes en glaçon (icicle, barres hiérarchiques), les strip treemaps (ordonnés mais allongés), le pivot-by-middle (meilleure stabilité quand les données changent). Je les ai considérées brièvement avant de m’en tenir au squarified pour trois raisons. D’abord, il offre parmi les meilleurs rapports d’aspect en pratique de toutes les approches à base de rectangles, essentiel quand on doit afficher des étiquettes dans chaque cellule. Ensuite, il est compatible avec l’ombrage en coussin, qui a besoin de rectangles convexes pour produire des effets de profondeur convaincants. Enfin, c’est le choix le plus courant pour les analyseurs de disque : WinDirStat l’utilise directement. Quiconque a vu un treemap rectangulaire de disque reconnaîtra la disposition.

La contrepartie : comme l’algorithme trie par taille, un petit changement dans les données peut réagencer l’ensemble de la disposition. S’il fallait animer les transitions entre deux scans, le pivot-by-middle mériterait d’être reconsidéré. Pour un analyseur de disque qui scanne une fois et affiche le résultat, la stabilité de la disposition n’est pas un enjeu.

L’approche naïve du découpage en bandes présentée plus haut n’est pas qu’un repoussoir pédagogique. C’est la première chose que j’ai implémentée. Elle produisait des surfaces correctes et des rapports d’aspect calamiteux : cet échec rendait la contribution de l’article squarified évidente, d’une manière que la seule lecture du résumé n’aurait pas permis.

Le premier rendu

Le premier rendu fonctionnel a été un cap. J’avais un scanner qui parcourait le système de fichiers, un moteur squarified qui transformait un arbre de tailles de fichiers en une liste plate de rectangles, et un Canvas SwiftUI qui les dessinait. Les coordonnées étaient justes, les surfaces étaient justes : chaque fichier de mon disque avait son rectangle.

Ça ressemblait à un tableur avec des idées de grandeur.

Les rectangles étaient plats, en aplats de couleur, disposés en grille. Chacun avait un contour net et une étiquette. L’impression visuelle était celle d’un tableau, pas d’une visualisation. Aucun sens de la hiérarchie, aucune profondeur, aucun moyen de saisir d’un coup d’œil quels rectangles étaient des conteneurs et lesquels étaient des feuilles. L’information était là, techniquement ; la perception, non.

L’ombrage en coussin

La solution vient de la même époque que l’algorithme de disposition. Jarke van Wijk et Huub van de Wetering l’ont décrite dans leur article de 1999, « Cushion Treemaps: Visualization of Hierarchical Information », et l’idée centrale est physique : donner à chaque rectangle l’apparence du relief.

Chaque rectangle est modélisé comme une surface légèrement convexe, à la manière d’un coussin de canapé capitonné : plus haute au centre, s’inclinant doucement vers chaque bord. Une source de lumière virtuelle éclaire cette surface d’en haut et légèrement de côté.

La suite relève de l’éclairage 3D classique, détaillé dans l’article sur l’ombrage de Lambert. En résumé : en chaque pixel, la surface pointe dans une direction (sa normale). Si cette normale est orientée vers la lumière, le pixel est clair ; si elle pointe ailleurs, il est sombre. Le produit scalaire entre la normale et la direction de la lumière donne la luminosité, une valeur de 0 à 1. On multiplie par la couleur de base, et on obtient le pixel ombré.

graph LR
    accTitle: Cushion shading computation
    accDescr: A quadratic surface defines height at each pixel. The surface normal is computed from the partial derivatives. A dot product between the normal and the light direction gives pixel intensity from 0 to 1. Multiply by the base color to get the final shaded pixel.
    Q["Surface quadratique<br/>h(x,y) = aₓx² + bₓx + aᵧy² + bᵧy"] --> N["Normale à la surface par pixel<br/>nx = −(2aₓx + bₓ)<br/>ny = −(2aᵧy + bᵧ)<br/>nz = 1.0"]
    L["Direction de la lumière<br/>(lx, ly, lz)"] --> D["Produit scalaire<br/>max(0, N · L / |N|)"]
    N --> D
    D --> I["Intensité<br/>0.0 – 1.0"]
    BASE["Couleur de base<br/>(catégorie de fichier)"] --> OUT["Couleur du pixel"]
    I --> OUT

Les rectangles imbriqués accumulent les paramètres de coussin de leurs ancêtres. Un fichier à l’intérieur d’un répertoire hérite des paramètres du coussin parent et y ajoute les siens. Le résultat : les frontières de répertoire deviennent visibles sous forme de crêtes subtiles dans l’ombrage, sans tracer la moindre bordure. La structure d’imbrication s’inscrit dans le jeu de lumière et d’ombre.

graph TD
    accTitle: Cushion parameter inheritance
    accDescr: The root rectangle has small cushion parameters. A directory inherits and scales those parameters, adding its own offset. A file inherits again, producing stronger curvature. The result is per-pixel brightness highest at the center and darker at the edges.
    ROOT["Paramètres du coussin racine<br/>ax=petit, bx=0"] -->|hérité + mis à l'échelle| DIR["Coussin du répertoire<br/>ax=moyen, bx=décalage"]
    DIR -->|hérité + mis à l'échelle| FILE["Coussin du fichier<br/>ax=grand, bx=décalage"]
    FILE --> PIXEL["Luminosité par pixel<br/>maximale au centre, plus sombre aux bords"]

Après l’ajout de l’ombrage, ça ressemblait enfin à un analyseur de disque.

La version plate était correcte ; la version ombrée était utile. Correct et utile ne sont pas la même chose, et « correct » n’a jamais fait rêver personne.

Pourquoi l’ombrage encode la hiérarchie

Sans ombrage, un répertoire rempli de petits fichiers ressemble à une mosaïque de carrés colorés. On voit les fichiers, pas le répertoire auquel ils appartiennent. L’ombrage change la donne : les fichiers à l’intérieur d’un répertoire se trouvent dans l’ombre du coussin parent, si bien que le conteneur se détache comme tel.

L’œil lit les frontières de luminosité comme des indices de regroupement avant de lire les étiquettes : la hiérarchie est visible avant qu’on ait lu un seul nom de fichier.

Deux problèmes, deux vieilles solutions

Le problème du treemap cachait en réalité deux problèmes distincts : la disposition et le rendu. Les deux avaient de bonnes solutions datant de 1999 ; les deux figuraient dans des articles publiés qu’on pouvait lire en un après-midi.

Les parties difficiles quand on construit une nouvelle application ne sont souvent pas des problèmes nouveaux, mais des problèmes connus qu’on n’a pas encore rencontrés. L’algorithme squarified est dans un article ; l’ombrage de Lambert est dans n’importe quel manuel d’infographie : l’article Wikipédia sur la réflectance lambertienne couvre les mathématiques avec concision. Le vrai travail : trouver la bonne source, comprendre les contraintes, appliquer la solution à son cas particulier.

Ce qui ressemble à un problème de rectangle est en général un problème de lecture. Le rectangle n’était pas en cause : on n’avait pas encore lu le bon article.

Références

• Bruls, M., Huizing, K., van Wijk, J.J. (2000). Squarified Treemaps. Proceedings of the Joint Eurographics and IEEE TCVG Symposium on Visualization.
• van Wijk, J.J., van de Wetering, H. (1999). Cushion Treemaps: Visualization of Hierarchical Information. IEEE Symposium on Information Visualization.
• Shneiderman, B. (1992). Tree visualization with tree-maps: 2-d space-filling approach. ACM Transactions on Graphics.
• Wikipedia: Treemapping, Lambertian reflectance