Chapitre 6

Placement spatial à base de contraintes

1 Introduction

Ce chapitre décrit le placement spatial que nous voulons mettre en oeuvre dans Madeus. Son implémentation sera décrite dans le chapitre .

Ce placement consiste en un positionnement relatif des éléments à l'intérieur d'un même niveau de structure. Il s'exprime par des relations symétriques entre les éléments, relations qui doivent être prises en compte immédiatement et maintenues tant qu'elles sont définies (chapitre ).

La problématique de se placement peut s'exprimer sous forme d'un système de contraintes. C'est pourquoi nous avons étudié dans les chapitres précédents les techniques de résolution de contraintes et plus particulièrement la technique de maintien de solution par propagation locale. Cette étude a abouti au choix du résolveur de contraintes DeltaBlue.

Cependant, nous avons vu que ce dernier (et la technique de propagation locale en général) ne gère pas les cycles de contraintes ni les contraintes d'inégalité. Or, ces types de contraintes s'avèrent indispensables dans un problème de placement d'objets et il convient d'apporter des réponses.

Face à ces limitations, nous avons redéfini les types de relations spatiales initialement prévues pour limiter les possibilités de cycles et d'inégalité. Nous avons également développé un algorithme spécifique pour traiter le problème des relations redondantes exprimées par l'auteur et qui se traduisent également par des cycles de contraintes.

La deuxième section de ce chapitre présente les principes du placement spatial mis en oeuvre dans Madeus. La troisième section décrit le jeu de relations spatiales définies. La quatrième section présente le fonctionnement général du placement spatial à base de contraintes dans Madeus. La cinquième section présente les limitations apportées par rapport aux spécifications initiales. La dernière section présente l'algorithme développé pour gérer les contraintes redondantes exprimées par l'auteur.

2 Principes

Dans cette section, nous présentons les principes généraux du placement spatial dans Madeus. Ils concernent :

2.1 Représentation spatiale d'un élément

Tous les éléments d'un document Madeus, exceptés les éléments de base de type Audio possèdent une représentation graphique sous forme de boîte correspondant au plus petit rectangle englobant l'élément. Chaque élément possède six paramètres représentant les quatre bords (gauche, droit, supérieur, inférieur) et les deux dimensions (largeur, hauteur) de cette boîte (Fig 1 ).

Image placement_boite.gif

Fig 1. Représentation graphique des éléments

2.2 Placement relatif

Le placement spatial des éléments dans Madeus est un placement relatif où l'auteur définit des relations entre des éléments d'un même élément composite. Les relations spatiales entre deux éléments n'appartenant pas au même composite ou bien entre un élément et son composite ne sont pas acceptées dans la version actuelle de Madeus.

Les relations définies par l'auteur sont des relations binaires. Elles font intervenir un élément de référence et un élément secondaire qui est éventuellement déplacé par l'application de la relation. Dans l'exemple de la Fig 2 , l'auteur définit une relation d'alignement gauche pour un élément B par rapport à un élément A.

Image placement_relation.gif

Fig 2. Placement relatif de deux éléments A et B

Ce placement s'effectue de façon équivalente selon l'axe vertical et l'axe horizontal du document. Dans le cadre de cette étude, nous traitons les relations sur chacun des deux axes de façon indépendante.

2.3 Symétrie des relations

Une relation spatiale est définie entre un élément de référence et un élément secondaire. A l'établissement de la relation, l'élément secondaire est placé par rapport à l'élément de référence. Par la suite, nous ne faisons plus la distinction entre l'élément de référence et l'élément secondaire, l'un et l'autre jouent un rôle identique dans la relation.

2.4 Types de relations

Dans Madeus, nous avons considéré deux types de relations spatiales : les relations intrinsèques et les relations explicites.

Les relations intrinsèques correspondent aux relations générées automatiquement à la définition d'un élément. Elles sont au nombre de deux par élément : bord_droit = bord_gauche + largeur, bord_inférieur = bord_supérieur + hauteur. Ces relations doivent être constamment maintenues, c'est pourquoi elles sont définies avec une priorité maximale.

Les relations explicites correspondent aux relations exprimées par l'auteur. Par souci de simplicité, aucun niveau de priorité n'est spécifié par l'auteur et ces relations sont toutes de priorité maximale. Cela correspond en plus à la volonté de prendre en compte chacune des relations spatiales définies par celui-ci.

2.5 Relations et contraintes

L'ensemble des paramètres des éléments (bords, dimensions) ainsi que les relations intrinsèques et explicites sont traduites dans un système de contraintes géré par le résolveur. Les paramètres et les distance spécifiées dans certaines relations constituent les variables de ce système. Les relations entre les éléments en constituent les contraintes (une relation est représentée par une contrainte). Ainsi, une relation d'alignement est traduite par une contrainte d'égalité entre deux variables représentant les bords. Une relation d'espacement entre deux éléments est traduite par une contrainte de somme entre trois variables, deux d'entre elles représentant les bords des éléments reliés, la troisième représentant la distance exprimée.

La Fig 3 présente le système de contraintes sur l'axe vertical obtenu par la déclaration de deux éléments A et B et par la définition d'une relation d'alignement sur leur bord gauche.

Image placement_contrainte2.gif

Fig 3. Traduction d'une relation en contrainte

Le résolveur détermine ensuite la valeur des variables du système de contraintes en fonction de leur valeur initiale et des actions de l'auteur, comme le déplacement d'éléments, l'ajout ou le retrait de relations. Ces variables définissent la position relative des éléments à l'intérieur de leur élément composite.

Dans la suite de ce chapitre, nous utiliserons le terme relation au niveau de Madeus et le terme contrainte au niveau du résolveur.

3 Jeu de relations spatiales mis en oeuvre

Dans le cadre de ce mémoire, nous n'avons pas cherché à offrir un ensemble exhaustif de relations mais seulement celles qui paraissaient les plus utiles. Nous avons classé les relations en différentes catégories :

3.1 Relations d'alignement

Ces relations traduisent l'alignement d'un bord de l'élément secondaire () par rapport au même bord de l'élément de référence ().

3.2 Relations de centrage

Ces relations traduisent l'égalité d'un axe médian de l'élément secondaire par rapport au même axe médian de l'élément de référence.

3.3 Relations d'espacement

Ces relations expriment une distance entre un bord de l'élément secondaire et le bord opposé de l'élément de référence. Elles peuvent signifier un espacement, un recouvrement ou bien une juxtaposition si la distance exprimée est nulle. Afin de ne pas multiplier le nombre de relations disponibles, nous avons décidé de n'utiliser qu'une seule relation pour ces trois placements, la différence s'effectuant selon la valeur de la distance. Ainsi une distance positive représente un espacement entre les éléments, une distance négative un recouvrement et une distance nulle une juxtaposition. Les icônes ci-dessous symbolisent une distance positive.

3.4 Relations de décalage

Ces relations expriment une distance entre un bord de l'élément secondaire et le bord identique de l'élément de référence. De même que les relations précédentes, celles-ci peuvent générer trois placements différents : décalage dans un sens ou dans l'autre ou bien alignement si la distance exprimée est nulle (ces relations sont alors identiques à celles de la section 3.1). Là aussi nous avons décidé de n'utiliser qu'une seule relation pour exprimer ces trois placements. Une distance positive représente un décalage dans le sens indiqué par les icônes, une distance négative un décalage dans le sens inverse.

Pour les deux dernières catégories de relations (espacement et décalage), la distance spécifiée est exprimée en pixels. D'autres unités devront à terme pouvoir être utilisées (millimètre, centimètre, etc.).

4 Vue d'ensemble du placement spatial dans Madeus

Par analogie avec l'aspect temporel des documents Madeus (0), nous appelons gestionnaire spatial l'ensemble des opérations portant sur la dimension spatiale des documents. C'est lui qui détermine la position souhaitée des éléments sur l'écran en fonction des actions de l'auteur. Nous présentons d'abord l'architecture générale de ce gestionnaire spatial puis, le processus d'édition/présentation spatiale d'un document Madeus.

4.1 Architecture générale du gestionnaire spatial

Le gestionnaire spatial de Madeus est composé de trois modules : le module de traitement des relations, le module de gestion des relations redondantes et le module de maintien de solution (Fig 4 ).

Image placement_architecture.gif

Fig 4. Fonctionnement du gestionnaire spatial dans Madeus

4.2 Processus d'édition/présentation spatiale

Le gestionnaire spatial de Madeus construit la représentation graphique d'un document à partir de l'attribut de positionnement des éléments et des relations spatiales définies par l'auteur. L'attribut de positionnement, introduit par la balise <POS> dans les documents Madeus, contient les informations relatives à la représentation graphique d'un élément (dimensions, coordonnées). Il est présent pour tous les éléments, excepté pour les éléments de base de type Audio. Les relations spatiales sont définies au niveau d'un élément composite pour les éléments qui le composent. Elles peuvent être présentes initialement dans le document et/ou être ajoutées ou retirées de façon interactive par l'auteur lors de la phase d'édition du document.

Le système d'édition de Madeus permet de combiner les phases de présentation et d'édition d'un document multimédia (0.0). Au niveau spatial, l'édition d'un document commence dès son chargement, se poursuit par des opérations d'édition effectuées par l'auteur et se termine lors de la sauvegarde du document.

4.2.1 Chargement d'un document

Lors du chargement d'un document, les attributs de positionnement sont transformés en variables et les relations intrinsèques aux éléments sont traduites sous forme de contraintes. Les variables et les contraintes ainsi obtenues forment le système de contraintes initial.

Le gestionnaire spatial analyse ensuite les relations spatiales du document. Si au niveau d'un élément composite il n'y a pas de relations spatiales, alors les éléments sont positionnés dans l'élément composite grâce à leur attribut <POS>. En considérant les éléments composites de façon récursive, on obtient le placement absolu des éléments à l'écran.

Si des relations spatiales sont présentes initialement dans le document, alors leur traitement est identique à celui effectué pour l'ajout d'une relation en phase d'édition (4.2.2).

4.2.2 Opérations d'édition spatiale

Les opérations d'édition spatiale dans Madeus concernent pour l'instant l'ajout ou le retrait de relations et le déplacement des éléments. Ces opérations s'effectuent de manière incrémentale par l'intermédiaire de l'interface utilisateur de Madeus.

Ajout d'une relation

Lorsque l'auteur ajoute une relation R entre un élément de réference A et un élément secondaire B, le gestionnaire spatial effectue au préalable une phase de vérification. Il contrôle que les éléments reliés appartiennent au même élément composite et vérifie également la cohérence de la relation avec les relations spatiales précédentes (section 6).

Si la relation est acceptée, alors elle est traduite sous forme de contrainte puis envoyée au résolveur. La contrainte générée relie une variable relative à A (référence) à une variable relative à B (secondaire). L'ajout de la nouvelle contrainte dans le système provoque une perturbation de la solution courante. Pour rétablir la cohérence du système, le résolveur modifie la variable B, de manière à respecter la nouvelle contrainte, puis propage cette modification dans le graphe de contraintes. Le résultat de cette opération est que la variable B et toutes les variables liées avec elle sur le même axe de référence sont mises à jour. Les éléments concernés sont affichés avec leur nouvelle position, ce qui provoque leur déplacement à l'écran.

Retrait d'une relation

Pour le retrait d'une relation spatiale, le gestionnaire vérifie d'abord l'existence d'une relation entre les éléments sélectionnés selon l'axe de référence exprimé.

Si une telle relation existe, alors elle est supprimée et la contrainte associée est retirée du système de contraintes courant. Le retrait d'une contrainte ne modifie pas la solution courante et les variables du système continuent de vérifier l'ensemble des contraintes spécifiées. Il n'y a donc pas de mise à jour de variables et par conséquent, aucun déplacement d'élément à l'écran.

Déplacement d'un élément

Le déplacement d'un élément par l'auteur se traduit par la création de deux contraintes d'entrée, une pour chacun des deux axes de référence. Ces contraintes stipulent une égalité entre les bords gauche et supérieur de l'élément avec le déplacement de la souris sur l'axe correspondant. L'introduction de ces contraintes dans le système courant provoque la modification des variables associées aux deux bords précédents et par propagation, la mise à jour de toutes les variables qui leurs sont liées. Les éléments concernés par ces mises à jour sont affichés avec leurs nouvelles coordonnées, ce qui provoque leur déplacement à l'écran. Ce mécanisme permet de prendre en compte les modifications provoquées à chaque mouvement de la souris et ainsi, permet d'obtenir un déplacement continu des éléments.

Lors du déplacement d'un élément, nous effectuons une phase de planification initiale qui construit deux plans contenant les séquences des mises à jour effectuées par le résolveur pour chacun des deux axes de référence. Ces plans sont ensuite exécutés en séquence à chaque mouvement de la souris ce qui permet de réduire le temps d'obtention d'une nouvelle solution.

4.2.3 Sauvegarde d'un document

Lorsque le document est sauvegardé, la valeur courante des variables du système de contraintes est copiée dans le paramètre correspondant de l'attribut <POS> de chacun des éléments. Les relations explicites sont copiées au niveau de l'élément composite auxquelles elles se rapportent.

4.3 Problème de visualisation de contraintes

Un des problèmes qui se posent en utilisant des relations pour exprimer le placement des éléments est celui de leur visualisation. Ce problème n'est pas spécifique au placement spatial des éléments, il se pose en termes similaires pour leur placement temporel. Il fait d'ailleurs l'objet d'une étude en cours au sein du projet Opéra , c'est pourquoi ce sujet n'est pas traité de façon approfondie dans ce mémoire. Néanmoins, nous avons mis en oeuvre une solution "minimale" qui consiste à distinguer les éléments qui sont reliés sur un même axe de référence avec un élément sélectionné. Ainsi lorsque l'auteur pointe sur un élément (de façon spécifique pour chacun des deux axes de référence), un cadre apparaît autour des éléments reliés avec celui-ci.

L'exemple de la Fig 5 montre les relations spatiales de l'élément central Planet Earth sur l'axe vertical. Il possède quatre relations explicites avec les éléments Hubble One, Hubble Two, Hubble Three et Hubble Four. Cela donne une vue instantanée de toutes les relations auxquelles participe un élément particulier sur un axe de référence. Par contre, la nature de la relation entre deux éléments n'est pas spécifiée.

Image pla_visualisation.gif

Fig 5. Visualisation d'éléments reliés

5 Limitations apportées

Nous avons vu au chapitre précédent que la technique de maintien de solution par propagation locale ne gère ni les contraintes cycliques ni les contraintes non fonctionnelles, en particulier les contraintes d'inégalité. Afin d'éviter les configurations spatiales qui génèrent de telles contraintes, nous avons limité les relations de placement initialement prévues.

5.1 Relations exclusives

Nous avons considéré les relations sur un même axe comme étant exclusives les unes des autres. La définition d'une relation entre deux éléments sur un axe de référence annule et remplace la précédente relation qui pouvait exister entre ces deux éléments sur le même axe. Si l'on spécifie par exemple une relation d'alignement droit entre deux éléments suivie d'une relation d'alignement gauche entre ces mêmes éléments, alors l'alignement droit n'est pas maintenu.

Ce choix repose sur deux considérations. D'une part, il correspond à un comportement plus naturel du système pour l'auteur. En effet, la seule façon de satisfaire les deux contraintes d'alignement précédentes serait de retailler un des éléments, ce qui ne correspond pas forcément à la volonté de l'auteur. D'autre part, la définition de deux contraintes sur le même axe génère un cycle de relations et donc un cycle de contraintes que le résolveur ne sait pas gérer (Fig 6 ).

Image pla_exclusive.gif

Fig 6. Cycle généré par deux contraintes sur le même axe

5.2 Relations sur les dimensions

Les relations sur les dimensions des éléments peuvent également générer des cycles dans le système de contraintes. Si par exemple on définit une relation d'alignement droit et une relation d'égale largeur entre deux éléments A et B, alors on obtient un cycle de contraintes (Fig 7 ).

Image pla_dimension.gif

Fig 7. Exemple de contrainte cyclique sur les dimensions

Ce problème pourrait être géré de la même façon que le problème précédent en considérant les relations sur les dimensions des éléments comme étant exclusives avec les relations de placement sur le même axe. Ainsi, les relations d'alignement gauche, d'alignement droit, de centrage vertical et les relations sur la largeur d'un élément seraient mutuellement exclusives sur l'axe vertical.

Cependant, ce choix génère un certain nombre de problèmes. D'abord le comportement obtenu pourrait être gênant pour l'auteur. Dans l'exemple de la Fig 8 , celui-ci définit une relation d'alignement gauche entre deux éléments A et B de taille différente (a). Leur déplacement est donc solidaire (b). S'il définit maintenant une relation spécifiant que la largeur de B est égale à la largeur de A, alors B est retaillé (c) mais les deux éléments ont perdu leur relation d'alignement (d), alors que l'auteur n'a pas supprimé explicitement cette relation. Ce comportement n'est donc pas satisfaisant pour lui.

Image pla_pbdim.gif

Fig 8. Exemple de comportement avec des relations exclusives sur les positions et sur les dimensions

De plus, en faisant le choix de l'exclusion mutuelle, on traite de la même façon les relations concernant la position des éléments et les relations concernant leur dimension alors qu'elles sont conceptuellement différentes.

Enfin, le redimensionnement pose un certain nombre de problèmes techniques (mises en lignes d'un élément textuel retaillé, retaillage des images et des vidéo, etc.) qu'il n'aurait pas été possible de traiter complètement dans le cadre de ce stage.

Pour ces raisons et afin d'obtenir une première solution de placement spatial dans Madeus, nous avons choisi de ne pas prendre en compte dans ce mémoire les relations sur les dimensions des éléments.

5.3 Relations quantitatives

Les relations spatiales de type qualitatif comme "A Droite de" ou "Au dessus de" qui se traduisent par des contraintes d'inégalité ne sont pas non plus définies. Les relations possibles sont de type quantitatif avec la spécification d'un paramètre ("A droite de (t)", "Au dessus de (t)", ...).

5.4 Problèmes subsistants

Malgré ces restrictions, certains problèmes liés à la présence de cycles subsistent et notamment dans la cas de la définition de relations redondantes. En effet, si l'auteur définit une relation d'Alignement_Inférieur entre deux éléments A et B puis, une relation de Centrage_Horizontal entre les éléments B et C, alors il existe de façon implicite une relation sur l'axe horizontal entre les éléments A et C (Fig 9 ). Cette relation se traduit par le fait qu'un déplacement vertical de A entraîne un déplacement identique de C et inversement, bien que l'auteur n'ait pas spécifié de relations entre A et C sur l'axe horizontal. Si l'auteur n'a pas connaissance de cette information et définit une relation entre A et C sur cet axe, alors cela introduit un cycle dans le système de contraintes. Le résolveur, ayant détecté le cycle, stoppe la propagation et renvoie un message d'erreur. Ce fonctionnement n'est pas satisfaisant pour l'auteur, c'est pourquoi nous avons décidé d'étudier plus spécialement ce problème.

Image pla_implicite.gif

Fig 9. Exemple de relation implicite

6 Traitement des cycles issus de relations redondantes

Dans la configuration de la Fig 9 et si l'auteur introduit une nouvelle relation entre A et C, deux scénarios sont possibles :

6.1 Types de relations

L'idée générale de ce traitement est d'accepter la définition des relations redondantes mais de ne pas les traduire sous forme de contraintes car elle généreraient des cycles que le résolveur ne sait pas traiter. Comme ces relations sont redondantes avec les relations déjà présentes, l'information qu'elles contiennent n'est pas nécessaire au résolveur pour maintenir les positions des éléments dans une configuration cohérente avec l'ensemble des relations exprimées. Néanmoins, nous devons garder une connaissance spécifique de ces relations car le retrait d'autres relations peut faire qu'elles ne soient plus redondantes. En effet, sur l'exemple de la Fig 9 si l'auteur supprime la relation d'alignement entre les éléments A et B, alors la relation entre A et C n'est plus redondante et elle doit être connue du résolveur afin que ce dernier puisse garder cohérent l'ensemble des relations exprimées par l'auteur.

Pour gérer cela, nous avons défini trois types de relations :

La notion de relation active ou latente est supportée uniquement au niveau du système pour éviter d'introduire dans le résolveur des contraintes redondantes qui généreraient des cycles. Cette distinction n'est pas connue de l'auteur et toutes les relations qu'il définit sont pour lui de même type. De même, elle n'apparaît pas au niveau du document où toutes les relations explicites (actives ou latentes) sont sauvegardées de la même façon.

Pour gérer les transitions entre les différents types de relations, nous avons développé un algorithme spécifique.

6.2 Algorithme de gestion des types de relations

L'algorithme mis en oeuvre consiste d'une part à gérer les transitions des relations d'un type à un autre en fonction des actions de l'auteur et d'autre part à ne transmettre au résolveur que les contraintes qu'il est capable de maintenir, c'est-à-dire celles associées aux relations actives. Il est appelé à chaque fois que l'auteur ajoute ou retire une relation. Il possède donc deux points d'entrée qui sont les procédures Ajout_Relation et Retrait_Relation. Les autres procédures sont des procédures internes à l'algorithme dont le but est de maintenir de façon incrémentale la fermeture transitive des relations.

Les traitements effectués par cet algorithme ne concernent que les relations définies sur un même axe de référence. L'axe sur lequel porte la relation détermine cet axe de référence. Les procédures appelées sont écrites en gras.

6.2.1 Ajout d'une relation

Cette procédure est appelée lors de la définition d'une nouvelle relation entre deux éléments elem1 et elem2 d'un élément composite Elem.

S'il n'existe aucune relation entre les deux éléments elem1 et elem2, alors l'ajout d'une nouvelle relation se traduit par la création d'une relation active (avec la création de la contrainte associée) et par la génération des relations induites qui en dépendent (3-9).

S'il existe une relation induite ou latente entre les deux éléments elem1 et elem2, alors il faut vérifier la cohérence de la nouvelle relation avec la configuration courante. Si elle n'est pas cohérente, alors l'ajout est impossible. Si elle est cohérente, alors la relation existante est supprimée et la nouvelle relation est ajoutée avec le type latente (10-19).

S'il existe une relation active entre les deux éléments elem1 et elem2, alors il faut distinguer deux cas selon l'existence ou non d'une relation latente. En effet, les relations exprimées par l'auteur étant exclusives sur un même axe, la nouvelle relation entraîne la suppression préalable de la relation existante entre elem1 et elem2 (procédure Retrait_Relation). Or, s'il existe une relation latente, cette dernière devient active et de ce fait, la relation entre elem1 et elem2 devient induite (6.2.4). Dans ce cas, l'ajout de la nouvelle relation active entre elem1 et elem2 se ramène au cas précédent où il existait une relation induite entre ces deux éléments. Le traitement effectué est donc identique à savoir une phase de vérification préalable et selon le résultat, un refus de l'ajout ou la création d'une relation latente (21-29). Dans le cas où il n'existe pas de relation latente, alors la relation active entre elem1 et elem2 est supprimée (avec suppression de la contrainte associée) et la nouvelle relation active est ajoutée avec création de la contrainte associée (31-35).


Procédure Ajout_Relation (RelId, elem1, elem2)

{

1. R = Relation (elem1, elem2)

2. /* Recherche de l'existence d'une relation

sur le même axe de référence */

3. si (R inexistante) alors

4. création de RelId(elem1, elem2) active

5. /* La relation RelId est traduite sous forme

de contrainte envoyée au résolveur */

6. création de la contrainte associée

7. Generation_Relations_Induites (RelId, elem1, elem2)

8. Sortie Procédure

9. fsi

10. si (R induite) ou (R latente)

11. /* Vérification de la cohérence de RelId

par rapport à la position courante */

12. si RelId non cohérente alors

13. Ajout impossible

14. sinon

15. suppression de R

16. création de RelId(elem1, elem2) latente

17. fsi

18. Sortie Procédure

19. fsi

20. si (R active) alors

21. si (il existe une relation latente dans le graphe) alors

22. /* Vérification de la cohérence de RelId

par rapport à la position courante */

23. si RelId non cohérente alors

24. Ajout impossible

25. sinon

26. Retrait_Relation (R, elem1, elem2)

27. /* La contrainte associée est supprimée */

28. création de RelId(elem1, elem2) latente

29. fsi

30. sinon

31. Retrait_Relation (R, elem1, elem2)

32. suppression de la contrainte associée

33. création de RelId(elem1, elem2) active

34. /* La relation RelId est traduite sous forme

de contrainte envoyée au résolveur */

35. création de la contrainte associée

36. fsi

37. fsi

}


Fig 10. Algorithme pour l'ajout d'une relation

6.2.2 Génération des relations induites

Les relations induites ont pour but de créer la fermeture transitive du graphe composé par les éléments reliés par des relations actives. Cette fermeture transitive est maintenue de façon incrémentale après chaque ajout ou retrait de relation.

La procédure Generation_Relations_Induites est appelée automatiquement lors de l'ajout d'une relation active entre deux éléments elem1 et elem2 d'un élément composite Elem. Elle a pour but de créer les relations induites nouvellement générées par l'ajout de cette relation active comme le montre la séquence de la Fig 11 .

Image pla_ajout_induite.gif

Fig 11. Génération de relations induites


Procédure Generation_Relations_Induites (RelId, elem1, elem2)

{

1. /* Création des relations induites entre elem1 et

les éléments en relation avec elem2 */

2. tant que il existe elemx in Elem tel que elemx =/= elem1 et

il y a une relation entre elem2 et elemx et

il n'y a pas de relation entre elem1 et elemx faire

3. création Rel(elem1, elemx) induite

4. fin tant que

5. /* Création des relations induites entre elem2 et

les éléments en relation avec elem1 */

6. tant que il existe elemx in Elem tel que elemx =/= elem2 et

il y a une relation entre elem1 et elemx et

il n'y a pas de relation entre elem2 et elemx faire

7. création Rel(elem2, elemx) induite

8. /* Création des relations induites entre les éléments

en relation avec elem1 et les éléments en

relation avec elem2 */

9. tant que il existe elemy in Elem tel que elemy =/= elemx et

il y a une relation entre elem2 et elemy et

il n'y a pas de relation entre elemx et elemy faire

10. création Rel(elemx, elemy) induite

11. fin tant que

12. fin tant que

}


Fig 12. Algorithme de génération des relations induites

6.2.3 Retrait d'une relation

Cette procédure est appelée lors du retrait par l'auteur d'une relation entre deux éléments elem1 et elem2 d'un élément composite Elem. Seules les relations explicites (actives ou latentes) peuvent être supprimées. Les relations induites n'ont pas d'existence propre et de ce fait ne peuvent pas être retirées par l'auteur (1-3).

La suppression d'une relation latente a pour conséquence de la faire retourner à l'état de relation induite (4-7).

La suppression d'une relation active a pour conséquences :


Procédure Retrait_Relation (RelId, elem1, elem2)

{

1. si (RelId inexistante) ou (RelId induite) alors

2. Retrait impossible, relation inexistante

3. fsi

4. si (RelId latente) alors

5. suppression de RelId

6. création de R(elem1, elem2) induite

7. fsi

8. si (RelId active) alors

9. suppression de RelId

10. suppression de la contrainte associée

11. Suppression_Relations_Induites (elem1, elem2)

12. fsi

}


Fig 13. Algorithme pour le retrait d'une relation

6.2.4 Suppression des relations induites

Cette procédure est appelée automatiquement lorsqu'une relation active est supprimée entre deux éléments elem1 et elem2 d'un élément composite Elem. Elle a pour effet de supprimer toutes les relations induites qui n'ont plus lieu d'exister après ce retrait.

Après le retrait de la relation entre elem1 et elem2, on obtient deux sous-ensembles distincts du point de vue des relations actives (Fig 14 b) (1-4).

Image pla_extraire_active.gif

Fig 14. Eléments reliés par des relations actives

S'il n'y a pas de relation latente entre les deux sous-ensembles constitués, alors toutes les relations induites entre un élément du premier sous-ensemble et un élément du second sont supprimées (Fig 15 b) (16-20).

Image pla_retrait_induite.gif

Fig 15. Suppression de relations induites sans relation latente

S'il existe une relation latente entre les deux sous-ensembles, alors cette dernière est transformée en relation active (traduite sous forme de contrainte) et une relation induite est créée entre les éléments elem1 et elem2 (Fig 16 b) (6-14). Ce traitement n'est effectué que pour la première relation latente trouvée entre les deux sous-ensembles. Cette dernière correspond actuellement à la plus "ancienne" relation latente dans l'ordre de leur définition, mais un autre choix pourrait être effectué pour tenir compte d'éventuelles priorités.

Image pla_retrait_latente.gif

Fig 16. Suppression de relations induites avec relation latente


Procédure Suppression_Relations_Induites (elem1, elem2)

{

1. L_elem1 = {elem1}

2. L_elem1 = Extraire_Relations_actives (L_elem1)

3. L_elem2 = {elem2}

4. L_elem2 = Extraire_Relations_actives (L_elem2)

5. /* Test si relation latente entre L_elem1 et L_elem2

sur le même axe de référence */

6. tant que il existe une relation latente R dans Elem faire

7. si R(elemx, elemy) et

elemx in L_elem1 et elemy in L_elem2 alors

8. Suppression de R latente

9. Création de R(elemx, elemy) active

10. création de la contrainte associée

11. Création de R(elem1, elem2) induite

12. Sortie Procédure

13. fin si

14. fin tant que

15. /* Suppression des induites entre L_elem1 et L_elem2 */

16. tant que il existe une relation induite R dans Elem faire

17. si R(elemx, eleny) et

elemx in L_elem1 et elemy in L_elem2 alors

18. Suppression de R induite

19. fin si

20. fin tant que

}


Fig 17. Algorithme de suppression de relations induites

La fonction Extraire_Relations_actives a pour but de construire la liste des éléments ayant une relation active directe ou indirecte avec un élément elem.


Liste <== Extraire_Relations_actives(L_elem)p>

{

<

1. elem = Last(L_elem)

2. /* la fonction Last donne le dernier élément de la liste */

3. tant que il existe une relation active R dans Elem faire

4. si R(elem, elemx) et elemx not in L_elem alors

5. L_elem <==L_elem + elemx

6. /* elemx est ajouté en fin de la liste L_elem */

7. Extraire_Relations_actives (L_elem)

8. fin si

9. fin tant que

10. Retourne (L_elem)

}


Fig 18. Algorithme d'extraction des relations actives à partir d'un élément

6.2.5 Discussion

Un graphe comportant n relations actives peut posséder au maximum (n(n+1))/2 relations totales (actives, latentes et induites). Le nombre N de relations totales pour un élément composite est donc de l'ordre de n2. La complexité de l'algorithme précédent est en N2 , ce qui équivaut à n4. Cependant, nous pouvons faire plusieurs remarques sur ce résultat.

D'abord, cet algorithme exploite la localité des relations. En effet, les relations spatiales n'étant définies que pour des éléments d'un même composite, les relations considérées dans cet algorithme sont celles rattachées à un seul élément composite et non la totalité des relations du document. De plus, les relations prises en compte pour chaque élément composite sont uniquement les relations exprimées par l'auteur et non les relations intrinsèques aux éléments. Ces deux éléments conjugués font que le nombre de relations actives considérées est en général relativement faible (de l'ordre d'une dizaine dans nos documents).

De plus, la gestion des relations cycliques intervient uniquement lors de l'ajout ou lors du retrait d'une relation. Le déplacement continu des éléments, qui nécessite des temps de réponse très rapides ne fait pas appel à cet algorithme.

Enfin, certaines optimisations sont possibles, notamment la création d'un double chaînage reliant uniquement les relations explicites d'un élément composite, permettant ainsi de réduire la complexité de l'algorithme en N, c'est-à-dire n2.

Une limitation de cet algorithme réside dans le fait qu'il a été développé pour des configurations où l'on ne redimensionne pas les éléments. Dans cette éventualité, il n'est pas applicable en l'état et pour ajouter cette fonctionnalité, il nécessite certaines modifications. Dans l'exemple de la Fig 19 a, on a défini une relation d'Alignement_Gauche entre A et B, une relation d'Alignement_Droit entre B et C et une relation de Décalage_Gauche(5) entre A et C cohérente avec la configuration donnée. Cette dernière relation étant redondante, elle est de type latente et n'est pas transmise au résolveur. Si l'on agrandit B, les deux premières relations restent vérifiés (les variables correspondantes sont mises à jour par le résolveur) mais la relation latente n'est plus cohérente avec la nouvelle configuration Fig 19 (b).

Image placement_redimensionnement.gif

Fig 19. Redimensionnement avec relation latente

Dans ce cas, plusieurs stratégies sont possibles : interdire le redimensionnement en présence de relations latentes, retirer la relation latente ou accepter le redimensionnement de C pour garder la relation latente cohérente. Dans ce dernier cas, le résolveur doit avoir connaissance de cette relation, ce qui nous ramène à un problème de résolution de cycles.

7 Conclusion

Dans ce chapitre, nous avons spécifié le placement spatial à mettre en oeuvre dans Madeus. Ce placement s'exprime par un problème de maintien de solution dans un système de contraintes et, pour le résoudre, nous avons choisi un résolveur de contraintes incrémental basé sur la technique de propagation locale. Face aux limitations de ce résolveur, nous avons restreint les relations spatiales initialement prévues et nous avons développé un algorithme spécifique pour traiter le problème des relations redondantes qui génèrent des cycles de contraintes.

Le placement spatial que nous avons défini peut se voir comme une base qui peut servir pour exprimer des fonctionnalités plus riches comme le redimensionnement ou les relations d'inclusion par exemple.

Ce placement ne traite pas des problèmes liés à la dimension temporelle des documents multimédia pour leur présentation spatiale. Pour ce problème également, il peut servir de base à une étude spécifique. Comme il est indépendant des aspects temporels, il peut aussi être utilisé ou appliqué dans un environnement statique.

Dans le chapitre suivant, nous présenterons la mise en oeuvre du placement spatial dans le prototype Madeus.