I. Introduction


Autrefois réservé à l'édition de schémas électroniques et au routage de circuits imprimés, l'éditeur de diagrammes est un utilitaire qui aujourd'hui ne dépareille plus dans la boîte à outils de l'informaticien moderne. Il est bien loin le temps où l'on se gaussait des ordigrammes qui, on en était certain, ne remplaceraient jamais le pseudocode.

Car si les diagrammes ont bien échoué dans la représentation de bas niveau, leur succès n'en est pas moins grand dans la communication et la représentation de haut niveau.
Les domaines embrassés par cet engouement sont tellement multiples :


que l'ensemble du secteur est touché, du plus praticien au plus théoricien.

Considérant l'ampleur de cet engouement il paraît surprenant de constater le manque de maturité des outils disponibles.

De simples listes chaînées ont toujours très bien fait l'affaire pour manipuler les fameuses fenêtres qui ont supplanté la ligne de commande. C'est pourquoi il a été tentant de croire qu'une structure linéaire était assez bien adaptée pour la représentation bidimensionelle. Le résultat ce sont des manipulations saccadées, des connexions flottantes, et plus généralement l'absence ou la pauvreté de l'assistance à la cohérence d'ensemble. Bref tout ce qui fait aujourd'hui la frustration à utiliser un éditeur de diagrammes. On a fini par accepter de peiner pour faire des schémas propres.

II. Domaine


D'une façon générale, on peut dire que l'édition de schémas consiste à relier des boîtes par des connecteurs :

Image non disponible



En effet, dans sa représentation interne, le schéma ci-dessus n'est pas fondamentalement différent du schéma ci-dessous :

Image non disponible



où toutes les boîtes sont des rectangles et tous les connecteurs sont des lignes verticales (rectangles de largeur nulle) ou horizontales (rectangles de hauteur nulle).

III. Type Abstrait de Données


Il s'agit bien entendu d'une partition du plan dont le pivot serait un rectangle.

Cette définition nous rapproche du quadtree, un type abstrait de données qui partitionne le plan et dont le pivot est un point.

Un quadtree découpe le plan en quatre quadrants, Nord-Ouest, Nord-Est, Sud-Ouest et Sud-est.
Cette dichotomie du plan est parfaite, car tout point est inclus dans l'un des quatre quadrants.

Image non disponible

L'algorithme de quadtree est traditionnellement une méthode de traitement de l'image dont elle permet une segmentation en régions (voir le tutoriel Segmentation en régions par Xavier Philippeau).
Le logiciel Fractint (rendu d'images fractales) a popularisé le quadtree en l'utilisant pour accélérer le rendu d'images fractales. La fractale est récursivement découpée en quatre quadrants afin de détecter au mieux l'intérieur des régions connexes de l'image. Ces régions sont alors affichées par un simple remplissage de couleur plutôt que par un coûteux calcul point par point.



Alors pouvons-nous réutiliser la conception du quadtree pour l'adapter au rectangle ?
Oui et non :

  • oui, car chacun des quatre coins du rectangle définit naturellement son quadrant associé ;
  • non, car la dichotomie ne pourra pas être parfaite, certains rectangles ne seront entièrement inclus dans aucun de ces quatre quadrants.

Le rectangle ouvre dans le plan un 5e espace de recherche en forme d'une croix centrée sur lui et qui s'étend aux quatre points cardinaux.
Un rectangle n'est inclus dans aucun quadrant si et seulement si son intersection avec cette croix n'est pas vide.
On est là en présence de deux définitions complémentaires de l'appartenance :

  • l'appartenance à un quadrant est plus restrictive, elle se fait par inclusion ;
  • l'appartenance à la croix interquadrants est plus large, elle se fait par simple intersection.
Image non disponible

Un rectangle est un intervalle à deux dimensions borné par (xmin,xmax,ymin,ymax).
La dichotomie est possible, car il existe une relation d'ordre partiel sur l'ensemble des intervalles.
Quant à la croix interquadrants, c'est le prix à payer pour l'absence d'une relation d'ordre total.

Une droite, ou un segment de droite partitionne le plan en deux demi-plans.
Il n'y a donc pas d'obstacle théorique à inclure des segments quelconques (non parallèles aux axes) dans une structure de partition du plan. Nous avons toutefois écarté cette possibilité afin de ne pas encombrer le discours avec trop de cas particuliers.

Voyons maintenant comment définir efficacement les opérations habituelles sur les rectangles hiérarchisés par notre nouveau TAD (Type Abstrait de Données).

IV. Recherche d'un rectangle


Une opération indispensable pour toute application interactive c'est la recherche.
Soit un point (x,y) du plan (typiquement le lieu d'un évènement de pointage), on veut retrouver efficacement le rectangle (c'est-à-dire la boîte) désigné par l'utilisateur (pour le sélectionner, le déplacer, le redimensionner…).

C'est typiquement le genre de requête qu'une structure dichotomique permet d'accélérer considérablement.
En effet, considérons un rectangle pivot :

  • les chances sont grandes pour que le lieu du pointage se situe dans l'un des quatre quadrants, l'espace de recherche est alors divisé par 4
  • dans le cas contraire le point est dans la croix et l'espace de recherche est alors amputé des quatre quadrants
 
Sélectionnez
boucle
   choisir
   ou bien l'arbre est vide alors
      le point ne désigne aucun rectangle
   ou bien le point est dans le rectangle pivot alors
      on a trouvé le rectangle désigné
   ou bien le point est dans le quadrant NO alors
      on poursuit la recherche dans le sous-arbre NO
   ou bien le point est dans le quadrant NE alors
      on poursuit la recherche dans le sous-arbre NE
   ou bien le point est dans le quadrant SO alors
      on poursuit la recherche dans le sous-arbre SO
   ou bien le point est dans le quadrant SE alors
      on poursuit la recherche dans le sous-arbre SE
   sinon // le point est dans la croix
      on poursuit la recherche dans le sous-arbre NSWE
   fin choisir
fin boucle

V. Intersection avec un rectangle


Une autre opération indispensable pour une application interactive c'est l'intersection.
On veut ajouter une boîte, ou bien déplacer une boîte, et alors :

  • soit l'application interdit que deux boîtes se superposent ;
  • soit l'application adopte un rendu spécial lorsqu'une boîte est couverte par une autre.


Dans les deux cas, il faut d'abord identifier les deux rectangles qui se croisent.
Pour ce faire on suit la décomposition du plan selon nos quatre quadrants, pour décider si notre rectangle est dans un cadran il nous suffira de comparer le coin du rectangle pivot avec le coin qui lui est opposé par notre rectangle.

Image non disponible
 
Sélectionnez
boucle
   choisir
   ou bien l'arbre est vide alors
      l'intersection est vide
   ou bien le rectangle croise le rectangle pivot alors
      on a trouvé une intersection
   ou bien le coin SE est dans le quadrant NO du pivot alors
      on poursuit la recherche dans le sous-arbre NO
   ou bien le coin SO est dans le quadrant NE du pivot alors
      on poursuit la recherche dans le sous-arbre NE
   ou bien le coin NE est dans le quadrant SO du pivot alors
      on poursuit la recherche dans le sous-arbre SO
   ou bien le coin NO est dans le quadrant SE du pivot alors
      on poursuit la recherche dans le sous-arbre SE
   sinon // le rectangle et la croix ont une intersection non vide
      on poursuit la recherche dans le sous-arbre NSWE
   fin choisir
fin boucle

VI. Insertion d'un rectangle


Dernière opération indispensable : on veut ajouter une boîte dans notre arbre.

Même méthode que pour l'intersection : pour chaque coin du rectangle le coin opposé du rectangle pivot sert de discriminant.

 
Sélectionnez
boucle
   choisir
   ou bien l'arbre est vide alors
      son père est le père du rectangle à ajouter
   ou bien le rectangle croise le rectangle pivot alors
      on a trouvé une intersection
   ou bien le coin SE est dans le quadrant NO du pivot alors
      on ajoute le rectangle au sous-arbre NO
   ou bien le coin SO est dans le quadrant NE du pivot alors
      on ajoute le rectangle au sous-arbre NE
   ou bien le coin NE est dans le quadrant SO du pivot alors
      on ajoute le rectangle au sous-arbre SO
   ou bien le coin NO est dans le quadrant SE du pivot alors
      on ajoute le rectangle au sous-arbre SE
   sinon // le rectangle et la croix ont une intersection non vide
      on ajoute le rectangle au sous-arbre NSWE
   fin choisir
fin boucle

VII. Conclusion


On pourra faire remarquer que parmi les cinq sous-arbres du TAD proposé :

  • seuls quatre effectuent une opération de division comparable à un arbre de recherche ;
  • le 5e effectue une soustraction comparable à une liste chaînée.


Il y a cependant une différence fondamentale entre notre sous-arbre NSWE et la queue d'une simple liste chaînée :

  • à chaque nœud une liste chaînée ne soustrait qu'un simple rectangle à l'espace de recherche ;
  • à chaque nœud notre espace en croix soustrait quatre quadrants à l'espace de recherche.


Intuitivement notre TAD paraît donc une solution simple et efficace pour partitionner le plan à l'aide d'un ensemble de rectangles.

VIII. Annexe A. Implémentation avec Objective-Caml


Il fait chaud et la tentation est grande de programmer comme un chameau.
Le lecteur inaverti des dangers du désert pourra s'épargner une expérience pénible en choisissant de se contenter du pseudocode plutôt que de s'aventurer dans ces contrées inhospitalières.

VIII-A. Type Inductif persistent


Sans surprise, le type inductif est semblable à un arbre binaire de recherche.

Chaque nœud porte :

  • les bornes d'un intervalle à deux dimensions ;
  • les quatre sous-arbres pour l'inclusion dans les quatre quadrants nw, ne, sw et se ;
  • le sous-arbre nswe pour l'intersection avec la croix centrée sur le rectangle pivot.
 
Sélectionnez
type shape =
  | Nil
  | Rect of rect
and rect =
  {
  xmin:int;
  xmax:int;
  ymin:int;
  ymax:int;
  nw:  shape;
  ne:  shape;
  sw:  shape;
  se:  shape;
  nswe: shape;
  }

VIII-B. Notion de chemin dirigé


Ce qui nous importe vraiment c'est une façon de parcourir la structure de données.
Mais pas n'importe quelle façon, une façon particulière.
Celle qui partant de la racine de l'arbre suit le chemin désigné par le rectangle qui nous intéresse.
Nous appellerons r ce rectangle qui dirige le cheminement à travers un arbre s.

La fonction directed_path capture assez bien la notion de chemin dirigé par un rectangle r à travers un arbre s :

  • la fonction nil dit que faire de l'arbre vide ;
  • les fonctions nw, ne, sw, se et nswe disent que faire pour chacune des cinq directions possibles ;
  • la fonction overlap dit que faire en cas de recouvrement de deux rectangles.
 
Sélectionnez
let directed_path nil nw ne sw se nswe overlap s r =
  let rec helper s =
    match s with
    | Nil -> nil r
    | Rect t ->
        if r.ymax < t.ymin then
          if r.xmax < t.xmin then nw (helper t.nw) t
          else if r.xmin > t.xmax then ne (helper t.ne) t
          else nswe (helper t.nswe) t
        else if r.ymin > t.ymax then
          if r.xmax < t.xmin then sw (helper t.sw) t
          else if r.xmin > t.xmax then se (helper t.se) t
          else nswe (helper t.nswe) t
        else overlap t
  in helper s

VIII-C. Prélude


Chaque chamelier a probablement un petit fichier prelude.ml contenant quelques définitions triviales.
En voici quatre qui figurent dans le mien, rien de bien méchant ici :

  • id1 est la fonction identité sur le 1er argument ;
  • id2 est la fonction identité sur le 2nd argument ;
  • none est un constructeur pour rien ;
  • some est un constructeur pour quelque chose.
 
Sélectionnez
let id1 x y = x
let id2 x y = y
let none x = None
let some x = Some x

VIII-D. Intersection avec un rectangle


Cette opération est une application triviale du cheminement dirigé :

 
Sélectionnez
let intersect s r =
  directed_path none id1 id1 id1 id1 id1 some s r

VIII-E. Recherche d'un rectangle


Cette opération est également une application du cheminement dirigé, il suffit de créer un rectangle r aux dimensions du point (x,y) :

 
Sélectionnez
let find s x y =
  directed_path none id1 id1 id1 id1 id1 some s
  {xmin=x;xmax=x;ymin=y;ymax=y;nw=Nil;ne=Nil;sw=Nil;se=Nil;nswe=Nil}

VIII-F. Insertion d'un rectangle


C'est encore une application du cheminement dirigé, cette fois-ci il faut copier consciencieusement le chemin qui mène de la racine jusqu'à la nouvelle feuille :

 
Sélectionnez
let insert s r =
  directed_path
  (fun x -> Rect x)
  (fun h t ->  Rect {t with nw=h})
  (fun h t ->  Rect {t with ne=h})
  (fun h t ->  Rect {t with sw=h})
  (fun h t ->  Rect {t with se=h})
  (fun h t ->  Rect {t with nswe=h})
  (fun x -> failwith "insert")
  s r

Le cas d'échec correspond à la tentative d'insertion d'un rectangle qui croise un autre rectangle présent dans l'arbre.
Pour autoriser ce cas, il suffirait de poursuivre l'insertion dans le sous-arbre NSWE.