Un TAD pour éditeurs de diagrammes

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 :

• diagrammes de classes ;
• diagrammes d'objets ;
• diagrammes syntaxiques ;
• réseaux sémantiques ;
• automates ;
• réseaux de PETRI ;
• théorie des graphes ;
• théorie des catégories et diagram chasing,

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.

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

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

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).

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.

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 5^e 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.

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).

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

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

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.

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

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.

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

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.

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 persistant▲

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é▲

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▲

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▲

let intersect s r =
  directed_path none id1 id1 id1 id1 id1 some s r

VIII-E. Recherche d'un rectangle▲

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▲

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