• Accès rapide
  • Page d'accueil
  • International (en)
  • Blog de François
  • Blog de Frédéric
  • Maths
  • Informatique
  • Programmation
  • Nos jeux
  • Jeux vidéo
• Pages spéciales
  • Connexion
  • Forum
  • Auteurs
  • Plan du site
• Répertoires parents
  • Informatique
  • Éditeur de schémas et graphiques en SVG
• Répertoire courant
  • Nos smileys
  • Conception et développement d'une interface C/C++ de solveurs numériques en Calcul Parallèle
  • Développement d'un solveur de programmes linéaires
  • Calculatrice Scientifique
  • Éditeur de schémas et graphiques en SVG
  • TIPE 2006-2007
  • Nos Programmes
  • Programmation

Table des matières

Résumé

Dans ce stage, j'ai travaillé sur l'éditeur de documents Web Amaya. L'objectif était de mettre place des capacités d'édition d'images vectorielles SVG en ne cherchant pas les fonctionnalités sophistiquées des logiciels de création artistique (gradient, flou...) mais en se concentrant plutôt sur la réalisation de schémas simples. Les fonctionnalités que j'ai mises en oeuvre incluent l'édition de formes de base (carré, rectangle, triangle...) de tracés (polygone, courbes de Bézier...) et de style simple (couleur, épaisseur des traits, transparence...), la gestion de calques (grouper, monter/descendre), des transformations (rotation, déplacement, étirement...), des outils de positionnement automatique (alignement et distribution), le tracé de connecteurs (lignes et flèches), l'insertion de composants prédéfinis (formes 3D, symboles électriques, portes logiques, verreries de chimie...), l'insertion d'éléments non SVG (image, texte et objets étrangers) ainsi que la gestion des méta-données (titre, description).

Accueil et encadrement

L'INRIA

L'INRIA, institut national de recherche en informatique et en automatique a pour vocation d'entreprendre des recherches fondamentales et appliquées dans les domaines des sciences et technologies de l'information et de la communication. Il accueille 3800 personnes réparties dans 8 centres de recherche et travaillant dans plus de 150 équipes-projets de recherche.

J'ai effectué mon stage à l'INRIA Grenoble - Rhône-Alpes dont les trois grandes priorités thématiques du centre sont les suivantes :

• Programmer et communiquer : systèmes embarqués sur puces, infrastructures de calcul et de communication etc
• Modéliser et simuler des phénomènes multi-échelles et multi-composants.
• Percevoir et intéragir avec des environnements réels ou virtuels.

Le projet WAM

J'ai travaillé au sein de l'équipe de recherche WAM qui s'intéresse à la création et la transformation de documents Web multimédia et à leur adaptation. Elle est dirigée par Vincent Quint, qui a occupé différentes fonctions au W3C et participe depuis plusieurs années aux travaux sur les technologies Web. La dizaine de chercheurs et ingénieurs de WAM travaille autour de différents sujets : recherche sur le traitement des documents XML, adaptation à différents terminaux et développement de deux logiciels : LimSee3 (présentation multimédia) et Amaya (éditeur de documents structurés pour le Web). C'est sur ce dernier que j'ai développé des fonctionnalités d'édition SVG.

L'équipe Amaya

Irène Vatton, ex-membre du W3C et actuellement à la tête du projet Amaya, a été ma directrice de stage. L'équipe se compose de 3 autres développeurs : Vincent Quint, Laurent Carcone (ingénieur expert à ERCIM, membre du W3C) et Émilien Kia (Ingénieur associé). Amaya est actuellement partiellement financé par le projet européen PALETTE [13] qui vise à développer et mettre en oeuvre des outils pour les communautés de pratique. En particulier, Amaya est susceptible d'être utilisé par la communauté ePrep [8], constituée d'enseignants des CPGE. Cette communauté est intéressée par l'édition de formules mathématiques et de schémas.

Remerciements

Mes remerciements vont tout d'abord à Irène Vatton pour m'avoir permis de réaliser ce stage et accompagné lors de son déroulement. Son aide dans la correction des bogues et ses indications sur la manière d'implémenter les nouvelles fonctionnalités m'ont été très précieux. Je suis aussi reconnaisant envers l'assistante de l'équipe WAM et le personnel admistratif du CROUS pour avoir facilité mon intégration à l'INRIA et mon logement sur Grenoble. Je tiens à remercier tous les membres du projet WAM pour leur accueil et plus particulièrement les développeurs d'Amaya : Irène, Vincent, Laurent et Émilien. Leurs commentaires, conseils et assistance m'ont été très utiles pour réaliser mon travail tandis que le logiciel qu'ils développent a été un outil indispensable à la rédaction de mon rapport. Finalement je souhaite exprimer ma gratitude envers toute la communauté du logiciel libre pour mettre à disposition les logiciels que j'ai utilisé au cours de mon stage ou ceux dont j'ai repris des idées et icônes.

1. Introduction

Depuis toujours, le Web se distingue des autres média en offrant à chaque utilisateur la possibilité d'être aussi un auteur. C'est ainsi que le premier navigateur intégrait des capacités d'édition de façon à ce que chacun puisse lire et publier des pages. Ces dernières années de nombreux systèmes de gestion de contenu sont apparus et ont connu un succès croissant : blog, wiki, forum... Bien qu'ils permettent de gérer facilement les données en ligne, ils deviennent rapidement limités lorsqu'il s'agit d'éditer les pages. En effet, pour réaliser des structures complexes comme des listes, tableaux, formules mathématiques ou croquis, l'auteur doit apprendre et utiliser une pseudo-syntaxe. Certes plus simple que le XML, elle n'en reste pas moins difficile pour les non programmeurs.

L'un des objectifs d'Amaya [2] est de répondre à ce besoin d'un outil d'édition. Il permet ainsi d'éditer des pages Web conformes aux recommandations du W3C parmi lesquels XHTML (structuration de la page en paragraphe, liste, tableau...), CSS (information de mise en page) et MathML (formules mathématiques) tout en encourageant la production de contenu accessible [4]. Le travail réalisé au cours de mon stage ajoute des possibilités d'édition SVG (graphique vectoriel) pour la réalisation de schémas. Il viendra, je l'espère, s'ajouter aux progrès réalisés dans le cadre du projet PALETTE pour que l'édition Web soient réalisables par des utilisateurs novices.

Dans la suite de l'introduction, je présenterai brièvement les caractéristiques d'Amaya et du langage SVG. Une seconde partie présentera l'environnement dans lequel j'ai travaillé, l'état de l'art et mon plan de travail. Je développerai ensuite le travail que j'ai réalisé dans la création, la manipulation, l'édition et la transformation des objets, ainsi que l'ajout de style. La conclusion fera le bilan du travail effectué et de ce stage m'a apporté à titre personnel.

1.1. L'éditeur Web Amaya

Amaya est un éditeur Web développé par l'INRIA et le W3C (organisme international de normalisation des formats Web). Il sert à la fois de démonstrateur des nouvelles technologies et d'outil pour réaliser facilement des pages respectant les recommandations du W3C.

Les fonctionnalités d'édition et de navigation sont intégrées de façon homogène dans un même environnement. L'utilisateur peut aussi bien créer une page entièrement nouvelle que en récupérer une sur le Web pour l'éditer. Il peut directement enregistrer ses pages sur un serveur s'il possède les droits d'écriture. Il peut charger simultanément plusieurs pages et facilement créer des liens entre elles, sur n'importe quel élément. Il peut attacher des commentaires au format XML à tout élément d'une page Web grace à son système d'annotation. Il peut directement envoyer par courriel les documents qu'il édite.

Il est possible d'ouvrir simultanément dans une même fenêtre plusieurs onglets. La fenêtre de l'application peut être divisée en plusieurs cadres pour pouvoir afficher en parallèle des documents. Un document peut être affiché et édité dans plusieurs vues synchronisées, parmi lesquelles la vue formatée (classique), la vue structure (arbre du document) et la vue source (code XML).

Sauf lorsque l'utilisateur effectue des modifications dans le code source et à l'inverse d'autres logiciels de création Web, l'édition d'Amaya se réalise à un niveau élevé : toutes les commandes agissent directement sur l'arbre XML du document. Ainsi, l'édition se caractérise à la fois par une interface Wysiwyg qui offre à chaque instant le rendu du document et une manipulation structurelle de l'arbre. Ce dernier est constamment maintenu valide vis-à-vis de doctypes connus.

On retrouve dans Amaya toutes les commandes classiques des éditeurs Wysiwyg (copier-coller, annuler/refaire, rechercher, zoom, panneau d'insertion éléments et de style, vérifieur orthographique, création de liens...) auxquelles s'ajoutent des fonctionnalités avancées commme la numérotation des sections ou la construction d'un livre à partir de plusieurs pages liées. Un système innovant de modèles sera bientôt fonctionnel.

Amaya propose aussi des manipulations structurelles pour les utilisateurs avancés : transformations de fragments d'arbres (par exemple conversion d'une suite de paragraphes en une liste d'items ou en un paragraphe unique), sélection directe des ancêtres du noeud courant affichés dans la barre inférieur, panneau d'édition des attributs XML ou des classes CSS de l'élément sélectionné...

Amaya permet enfin d'éditer facilement des documents avec des tableaux, listes, images, formulaires, formules mathématiques et dans la prochaine version, des schémas. Un exemple de tel document est donné sur la capture d'écran ci-dessus. L'édition du SVG mélangé avec plusieurs langages avait été expérimenté déjà dans le passé [7] et l'objectif de mon stage était de réaliser cette implémentation.

1.2. Le langage SVG

SVG (Scalable Vector Graphics) est un langage XML et une recommandation du W3C conçu pour réaliser des images vectorielles [14]. Le principe est de représenter l'image non pas par la couleur de chaque pixel mais par une description de chaque composant en utilisant des caractérisations géométriques, des changements de repères ou encore des informations de style. Les principaux avantages de SVG sont :

• L'image n'est pas décrite pour une taille fixe. Elle peut donc être zoomée ou imprimée en conservant une bonne qualité.
• Le fait de décrire l'image par chaque composant lui offre une véritable structure. Ainsi un éditeur peut facilement modifier une image existante puisqu'on préserve l'information structurelle contrairement aux images bitmap. On peut aussi attacher des méta-données qui sont importantes pour l'accessibilité des images [4].
• Le SVG peut être manipulé comme n'importe quel langage XML : il peut ainsi s'utiliser avec d'autres grammaires comme MathML ou XHTML (voir section 3.1.2), être stylé avec des feuilles CSS ou XSL, manipulé via une interface DOM ou animé par le langage SMIL.

A titre d'exemple, le fragment XML suivant décrit un rectangle à coin arrondi :

<svg xmlns="http://www.w3.org/2000/svg" width="350" height="250">
  <title>Un rectangle jaune à coins arrondis</title>
  <rect width="300" height="150px" style="stroke: black; fill: yellow"
        transform="rotate(-25,290,65) " rx="80px" ry="30px"/>
</svg>

L'élément <svg/> représente la zone de tracé qui est un rectangle de dimension 350×250. Un fils <title/> lui associe un titre. Un second fils <rect/> décrit le tracé d'un rectangle de dimension 300×150. L'attribut style indique que les bords du rectangle sont noirs et qu'il est rempli en jaune. L'attribut transform indique que le rectangle subit une rotation de centre (290,65) de -25°. Enfin les attributs rx et ry précisent les rayons des coins arrondis :

Un rectangle jaune à coins arrondis

2. Contexte

2.1. Environnement technique

2.1.1. Logiciels utilisés

Je développais sous Linux et avais à ma disposition un PC avec Windows XP et un portable Mac. J'ai aussi utilisé le dépôt CVS du W3C où est stocké la version de développement d'Amaya, en m'aidant des programmes cvs et tkcvs. Je codais avec emacs et utilisais les outils de développement GNU (gdb, gcc...). Le panneau SVG a été effectué à l'aide de l'éditeur de ressources XRCed. Les icônes ont été réalisées avec GIMP en reprenant éventuellement celles existant dans Open Office ou Inkscape. Ce dernier m'a été utile pour les conversions entre les formats SVG/PNG. Les "composants prédéfinis" (3.1.6) ont été créés à l'aide d'Amaya. Enfin, de nombreuses formules mathématiques ont été vérifiées à l'aide de Maxima [11].

2.1.2. Amaya

Amaya est basé sur la librairie C "Thot", qui offre tout un ensemble de commandes permettant de gérer des documents structurés. Actuellement une partie de l'interface utilisateur est écrite à l'aide de la librairie C++ wxWidgets. Les graphiques SVG sont rendus grace à la librairie OpenGL. J'ai appris à travailler avec ces différentes librairies. Amaya est un logiciel fonctionnant sous Linux, MacOSX et Windows et est traduit dans une quinzaine de langues. J'ai donc du tester mon éditeur SVG sur les différentes plate-formes et réaliser les nouveaux messages à la fois en anglais et en français.

2.2. État de l'art

2.2.1. Open Office

Open Office [12] comporte un module de dessin qui utilise en interne une syntaxe XML reprenant des attributs SVG. Il possède les caractéristiques suivantes :

• Insertion de divers objets pouvant être retaillés ou déformés.
• Tracé et édition des chemins (lignes, coubes de Bézier...).
• Transformations d'objets : rotation, translation...
• Gestion des calques : monter/descendre. Il est possible d'entrer/sortir dans un groupement d'objets pour pouvoir les éditer.
• Répartition d'objets : distribuer, aligner.
• Texte, méta-données (titre, description)
• Style (couleur, tracé...)
• Opérations sur les chemins (union, intersection).
• Des connecteurs peuvent se relier aux points caractéristiques des objets ou à des "points de collages" définis par l'utilisateur. Ces liaisons sont conservées si l'utilisateur déplace les objets.

Étant utilisé par des utilisateurs très variés, il est intéressant d'étudier ce logiciel pour avoir une interface non réservée à des spécialistes. Par contre les documents qu'il produit sont davantage destinés à l'impression qu'à la publication Web (l'édition se réalise entièrement sur une page blanche). De plus il utilise son propre format pour proposer des méthodes d'édition. Celles-ci ne sont donc pas forcément applicables au SVG.

2.2.2. Inkscape

Inkscape [10] est un éditeur d'image vectorielle SVG. Il possède les fonctionnalités d'Open Office citées précédemment, sauf pour l'insertion de constructions prédéfinies. Les formes de bases sont celles de la spécification SVG avec quelques structures supplémentaires (étoile, spirale...). Le logiciel montre des menus plus proches du SVG (par exemple le style ou les marqueurs) bien qu'il utilise aussi une extension XML pour des informations d'édition en plus. Il est par contre plus orienté "dessin d'art" et n'est pas vraiment adapté à l'édition de schémas.

2.2.3. Dia

Dia [6] est un logiciel spécialement conçu pour l'édition de diagrammes. Il permet l'insertion d'un grand nombre de composants prédéfinis (porte logique, circuit électrique...) et dispose d'une très bonne interface pour les "points de connexion". Il n'y a pas de tracé de segments/courbes mais seulement une insertion de formes que l'utilisateur peut ensuite éditer (augmenter/supprimer/déplacer les points). Il est possible d'insérer du texte et des images. Comme Open Office, il utilise son propre format. Il peut exporter en SVG mais le dessin ne peut alors plus être édité par le logiciel.

2.3. Plan de travail

Cette section donne un aperçu des fonctionnalités du langage SVG [14], en rapport avec la création de schémas/graphiques, qu'il serait intéressant d'intégrer à Amaya. Elles sont données dans l'ordre de priorité qui a été fixé pendant les réunions avec l'équipe.

2.3.1. Modèle de rendu et structure du document

Une image SVG possède une racine <svg/> qui décrit la zone de tracé. Ses fils sont les composants graphiques, chacun étant dessiné sur ses prédécesseurs. Les fils peuvent être des éléments de base (rectangle, polygone...) ou un élément "groupe" (<g/>) dont les fils sont eux-même d'autres composants graphiques. Chaque élément peut comporter des éléments <title/> et <desc/> qui permettent de rendre accessible les contenus graphiques en lui associant respectivement un titre et une description.

A titre d'exemple, considérons le cylindre ci-dessous, dessiné avec deux ellipses (représentant les bases) et d'un chemin (partie avant de la surface latérale) :

Un exemple d'imageSVGcomposéededeuxellipsesetd'unchemin. cylindre

L'utilisateur doit à la fois être capable de sélectionner chaque composant individuellement (par exemple pour les mettre en couleur) ou de sélectionner en groupe (par exemple pour appliquer des transformations sur le cylindre). Il doit aussi pouvoir être capable de choisir l'ordre des éléments (par exemple la base du dessous, vue par transparence est derrière la partie avant). Enfin l'utilisateur doit pouvoir éditer les descriptions associées aux éléments.

2.3.2. Chemins et figures élémentaires

Le langage SVG dispose de deux types d'éléments pour décrire les tracés : les figures élémentaires et les chemins. Pour les premiers, les éléments disponibles sont:

• L'élément <rect/> qui décrit un rectangle par la coordonnée de son coin inférieur gauche et ses dimensions.
• Les éléments <circle/> et <ellipse/> qui décrivent des cercles et ellipses par la coordonnée de leurs centres et de leurs rayons/demi-axes.
• L'élément <line/> qui décrit un segment par les coordonnées de ses extrémités.
• Les éléments <polyline/> et <polygon/> qui décrivent une suite de segments par une liste de points. Le second élément permet de représenter des figures fermées.

Les chemins sont décrits par un éléments <path/>. Si on imagine le tracé d'un chemin avec un crayon, un sous-chemin correspond à un tracé effectué sans lever le crayon. Les principales opérations sont :

• M : ouverture d'un sous-chemin.
• L : un tracé de ligne
• C et Q : un tracé de courbe de Bézier cubique ou quadratique.
• A : un arc d'ellipse
• z : fermeture du sous-chemin courant par une ligne droite.

On rappelle qu'une courbe de Bézier de degré $n$ décrites par les points de controle $A_0...A_n$ est paramètrée par $t\in [0,1]$ de la façon suivante [5] :

• $G\left(t\right)$ est barycentre des points $A_0...A_n$
• $A_i$ se voit affecter un poids égal à la valeur du $i$-ème polynômes de Bernstein de degré $n$ en $t$ : $B_i^n\left(t\right)=\left(\genfrac{}{}{0ex}{}{n}{i}\right)t^i{\left(1-t\right)}^{n-i}$ .

En pratique, on s'intéresse surtout au cas $n=3$, une courbe de Bézier quadratique pouvant être décrite de façon cubique [5]. Le point $A_0$ est le point de départ et le point $A_3$ le point d'arrivée de la courbe. Les points $A_1$ et $A_2$ donnent les tangentes de la courbe au point de départ et d'arrivée. La courbe est dans le polygone formé par les 4 points de contrôle.

Allure d'une courbe de Bézier de degré 3 A0 A3 A1 A2

Dans les éditeurs d'images, ces points servent de "poignées" pour que l'utilisateur puisse changer la forme de la courbe. Lorsque plusieurs fragments de courbe de Bézier sont enchainées dans les chemins, il est d'usage de rajouter des contraintes sur les deux demi-tangentes associées à un point. Par exemple, en imposant l'alignement des poignées, on obtient une courbe sans point anguleux :

En résumé, les possibilités attendues pour l'éditeur SVG sont :

• création et édition des figures élémentaires du SVG : ligne, rectangle, cercle et ellipse, polygone ouvert et fermé. Ces dernières constructions étant plutôt limitées pour l'utilisateur, il faudra aussi ajouter la création/édition de carré, losange, triangle etc
• création et édition de courbes ouverte et fermée, composés de courbes de Bézier. En effet, cela constitue un tracé classique des éditeurs d'images alors que le tracé d'un "arc d'ellipse" dans un chemin ne se fait pas vraiment de façon naturelle.

2.3.3. Objets particuliers

Outre le tracé de formes géométriques, le langage SVG permet d'inclure divers objets particuliers :

• Des images (<image>) ou de nouveaux canevas (<svg/>).
• Du texte.
• Des "objets étrangers" (<foreignObject>). Cet élément autorise potentiellement l'inclusion de nouveaux langages XML à l'intérieur même du SVG. Cette fonctionnalité est particulièrement utile pour l'inclusion de formules mathématiques MathML.

Les fonctionnalités intéressantes pour ces objets sont :

• Possibilité de les insérer et de les éditer.
• Choix de la position/dimension.

2.3.4. Transformations affines

Le SVG offre la possibilité d'effectuer des transformations sur les objets par le biais de changements de repère. Ceux-ci sont décrits par un attribut transform pouvant être attaché à la plupart des éléments et notamment des groupes. Si $x,y$ sont les coordonnées dans le système de coordonnées courant et $x\text{'},y\text{'}$ ceux dans le nouveau système de coordonnées, alors la spécification donne pour relation :

$\left(\begin{array}{c}x\\ y\\ 1\end{array}\right)=\left(\begin{array}{ccc}a& c& e\\ b& d& f\\ 0& 0& 1\end{array}\right)\left(\begin{array}{c}x\text{'}\\ y\text{'}\\ 1\end{array}\right)$

Généralement, on écrit plutôt une telle transformation affine de la façon suivante, pour qu'apparaisse clairement la composante linéaire et le changement d'origine :

$\left(\begin{array}{c}x\\ y\end{array}\right)=\underset{\text{composante linéaire}}{\underbrace{\left(\begin{array}{cc}a& c\\ b& d\end{array}\right)}}\left(\begin{array}{c}x\text{'}\\ y\text{'}\end{array}\right)+\underset{\text{changement d'origine}}{\underbrace{\left(\begin{array}{c}e\\ f\end{array}\right)}}$

La valeur de l'attribut transform correspondant est matrix(a, b, c, d, e, f). Une telle notation permet de décrire et manipuler uniformément les transformations affines, ce qui est utile pour les opérations internes du programme. Bien que certains éditeurs comme Inkscape propose un menu d'édition des coefficients, il est souvent plus commode pour l'utilisateur de se référer à des transformations simples. La spécification SVG fournit ainsi d'autres valeurs pour l'attribut transform, récapitulée ci-dessous.

Notons que ces valeurs de l'attribut peuvent être concaténées pour composer les transformations (avec l'ordre de lecture usuel). L'attribut rotate permet aussi de spécifier un centre de rotation (cx, cy) : ainsi "rotate(θ, cx, cy)" est équivalent à "translate(cx, cy) rotate(θ) translate(-cx, -cy)".

Les cinq transformations du tableau sont beaucoup plus claires pour l'utilisateur et se réalisent assez naturellement avec la souris. Par exemple pour un déplacement on clique sur la figure et on la fait glisser à la nouvelle position, pour un étirement on clique sur un bord et on tire dessus etc. Pour les transformations, les fonctionnalités possibles sont :

• Offrir à l'utilisateur une interface permettant de réaliser simplement (i.e. sans avoir à rentrer de valeurs) les cinq transformations de base du SVG.
• Si possible, offrir à l'utilisateur la possibilité de créer/éditer toutes les transformations affines données par la forme générale ci-dessus.
• Ajouter des transformations élémentaires supplémentaires en s'inspirant de ce que l'on trouve ailleurs : alignement, symétrie, pivotement de 90°.

2.3.5. Style

Les styles SVG concernent le tracé (couleur, épaisseur, opacité, pointillé, type de jointures/extrémités) et le remplissage (couleur, opacité et règle de remplissage) des éléments. Deux méthodes sont possibles pour styler les graphiques :

1. Par des attributs attachés aux éléments SVG.
2. Par des propriétés CSS. Les éléments SVG possèdent pour cela un attribut style.

Idéalement, il faudrait être capable de gérer les deux représentations et de pouvoir passer de l'une à l'autre.

2.3.6. Marqueurs

Les marqueurs répondent au besoin d'avoir des symboles spéciaux pour les tracés, par exemple pour représenter des flèches :

Une courbe avec deux flèches aux extrémités.

L'utilisation typique se fait en définissant des marqueurs dans un élément <defs>, dessinés comme tout autre élément SVG, que l'on peut ensuite réutiliser comme jointures/extrémités des courbes :

<svg [...]>
  <defs>
    <marker id="ID_MARQUEUR1" [...]>
      [Tracé du marqueur]
    </marker>
    [...]
  </defs>
  <path d="[Tracé du chemin]"
     marker-start="url(#ID_MARQUEUR1)"
     marker-mid="url(#ID_MARQUEUR2)"
     marker-end="url(#ID_MARQUEUR3)" />
</svg>

Pour l'éditeur, il faudrait présenter un ensemble de symboles prédéfinis à l'utilisateur ainsi que lui permettre de créer et utiliser ses propres marqueurs. L'utilisation des marqueurs combinées à des courbes/segments de droite permet d'envisager le tracé "des connecteurs" comme on les trouve dans Dia. Toutefois le SVG ne permet pas d'exprimer des contraintes de connexion.

3. Mise en oeuvre dans Amaya

3.1. Création d'objets

3.1.1. Le canevas SVG

La zone de dessin est donnée par un élément <svg/> qui peut être l'élément racine du document SVG : on retrouve le cas des éditeurs "classiques" à savoir un document dont tout l'espace est réservé au tracé. Néanmoins, Amaya permet aussi de mélanger plusieurs grammaires XML. Il est possible que le canevas SVG soit par exemple intégré dans une page XHTML ou soit lui même intégré dans un autre dessin SVG. Les boites peuvent aussi être positionnées à l'aide de style CSS. Il existe ainsi différents repères imbriqués et il faut être capable de passer du repère de la souris au repère local en composant les différentes transformations. Dans la suite on escamotte ces difficultés en raisonnant dans le repère local mais il faut garder à l'esprit que des fonctions réalisent ces changements de repères.

Pour simplifier, toutes les opérations effectuées en vue formatée (sélection, édition...) ne seront possibles que sur les fils directs du <svg/>. On peut toutefois adapter le code si on souhaite un mécanisme d'entrer/sortir du groupe tel qu'indiqué dans la section 3.2.1. Il faut alors modifier les matrices de transformation passées aux différents modules.

La capure ci-dessus montre un exemple typique d'édition dans Amaya. En haut, dans la vue formatée, on voit une image SVG (le logo d'Amaya) parmi du texte XHTML et positionné à l'aide de style CSS. En bas, dans la vue structure, on voit les éléments SVG correspondants : ellipse, groupe, polygone... Les deux vues sont synchronisées et montrent la sélection d'un groupe (en rouge dans la vue formattée, en bleu dans la vue structure). La sélection a été faite dans la vue formatée : comme indiqué plus haut, l'objet sélectionné est un fils direct du SVG. On peut directement éditer l'élément sélectionné dans la page.

3.1.2. Création des objets spéciaux

Le premier bouton de la palette SVG regroupe des commandes spéciales. Deux d'entre elles servent à la gestion des méta-données et seront expliquées dans la section 3.3.1. Les autres commandes sont :

• Création d'un canevas SVG
• Création de texte
• Création d'un objet étranger
• Insertion d'une image

La création d'un canevas SVG insère un nouvel élément <svg/> dans le document. Si la sélection est déjà dans un canevas, l'utilisateur dessine un cadre pour délimiter la nouvelle zone de dessin à l'intérieur de l'ancienne. Cette fonctionnalité permet d'emboiter des éléments <svg/> comme l'autorise la spécification (chapitre 5 de [14]) mais n'est pas vraiment utile pour le problème qui nous concerne. Un comportement plus intéressant est le cas où la sélection est à l'intérieur d'un autre langage XML. Actuellement, seul le Working Draft "An XHTML + MathML + SVG Profile" [3] précise les règles pour mélanger XHTML, MathML et SVG. Une DTD lui est associée et est intégrée dans le validateur du W3C [15]. La note "Guidelines for Graphics in MathML 2" [9] présente aussi une réflexion sur le mélange de SVG avec MathML. Actuellement la seule possibilité est l'insertion dans du XHTML. Dans ce cas, le nouveau canevas est inséré avec une taille par défaut et l'utilisateur peut ensuite le redimensionner à l'aide de la souris. Les éléments appartenant à l'espace de nom SVG sont alors préfixés par svg: de façon à produire des documents valides par rapport au doctype XHTML+MathML+SVG.

Inversement, on peut insérer du XHTML/MathML dans du SVG via les objets <switch/> et <foreignObject/>. Le premier sert à décrire un affichage conditionnel : le navigateur parcourt les fils jusqu'à tomber sur un élément qu' il est capable d'afficher. Le second autorise l'insertion d'"élément étranger" et possède des attributs précisant les capacités requises par le navigateur. Ses dimensions sont obligatoires. Ainsi dans l'exemple ci-dessous, un navigateur capable d'afficher des formules mathématiques affichera le contenu MathML tandis que les autres afficheront l'élément <text/>.

<svg [...]>
  <switch>
    <foreignObject width="100" height="50"
     requiredExtensions="[...]" [...]>
      <math [...]>
        <!-- Contenu MathML -->
        [...]
      </math>
    </foreignObject>

    <text>
      <!-- Text alternatif -->
      [...]
    </text>
  </switch>
</svg>

Lorsque l'utilisateur effectue la commande "Création d'un objet étranger" il doit cliquer à la position d'insertion souhaitée puis un groupe contenant la structure précédente est créé. Un <div/> est inséré dans le <foreignObject/> et l'utilisateur peut éditer du XHTML. Ce <foreignObject/> possède une dimension par défaut qui n'est pour l'instant modifiable qu'en allant éditer les attributs correspondants. Si l'utilisateur tente d'insérer du MathML alors que la sélection est dans du SVG, la même opération se produit sauf que c'est un élément <math/> que l'on insère. Le texte alternatif par défaut est "embedded XHTML not supported" ou "embedded MathML not supported" respectivement. Il y a actuellement un petit problème de compatibilité puisque les valeurs du requiredExtensions à utiliser ne sont pas explicitement indiquées dans les spécifications. Voir l'annexe 5.2.2.

Les commandes de création de texte et d'image génèrent respectivement les éléments SVG <text/> et <image/>. Pour le premier, l'utilisateur effectue un clic à la position où il souhaite insérer un élément textuel. Un mécanisme d'édition du texte existait déjà et prend en compte la gestion de plusieurs lignes. L'appuie sur la touche Entrer créé ainsi un élément SVG qui indique une nouvelle ligne. Pour le second, une boite de dialogue similaire à celle d'insertion des images XHTML (élément <img/>) s'ouvre pour que l'utilisateur puisse aller chercher le fichier correspondant. Cette boite comporte un champs "texte alternatif" qui génère un élément <desc/> dans l'image.

3.1.3. Création de connecteurs et de figures élémentaires

La création de ces objets se réalise en indiquant deux points. L'utilisateur clique une fois pour désigner un point A et maintient le bouton de la souris appuyé, déplace le curseur de la souris en un deuxième point B puis relache le bouton. Un "fantôme" de la figure est affiché à l'écran pendant que l'utilisateur maintient le bouton appuyé. Pour les segments ou flèche, le tracé va du point A au point B et peut avoir une précision limitée si on maintient le bouton shift appuyé (voir section 3.1.5). Dans les autres cas, le tracé de la figure se fait en déterminant le rectangle encadrant : les points A et B donnent les coins supérieur gauche et inférieur droit. Les constructions que j'ai réalisées sont :

• Figures élémentaires : carré, carré à coins arrondis, rectangle, rectangle à coins arrondis, losange, parallélogramme, trapèze, triangle équilatéral, triangle isocèle, triangle rectangle, cercle, ellipse.
• Connecteurs : ligne, flèche, flèche double, zigzag.

3.1.4. Création des segments de droites et courbes de Bézier

Dans cette section, on s'intéresse à la réalisation de formes plus générales. Pour cela, il est nécessaire d'avoir un sous-programme qui regarde les commandes effectuées à la souris et en déduit les tracés. Plutôt que de proposer toutes les fonctionnalités d'édition de chemins en même temps (courbes de bézier et poignées, arc, lignes...) on se restreint à quatre constructions :

• Segments de droites (<polyline/>) : une succession de points reliés entre eux.
• Polygone (<polygon/>) : idem mais la courbe est fermée.
• Courbe de Bézier ouverte : une succession de segments de Bézier formant une courbe sans point anguleux.
• Courbe de Bézier fermée.

On se fixe pour contrainte une interface de tracé simple et rapide. Il est en effet fort probable que ces tracés ne soient pas définitifs : l'idée est donc que l'utilisateur dessine une première approximation des contours de sa figure quitte à les raffiner ultérieument en éditant les points. Les commandes de bases sont :

• Simple clic : ajout d'un point à la position indiquée par le curseur de la souris.
• Double clic : ajout du dernier point.
• Clic droit (Ctrl+clic sous MacOS) : arrêt du tracé à l'état courant. Cette méthode est utile pour éviter d'insérer un point en trop.
• Touche shift : approximation des tracés de segments à 15°.
• Autre touche : annuler la contruction.

Pour les segments de droite et polygones, l'interface n'a pas besoin d'explication supplémentaire. Par contre pour les courbes de Bézier, les points de contrôle se scindent en deux catégories : les points sur la courbe et les "poignées". A nouveau j'ai choisi une interface simple, inspirée de celle d'Inskape, où l'utilisateur rentre le moins de points possible. Sur les schémas ci-dessous, le curseur de la souris courant est dessiné en rouge et la partie en cours d'édition en bleu. La succession des différentes étapes après chaque clic de souris est la suivante :

1. Rien n'est tracé. On attend que l'utilisateur indique le premier point de la courbe.

2. Une droite est tracée entre le premier point et le curseur de la souris.

   Étape 2 1

3. Deux points de la courbes sont fixés. Une courbe de Bézier quadratique est tracée entre le premier point et le second. Sa poignée est le symétrique du curseur de la souris par rapport au second point.

   Étape 3 1 sym 2

4. Deux points de la courbes et deux "poignées" sont fixés. Une courbe de Bézier quadratique est définivement tracée. Une courbe de Bézier cubique est tracée entre le second point et le curseur de la souris. Sa première poignée est donnée par le dernier clic. Sa seconde poignée est confondue avec le point d'arrivée (curseur de la souris).

   Étape 4 1 2

5. Trois points de la courbe et deux poignées sont fixés. Une courbe de Bézier quadratique est définitivement tracée. Une courbe de Bézier cubique est tracée entre le second et troisième point. Ses poignées sont la dernière poignée tracée et le symétique du curseur de la souris par rapport au troisième point.

   Étape5 1 2 3 sym

Après l'étape 5 on reboucle à l'étape 4, ce qui permet de tracer un nouveau fragment de Bézier cubique en deux clics. On continue jusqu'à ce que l'utilisateur indique la fin de l'interaction. L'utilisation des symétriques du curseur de la souris pour indiquer les tangentes permet à la fois à l'utilisateur de rentrer moins de points et d'obtenir une courbe sans point anguleux.

Dans le cas des courbes de Bézier fermées, on fait en sorte que la deuxième poignée du dernier fragment soit le symétrique de la toute première poignée de façon à éviter un point anguleux.

3.1.5. Approximation des lignes

Lors du tracé de segment de droites, l'utilisateur peut souhaiter réaliser des angles précis. Par exemple sous OpenOffice, les droites sont tracées avec une précision de 45° si l'utilisateur maintient la touche "Shift" appuyée. J'ai repris le même mécanisme, avec une précision d'angle $T=15°$. Le problème est décrit par la figure suivante : l'utilisateur a positionnée une extrémitée en $(x_1,y_1)$ et place l'autre extrémitée en $(x_2,y_2)$. On cherche à approximer l'angle $\theta$ suivant :

3.1.5.1. Algorithme

ApproximationLigne (T, x1, y1, *x2, *y2)

  << Complexité en O(1) >>

  x := *x2 - x1
  y := *y2 - y1
  r := racine(x^2 + y^2)

  Si r > 0
    θ := signe(y)*arccos(x/r)
    θ := Arrondir(θ/T)*T
    *x2 := x1 + r*cos(θ)
    *y2 := y1 + r*sin(θ)
  FinSi

FinApproximationLigne

Initialement, j'avais approximé les distances verticales/horizontales entre les deux points à l'instar d'Open Office. L'approximation de l'angle donne un meilleur résultat (elle conserve la longueur du segment), s'applique facilement à une valeur d'approximation quelconque (pas uniquement 45°) et s'écrit avec un code plus léger (évite d'utiliser plusieurs conditions if ... else ...).

3.1.6. Insertion de composants prédéfinis

Amaya possèdait autrefois une librairie graphique qui permettait de sauvegarder des images SVG de façon à pouvoir les réutiliser dans ses documents [1]. Après le passage à wxWidgets, il ne restait toutefois plus que la possibilité de copier/coller des images prédéfinies. J'ai choisi de remplacer cette librairie par un mécanisme plus rapide d'insertion. La palette SVG comporte donc un ensemble de boutons qui déclenche le chargement et l'insertion de composants prédéfinis dans le document. J'ai réalisé plusieurs composants en m'inspirant de ceux présents dans Open Office et Dia ou qui peuvent être utiles pour e-Prep. De nouveaux composants pourront être ajoutés, la liste actuelle comporte :

• Étoiles et polygones réguliers.
• Formes 3D (cône, cube, cylindre...)
• Flèches épaisses.
• "Bulles" (type bande dessinée).
• Formes diverses (soleil, parchemin...)
• Verrerie de chimie (fiole, bécher...)
• Composants de circuits électriques (diode, résistance, condensateur...)
• Composants de circuits logiques : (ET, OU...)

Ces composants sont dessinés en SVG et sont rangés dans le répertoire resources/svg/ d'Amaya. Les images sont insérées comme des groupes dans le document et peuvent donc subir plusieurs transformations (cf section 3.4) : redimensionnement, rotation déplacement etc. Ainsi, à l'inverse d'Open Office, on utilise pas d'images redondantes (par exemple les flèches dans plusieurs directions) lorsqu'elles peuvent s'obtenir rapidement par symétrie et/ou rotation de 90°. Enfin, les images possèdent un élément <title/> qui leur associe un titre et facilite donc la génération des descriptions (cf section 3.3.1).

3.2. Gestion des calques et sélection

3.2.1. Édition structurée et calque

Amaya est un éditeur structuré et il est possible d'afficher et éditer l'arborescence du fichier SVG en affichant la "vue structure". Lorsque l'on effectue un parcours du premier fils au dernier fils sur un niveau on se déplace dans l'image SVG de l'arrière-plan vers le premier plan. Lorsque l'on effectue un parcours en profondeur de l'arbre, on rentre dans des groupements d'objet. La vue structure permet donc de sélectionner les objets en contournant les contraintes liées aux niveaux (un objet peut être caché par un autre) et au groupe (quand on clique sur un objet d'un groupe, veut-on sélectionner l'objet ou le groupe en entier ?).

On aimerait maintenant pouvoir réaliser des parcours dans la vue formatée. Le choix qui a été fait est le suivant :

• Parcourir l'arbre en largeur

  Généralement, la création d'un élément dans Amaya se fait au point d'insertion courant. Cependant dans une image SVG, on s'attend à ce que le tracé de nouvelles figures se fasse au dessus du dessin courant. Par conséquent, les éléments créés dans la vue formatée sont d'abord placés comme dernier fils du canevas SVG et l'utilisateur doit ensuite utiliser les commandes monter/descendre pour le positionner correctement. On peut toutefois, sans quitter la vue formatée, positionner directement un élément en utilisant les commandes "insérer" et "ajouter" qui créer respectivement avant et après le point d'insertion un élément GraphicsElement. Ensuite, si on dessine un nouvel élément SVG et que le point d'insertion est sur un tel GraphicsElement, alors celui-ci est remplacé par le nouvel élément.

• Parcourir l'arbre en profondeur

  Par défaut, lorsque l'on clique sur un élément, la sélection remonte à l'ancêtre fils direct du canevas SVG qui sont donc les seuls éditables. Si on désire descendre plus en profondeur, il faut utiliser les commandes grouper/dégrouper des objets. L'implémentation actuelle du parcours en profondeur pose toutefois quelques problèmes. Ainsi seul les attributs transform sont conservés lors du dégroupage et ils ne sont pas factorisés lors du regroupage. L'utilisation d'une commande entrer/sortir du groupement serait donc préférable, mais elle n'a pas été mise en place.

3.2.2. Édition des calques

L'utilisateur peut appliquer des opérations sur un ou plusieurs calques simultanément, fils directs du <svg/>. Pour sélectionner les calques à traiter, il existe deux méthodes :

• Une sélection en cliquant sur l'objet à sélectionner. Si le bouton "Shift" est maintenu appuyé, l'élément est ajouté à la liste des éléments sélectionnés.
• Une sélection en traçant un rectangle à l'aide de la souris. Les objets dont la boite englobante est à l'intérieur sont sélectionnés.

La manière dont est affichée la sélection varie selon l'élément. Pour des <polyline/>, <polygon/> et <path/>, on affiche généralement les points de controle de la courbe, qui peuvent être déplacés. Lorsqu'il s'agit de figures élémentaires, des poignées spécifiques sont affichées pour permettre l'édition (changement de la taille, de la forme...). Enfin pour les groupes, le cadre rouge de la boite englobante est affiché. De cette façon, on peut par exemple distinguer une ellipse dans le canevas (elle a des poignées d'édition) ou dans un groupe (sa boite englobante est affichée).

Les calques peuvent être groupés/dégroupés. Du point de vue de l'arbre, cela consiste à créer un élément groupe <g/> et à y rentrer tous les éléments sélectionnés ou inversement prendre tous les <g/> sélectionnés, sortir les fils et à supprimer les <g/> vides. Pour ces opérations, il faut prendre garde à ne pas changer les niveaux des calques. Pour le dégroupage, il faut donc dégrouper les <g/> dans l'ordre dans lequel ils sont situés et, pour chacun, conserver l'ordre des fils. Pour le groupage, ce n'est pas toujours possible. En effet, même si on conserve aussi l'ordre des calques sélectionnés, il se peut qu'il existe un fils du <svg/> non sélectionné entre deux autres sélectionnés. On choisi de placer le nouveau <g/> comme successeur du fils sélectionné de niveau le plus haut. Cela est illustré dans groupement du carré bleu et du parallélogramme rose de la figure ci-dessous (les nombres indiquent les niveaux des calques) :

On considère maintenant les opérations pour monter/descendre un calque. Deux types d'opérations sont disponibles :

• Monter tout en haut / Descendre tout en bas : l'élément est placé comme dernier/premier fils du SVG.
• Monter/Descendre d'un niveau : l'élément est placé après/avant sont successeur/prédescesseur, si il en existe un.

Notons que pour le deuxième cas on interprète le déplacement comme une permutation de fils, ce qui ne correspond pas toujours à une "vraie" montée/descente si les éléments ne se chevauchent pas. On pourrait toutefois utiliser les boites englobantes pour déterminer si un objet est "réellement" devant un autre (cf section 3.3.1). Ci-dessous, on souhaite mettre le rectangle vert au dessus du triangle rose, on doit procéder en deux étapes :

Montée d'un élément Audépart,l'ordredesélémentsestrectangle,ellipseettriangle.Letriangleetlerectanglesechevauchentetl'ellipseestàpart,àdroite.Aladeuxièmeétape,l'ordreestellipse,rectangle,trianglemaisonnevoitpasdedifférence.Alatroisièmeétapel'ordreestellipse,triangleetrectangleetlerectangleestenfinpassédevantletriangle. 0 1 2 0 1 2 0 1 2

On va s'intéresser à la montée de calques, la descente s'obtenant par symétrie. Pour réaliser ces opérations, les fonctions disponibles dans Thot permettent de couper un élément et de le placer comme premier fils/successeur/prédécesseur d'un autre. On considère nombre objets sélectionnés objet[0], ... objet[nombre - 1] qui sont fils de canevas_svg.

Pour la fonction montant tous les objets, comme on n'a pas de fonction d'insertion à la fin et pour accélérer les traitements on utilise un pointeur sur le dernier objet (il y en a au moins un, ou sinon l'algorithme ne serait pas appelé) qui sert de référence. On coupe et colle alors chaque objet sélectionné à la fin du canevas_svg en utilisant cette référence.

3.2.2.1. Algorithme

MettreAuDessus(canevas_svg, nombre, objet[])
  curseur := DernierFils(canevas_svg)
  Pour i de 0 à nombre - 1
    Si objet[i] ≠ curseur
      MettreAprès(objet[i], curseur)
      curseur := objet[i]
    FinSi
  FinPour
FinMettreAuDessus

En ce qui concerne la fonction montant chaque objet sélectionné d'un niveau, l'algorithme naïf consistant à parcourir les fils sélectionnés et à les faire passer devant son successeur ne fonctionne pas dans le cas où plusieurs objets sont sélectionnés, puisque ce successeur peut lui-même être un objet qui a été ou va être monté. Pour pallier ce problème, on parcourt les éléments à l'envers (de façon à ce que lorsque l'on bouge un objet, tous ses successeurs aient déjà été déplacés) et on vérifie que le successeur n'est pas le dernier objet déplacé (pour conserver l'ordre des objets sélectionnés).

3.2.2.2. Algorithme

MonterUnNiveau(canevas_svg, nombre, objet[])
  curseur := Indéfini
  Pour i de nombre - 1 à 0
    suivant := Successeur(objet[i])

    Si suivant ≠ curseur
      MettreAprès(objet[i], suivant)
    FinSi

    curseur := objet[i]

  FinPour
FinMonterUnNiveau

3.3. Édition des objets

3.3.1. Édition des méta-données

Les éléments SVG peuvent comporter deux éléments <title/> et <desc/> qui permettent respectivement de leur associer un titre et une description. Ces éléments sont importants pour rendre les contenus graphiques accessibles, par exemple par les personnes avec des déficits visuels ou celles utilisant des matériels/logiciels ayant des capacités graphiques limitées. J'ai donc mis en place quelques commandes permettant à l'auteur de générer des contenus accessibles, comme conseillé dans [4].

Tout d'abord, pour chaque élément SVG, on peut utiliser une boite de dialogue qui permet d'éditer le titre et la description. De plus, les composants pré-définis possède un titre par défaut, traduit dans la langue de l'utilisateur.

Contrairement à une image matricielle où seule une description peut être fournie, l'image SVG offre une véritable structure à l'image comme on l'a vu dans la section 3.2.1 sur le positionnement des calques. Cela permet de savoir quel objet est devant un autre et de connaitre ceux qui sont "regroupés" en une entité. Une information intéressante mais plus difficile à obtenir est la répartition spatiale des objets. J'ai donc réalisé un algorithme simple qui génère une description d'un élément donné en prenant en compte les titres de ses fils :

3.3.1.1. Algorithme

On souhaite afficher la description d'un élément en considérant les fils comportant un titre ( fils[i] ). i varie de 1 au nombre d'éléments à décrire. La fonction obtenir distance donne la distance entre les centres des boites englobantes de deux éléments.

GenererDescription (nombre)

<< complexité en O(nombre^2)

AfficherNombreÉléments(nombre)

Pour i de 1 à nombre

  AfficherPositionAbsolu(fils[i])
      
  Si i > 0

    j_min := 0
    distance_min := ObtenirDistance(fils[i], fils[0] )

    Pour j de 1 à i - 1

      r := ObtenirDistance(fils[i], fils[j])
      Si r < distance_min
        j_min := j
        distance_min := r
      FinSi

    FinPour

    AfficherPositionRelative (fils[i], fils[j_min])

  FinSi

FinPour
      
FinGenererDescription

Il y a deux types de fonctions d'affichage de positions :

1. AfficherPositionAbsolu : On découpe largeur et hauteur de la boite englobante de l'objet en trois, ce qui donne neuf zones : coin supérieur gauche, haut, coin supérieur droit, gauche, centre, droite, coin inférieur gauche, bas, coin inférieur droit. On indique alors la position du centre de la boite englobante du fils.
2. AfficherPositionRelative : On regarde les positions des bords des boites englobante des deux fils verticalement et horizontalement. Par exemple 1 est à droite de 2 si le bord gauche de 1 est à droite du bord droit de 2. On obtient ainsi 3 valeurs verticales et 3 valeurs horizontales qui conduisent à 9 positions : au dessus et à gauche, au dessus, au dessus et à droite, à gauche, devant, à droite, en dessous et à gauche, en dessous, en dessous et à droite. La valeur "devant" correspond au cas où les fils se chevauchent. On s'arrange donc pour que les arguments soient passés dans un ordre précis.

3.3.1.2. Exemple

On a dessiné le schéma suivant à partir des composants prédéfinis d'Amaya et de formes élémentaires. Par défaut, les composants ont un <title/> "Burette" et "Bécher". En utilisant la commande "Édition des informations", on ajoute les titres "Barreau aimanté" et "Agitateur magnétique" aux éléments SVG correspondants. Les formules des composants chimiques sont écrites en MathML. Elles comportent un texte alternatif (un avertissement) qui est affiché si le navigateur n'est pas capable de gérer le MathML dans du SVG (cf section 3.1.2). De plus elles sont groupées avec les éléments <text/> associés ("Burette" et "Bécher").

Ilya4objets:[Agitateurmagnétique]enbas.[Bécher]enbas,audessusde[Agitateurmagnétique].[Burette]aucentre,audessusde[Bécher].[Barreauaimanté]enbas,audessusde[Agitateurmagnétique]. Agitateur magnétique Bécher Burette Barreau aimanté Barreau aimanté Bécher $\mathrm{FeS}{O}_4$ embedded MathML not supported Agitateur magnétique Burette $K\mathrm{Mn}{O}_4$ embedded MathML not supported

La commande "Générer une description" appliquée au canevas SVG ajoute un <desc/> avec pour contenu :

Il y a 4 objets : [Agitateur magnétique] en bas. [Bécher] en bas, au dessus de [Agitateur magnétique]. [Burette] au centre, au dessus de [Bécher]. [Barreau aimanté] en bas, au dessus de [Agitateur magnétique].

On remarque que le fait de ne prendre en compte que les éléments avec un intitulé permet de conserver uniquement ceux qui sont pertinents : on ignore les lignes ou la table de travail qui ne sont pas utiles pour la compréhension du schéma. On peut ensuite améliorer la description, par exemple en indiquant que le barreau aimanté est en réalité à l'intérieur du Bécher ou en ajoutant des informations sur les produits chimiques.

On remarque que contairement à une image matricielle, le contenu des éléments <text/> utilisés est accessible. Grace aux groupes <g/>, les navigateurs peuvent informer l'utilisateur quelle formule mathématique est associée à "Burette" et "Bécher". L'accès à ces formules dépend des capacités du navigateur. Ici, il convient de remplacer le texte d'avertissement par le nom des composants "permanganate de potassium" et "sulfate de fer".

3.3.2. Reconnaissance des figures élémentaires

Comme on l'a vu dans l'étude du langage SVG, il n'existe que très peu de figures élémentaires : rectangle, cercle et ellipse. Si cela peut être suffisant pour des logiciels à vocation artistique comme Inkscape, on aimerait avoir des formes plus diversifiée pour les schémas, par exemple pour faire de la géométrie. Les formes retenues sont celles mises à disposition dans l'ensemble de constructions "figures élémentaires" décrit précédemment (3.1.3).

Les deux dernières sont décrites par les éléments <circle/> et <ellipse/>. Les autres figures peuvent soit être décrites par un <polygon/> soit par un <path> composé d'un seul sous-chemin avec des segments de droites dont le départ et l'arrivée sont confondues. On pourrait aussi utiliser les <polyline/>, mais je n'ai pas traité ce cas qui correspond plus à des courbes ouvertes (section 9.6 de [14]). Enfin, les deux premiers peuvent aussi être des <rect/> ce qui autorise les coins arrondis. Lors de l'analyse syntaxique du code XML, les figures sont reconnues par l'algorithme 3.3.2.1 qui peut être désactivé en modifiant la variable d'environnement ENABLE_SHAPE_RECOGNITION.

Comme Amaya travaille avant tout sur la structure et non le rendu visuel, les éléments XML ne doivent pas être transformés sans l'accord de l'utilisateur : ainsi un <path/> reconnu comme un losange n'est pas changé en <polygon/>, mais il utilise simplement une structure interne spécifique. Par exemple, Thot disposait déjà de la structure losange, tracé en joignant les mileux des cotés de la boite graphique.

La reconnaissance des figures se fait en utilisant les propriétés élémentaires de la géométrie euclidienne, en se donnant une marge d'erreur due aux approximations. Notons que l'on peut caractériser les figures par les longueurs (pythagore, coté égaux) ou d'angle (angle 90°, angles égaux). On choisi la seconde caractérisation qui semble donner de meilleurs résultats en pratique aux regards des tests réalisés. De plus on peut fixer la constante d'erreur EPSILON_MAX de façon uniforme, qui est de 1 degré. Ainsi une fonction PresqueÉgaux vérifie si deux angles sont environ égaux. De même, PresqueOrthogonaux, PresquePositivementColinéaires vérifient si les angles de vecteurs sont environ de 90° ou 0°. Le positivement colinénaire utilisé lors de la reconnaissance des trapèzes permet d'assurer le convexité du polygone.

Pour l'algorithme, on considère un polygone avec des points numérotés de 1 à NombreDePoints. (i.e. la liste des points obtenus par un <polygon/> ou un <path/>). PermutationCirculaire(X->Y) réalise une permutation circulaire sur les points du polygone, qui place le point X en position Y. Cette fonction est importante pour pouvoir ensuite convertir l'ensemble de points en une structure interne : par exemple pour un triangle isocèle, le premier point sera le sommet principal. On ajoute aussi quelque simplification comme le fait que le parallélogramme est incliné vers la droite ou que le trapèze a sa plus petite base en haut.

On utilise enfin les notations [A>B] et [A>B>C] pour représenter respectivement le vecteur de $\overrightarrow{AB}$ et l'angle $\widehat{\mathrm{ABC}}$.

3.3.2.1. Algorithme

ReconnaitreFigure (polygone[1, 2, ... NombreDePoints])

<< Complexité en O(1) >>

Si NombreDePoints = 3

  Si PresqueOrthogonaux([1>2], [1>3])
    figure :=  TRIANGLE_RECTANGLE
  SinonSi PresqueOrthogonaux([2>3], [2>1])
    figure :=  TRIANGLE_RECTANGLE
    PermutationCirculaire(1->2)
  SinonSi PresqueOrthogonaux([3>2], [3>1])
    figure :=  TRIANGLE_RECTANGLE
    PermutationCirculaire(1->3)
  Sinon

    Si PresqueÉgaux([1>2>3], [2>3>1])
      figure := TRIANGLE_ISOCÈLE
    SinonSi PresqueÉgaux([3>1>2], [1>2>3])
      figure := TRIANGLE_ISOCÈLE
      PermutationCirculaire(1->3)
    SinonSi PresqueÉgaux([3>1>2], [2>3>1])
      figure := TRIANGLE_ISOCÈLE
      PermutationCirculaire(1->2)
    FinSi

    Si figure = TRIANGLE_ISOCÈLE
      Si PresqueÉgaux([3>1>2], [1>2>3])
        figure := TRIANGLE_ÉQUILATÉRAL;
      FinSi
    FinSi

  FinSi

SinonSi NombreDePoints = 4
      
  Si PresquePositivementColinéaires([1>2], [3>4])
    figure := TRAPÈZE
  SinonSi PresquePositivementColinéaires([2>3], [1>4])
    figure := TRAPÈZE
    PermutationCirculaire(1->2)
  FinSi
      
  Si figure = TRAPÈZE
    Si PresqueÉgaux([1>2>3], [3>4>1])
      figure := PARALLÈLOGRAMME

      Si PresqueÉgaux([2>4>1], [1>2>4])
        figure := LOSANGE
      FinSi

      Si PresqueOrthogonaux([1>2], [2>3])
        Si figure = LOSANGE
          figure := CARRÉ
        Sinon
          figure := RECTANGLE
        FinSi
      FinSi

      Si figure = PARALLELOGRAMME et EstAigu([4, 1, 2])
        PermutationCirculaire(1->2)
      FinSi
      
    FinSi

    Si figure = TRAPÈZE et Norme(4>3) < Norme(1>2)
      PermutationCirculaire(1->3)
    FinSi

  FinSi

FinSi

FinReconnaitreFigure

Une fois la figure reconnue avec ses points caractéritiques triés, on peut ensuite trouver une boite englobante dans laquelle la figure sera tracée. Toutefois la boite a toujours ses cotés parallèles aux axes du repère local alors que le polygone peut être "tourné". On va alors rechercher les coefficients de la matrice de transformation $A=\left(\begin{array}{cc}a& c\\ b& d\end{array}\right)$ et de la translation $\left(\begin{array}{c}e\\ f\end{array}\right)$ à appliquer localement pour pouvoir mettre la boite dans le bon sens. Commençons par le cas du rectangle :

UnrectanglededimensionsL,H.Enpartantducoinsupérieurgaucheetentournantdanslesensdesaiguillesd'unemontre,lessommetssontnumérotésde1à4. 1 2 3 4 L H

A partir des quatre points du rectangle, on détermine facilement les dimensions $L,H$ de la boite englobante. On souhaite ensuite avoir les équations suivantes :

• $A\left(\begin{array}{c}0\\ 0\end{array}\right)+\left(\begin{array}{c}e\\ f\end{array}\right)=\left(\begin{array}{c}{x}_1\\ y_1\end{array}\right)$
• $A\left(\begin{array}{c}L\\ 0\end{array}\right)+\left(\begin{array}{c}e\\ f\end{array}\right)=\left(\begin{array}{c}{x}_2\\ y_2\end{array}\right)$
• $A\left(\begin{array}{c}L\\ H\end{array}\right)+\left(\begin{array}{c}e\\ f\end{array}\right)=\left(\begin{array}{c}{x}_3\\ y_3\end{array}\right)$
• $A\left(\begin{array}{c}0\\ H\end{array}\right)+\left(\begin{array}{c}e\\ f\end{array}\right)=\left(\begin{array}{c}{x}_4\\ y_4\end{array}\right)$

On en déduit alors $a=\frac{x_2-x_1}{L},b=\frac{y_2-y_1}{L},c=\frac{x_4-x_1}{H},d=\frac{y_4-y_1}{H},e=x_1,f=y_1$. Pour la plupart des figures, on peut trouver une expression directe des coefficients à partir des coordonnées de points. De telles expressions sont fournies dans l'algorithme 3.3.2.2 et je laisse au lecteur le soin de les retrouver. Pour d'autres comme le trapèze ou le parallélogramme, on peut se ramener au cas du rectangle en déterminant les coordonnées des points de la boites englobante comme intersection de deux droites. Par exemple pour le trapèze, on considère des droites passant par les sommets et dirigés par un vecteur coliénaire/orthogonal à l'axe du trapèze. De tels vecteurs s'expriment facilemement en fonction des coordonnées des points : $\left(\begin{array}{c}{x}_2-x_1\\ y_2-y_1\end{array}\right)$ est un vecteur coliénaire et $\left(\begin{array}{c}{y}_2-y_1\\ -\left(x_2-x_1\right)\end{array}\right)$ un vecteur orthogonal.

Un trapèze avec les droites formant sa boite englobante

On cherche maintenant à déterminer l'intersection de deux droites : l'une passant par un point de coordonnées $\left(\begin{array}{c}{a}_1\\ b_1\end{array}\right)$ dirigée par le vecteur $\left(\begin{array}{c}{\mathrm{dx}}_1\\ {\mathrm{dy}}_1\end{array}\right)$, l'autre par un point de coordonnée $\left(\begin{array}{c}{a}_2\\ b_2\end{array}\right)$ dirigée par le vecteur $\left(\begin{array}{c}{\mathrm{dx}}_2\\ {\mathrm{dy}}_2\end{array}\right)$. Le point d'intersection $\left(\begin{array}{c}{x}_0\\ y_0\end{array}\right)$ vérifie pour des paramètres $t,u$ à déterminer : $\left(\begin{array}{c}{a}_1\\ b_1\end{array}\right)+t\left(\begin{array}{c}{\mathrm{dx}}_1\\ {\mathrm{dy}}_1\end{array}\right)=\left(\begin{array}{c}{x}_0\\ y_0\end{array}\right)$ et $\left(\begin{array}{c}{a}_2\\ b_2\end{array}\right)+u\left(\begin{array}{c}{\mathrm{dx}}_2\\ {\mathrm{dy}}_2\end{array}\right)=\left(\begin{array}{c}{x}_0\\ y_0\end{array}\right)$, ce qui conduit au système matriciel $\left(\begin{array}{cc}{\mathrm{dx}}_1& -{\mathrm{dx}}_2\\ {\mathrm{dy}}_1& {-\mathrm{dy}}_2\end{array}\right)\left(\begin{array}{c}t\\ u\end{array}\right)=\left(\begin{array}{c}{a}_2-a_1\\ b_2-b_1\end{array}\right)$ d'où on tire $t$ puis les coordonnées $\left(\begin{array}{c}{x}_0\\ y_0\end{array}\right)$ recherchées (en supposant que le système ait une unique solution, i.e que les droites ne sont pas parallèles).

3.3.2.2. Algorithme

Pour alléger l'algorithme, on n'indique pas les vérifications de "division par zéro". PointIntersection(X, U, Y, V) donne le point d'intersection des droites passant par X et Y et dirigée par U, V. On note $x_i$ et $y_i$ les coordonnées du point $i$.

ObtenirTailleBoiteEtCoefficients(figure, [1, ... NombreDePoints])

<< Complexité en O(1) >>

ChoisirSelon figure

  Cas TRIANGLE_ÉQUILATÉRAL, TRIANGLE_ISOCÈLE
    L := Norme([3>2])
    H := Norme([Milieu(2,3)>1])
      
    e := x1 + (x3 - x2)/2
    f := y1 + (y3 - y2)/2
      
    a := (x2 - x3)/L
    b := (y2 - y3)/L
    c := (x3 - e)/H
    d := (y3 - f)/H
  FinCas

  Cas TRIANGLE_RECTANGLE
    L = Norme([1>2])
    H = Norme([1>3])
    a := (x2 - x1)/L
    b := (y2 - y1)/L
    c := (x3 - x1)/H
    d := (y3 - y1)/H
    e := x1
    f := y1
  FinCas

  Cas TRAPÈZE
    Si EstAigu([4>1>2])
      1' = 1
      4' = PointIntersection(1, Orthogonal([1>2]), 4, [4>3])
    Sinon
      1' = PointIntersection(1, [1>2], 4, Orthogonal([4>3]))
      4' = 4
    FinSi

    Si EstAigu([1>2>3])
      2' = 2
      3' = PointIntersection(2, Orthogonal([1>2]), 3, [3>4])
    Sinon
      2' = PointIntersection(2, [1>2], 3, Orthogonal([3>4]))
      3' = 3
    FinSi

    L = Norme(1'>2')
    H = Norme(1'>4')

    a := (x2' - x1')/W
    b := (y2' - y1')/W
    c := (x4' - x1')/H
    d := (y4' - y1')/H
    e := x1'
    f := y1'
  FinCas

  Cas PARALLÉLOGRAMME
    1' = PointIntersection(1, [1>2], 4, Orthogonal([4>3]))
    2' = 2
    3' = PointIntersection(2, Orthogonal([1>2]), 3, [3>4])
    4' = 4

    L = Norme(1'>2')
    H = Norme(1'>4')
    a := (x2' - x1')/W
    b := (y2' - y1')/W
    c := (x4' - x1')/H
    d := (y4' - y1')/H
    e := x1'
    f := y1'
  FinCas

  Cas LOSANGE
    L = Norme([2>4])
    H = Norme([1>3])

    a := (x2 - x4)/L
    b := (y2 - y4)/L
    c := (x3 - x1)/H
    d := (y3 - y1)/H
    e := x1 - a*L/2
    f := y1 - b*L/2
  FinCas

  Cas CARRÉ, RECTANGLE
    L = Norme(1>2)
    H = Norme(1>4)
    a := (x2 - x1)/W
    b := (y2 - y1)/W
    c := (x4 - x1)/H
    d := (y4 - y1)/H
    e := x1
    f := y1
  FinCas

  FinChoisirSelon

FinObtenirTailleBoiteEtCoefficients

Notons que puisque le changement de repère n'est constitué que de symétrie, rotation et translation, la matrice trouvée peut en théorie se décomposer en produit d'un scale avec des coefficients ±1, d'un rotate et d'un translate. En pratique, lorsque des figures sont tournées on peut obtenir la décomposition générale avec des skew+scale+translate, à cause de l'accumulation des approximations. Il faudrait améliorer l'algorithme de façon à directement rechercher une décomposition en scale+rotate+translate au lieu d'une forme générale pour la matrice de décomposition.

3.3.3. Édition des figures élémentaires

Une fois les figures reconnues, elles peuvent être manipulées de façon particulière par l'utilisateur. Lorsqu'elles sont sélectionnées, des poignées spécifiques sont affichées sur ces figures en des points caractéristiques du contour de la figure ou de celui de la boite englobante. Lorsque l'utilisateur tire sur une de ces poignées il déplace un point de la figure ou de la boite englobante. Les points de la figure sont alors mis à jour de façon à respecter les contraintes imposées. Certaines figures ont aussi des cercles rouges qui peuvent être déplacés pour les déformer.

Figure (char associé)	Tracé dans la boite englobante	Contrainte sur la boite englobante	Image de la sélection
Carré (7)	Coïncide avec la boite englobante.	Hauteur = Largeur
Carré à coins arrondis (1)	idem	Les cercles rouges restent sur une moitié des cotés.
Rectangle (8)	idem	/	cf carré
Rectangle à coins arrondis ('C')	idem	cf carré arrondi	cf carré arrondi
Losange ('L')	Les sommets du losange sont les mileux de la boite englobante.	/
Parallélogramme (2)	Deux points du parallélogramme correspondent à des sommets de la boite. Les autres sont précisés par un nombre (positif ou négatif).	Les cercles rouges restent sur les cotés de la boite englobante et sont déplacés simultanément pour rester symétriquement disposés.
Trapèze (3)	Deux points du parallélogramme correspondent à des sommets de la boite. Les autres sont précisés par deux nombres (positifs ou négatifs).	Les cercles rouges restent sur les cotés de la boite englobante. Le trapèze ne peut pas être "croisé".
Triangle équilatéral (4)	Le sommet principal est au milieu du coté supérieur de la boite englobante. Les deux autres sommets sont les extrémités du coté inférieur de la boite.	$\mathrm{Hauteur}=\frac{\sqrt{3}}{2}\mathrm{Largeur}$
Triangle isocèle (5)	idem	/	cf triangle équilatéral
Triangle rectangle (6)	Le triangle rectangle a son angle droit dans le coin supérieur gauche de la boite englobante. Les deux autres sommets sont dans les coins supérieur droit et inférieur gauche.	/
Cercle ('a')	Inscrit dans la boite englobante.	Hauteur = Largeur
Ellipse ('c')	Inscrit dans la boite englobante, les demi-axes sont parallèles aux cotés de la boite.	/	cf cercle

Les rectangles (et carrés) spéciaux correspondent aux éléments <rect/>. Ceux-ci peuvent en effet avoir des attributs rx et ry variant entre 0 et les demi-dimensions du rectangle qui indiquent les rayons des coins arrondis. Des poignées représentées par de petits ronds rouges peuvent être glissés le long des cotés du rectangle de façon à faire varier ces rayons. Dans le cas où seul un des attribut rx ou ry est donné, la spécification [14] précise que les rayons doivent être égaux. Dans ce cas, le module d'édition modifie les rayons en conservant cette contrainte.

Rectangleà coins arrondis rx et ry rx ry

Pour le parallélogramme, l'inclinaison est indiquée par une distance $d$ dont le signe donne la direction d'inclinaison et la valeur absolue l'amplitude. Les cercles rouges peuvent être glissés le long des cotés supérieurs et inférieurs.

Parallélogrammes ladistancehorizontaledvadubordgauchedelaboiteenglobantejusqu'àunsommetduparallélogrammenonconfonduavecuncoindelaboite.Leparallélogrammeestinclinéversladroitesietseulementsidestpositif. d $d\ge 0$ embedded MathML not supported d $d\le 0$ embedded MathML not supported

Le trapèze ne possède pas de petits cercles coulissables car je n'ai pas programmé l'opération dans le module. L'inclinaison est décrite de la même façon que le parallélogramme mais il faut cette fois deux paramètres $d_1$ et $d_2$ indépendants :

Trapèze Lesdistancesd1etd2sontsimilairesaucasduparallélogramme.Ici,d1estpositif,d2négatifetlesdistancessontégalesenvaleurabsolue.Onobtientuntrapèzeisocèle. $d_1$ embedded MathML not supported $d_2$ embedded MathML not supported $d_1\ge 0,d_2\le 0$ embedded MathML not supported

Notons pour terminer que le module d'édition des trapèze et parallélogramme n'a pas été connecté. La visualisation et l'édition ont toutefois été testées en utilisant ce qui existait pour les boites représentants le rectangle à coins arrondis (utilisation des deux paramètres rx et ry pour représenter les distances).

3.3.4. Édition des points d'une courbe

Amaya possède un certain nombre de commandes génériques pouvant être appliquées aux éléments de l'arbre Thot : couper, coller, insérer, ajouter, détruire... Cependant les points des <polyline/>, <polygon/> et <path/> sont décrits comme des structures de données spécifiques attachées à une feuille du noeud représentant l'élément SVG. Il est nécessaire d'ajouter un traitement spécifiques pour ces éléments. Il existait déjà des fonctions pour sélectionner un point d'un <polyline/> et un module bogué pour déplacer des points. C'est sur cette interface que je me suis basé. Elle présente néanmoins le désavantage de ne pouvoir sélectionner qu'un point à la fois, ce qui empêche d'envisager des opérations sur des groupes de points. La sélection est décrite visuellement de la façon suivante :

• Tous les points de contrôle sur une courbe sont mis en valeur par des carrés verts.
• Si un point est sélectionné, ce carré est dessiné en plus gros.
• Si le point sélectionné est adjacent à une poignée de Bézier, celle-ci est affichée.

Les trois opérations retenues pour l'édition de points sont détruire, insérer et ajouter. La première supprime un point de la courbe. Les deux autres créer un nouveaux points respectivement sur le segment qui précède ou suit le point sélectionné, si il en existe un.

Pour les <polyline/>, le point est créé au mileu du segment. Il y a aussi un traitement spécifique aux extrémités, par exemple si on créé un point avant le premier point du <polyline/>, il sera le symétrique du second point par rapport au premier. De même, si on créé un point après le dernier point, il sera le symétrique de l'avant-dernier par rapport au premier.

Pour les <path/>, on recherche le fragment adjacent au point sélectionné et on le divise en deux selon son type. On s'arrête au "milieu" de la courbe, au sens de la paramétrisation utilisée.

• Pour un segment, on créer un point au milieu (en fait cela revient à une courbe de Bézier linéaire).
• Pour les courbes de Bézier cubique/quadratique, en prenant la paramétrisation en $t$, on créer le point donné à l'instant $\frac{t}{2}$.
• Pour un arc, en prenant la paramétrisation selon le centre (cf appendix F.6 de [14]) où $\theta$ varie entre ${\theta }_1$ et ${\theta }_1+\mathrm{\Delta \theta }$, on créer le point donné à l'instant ${\theta }_1+\frac{\mathrm{\Delta \theta }}{2}$

On conçoit facilement qu'un segment peut être découpé en deux segments et un arc d'ellipse en deux arcs d'ellipse. Pour les courbes de Bézier, cela est moins immédiat puisqu'il faut a priori repositionner les poignées.

3.3.4.1. Proposition

Une courbe de bézier $P\left(t\right)$ de point de contrôle $P_0$ ... $P_n$ peut être divisée en deux courbes de Bézier de même degré dont les points de départ et d'arrivée sont respectivement $P\left(0\right)$ et $P\left(\frac{1}{2}\right)$ pour la première et $P\left(\frac{1}{2}\right)$ et $P\left(1\right)$ pour la seconde.

Démonstration : on traite le cas $n=3$ et on cherche le premier fragment. Les expressions obtenues pourront facilement se généraliser. On a donc $P\left(t\right)={\left(1-t\right)}^3{P}_0+3{\left(1-t\right)}^{2}t{P}_1+3\left(1-t\right)t^3{P}_2+t^3{P}_3$ et on cherche une courbe $Q\left(t\right)$ de même forme telle que $\forall t\in [0,\frac{1}{2}]Q\left(2t\right)=P\left(t\right)$. Notons au passage que les fonctions étant polynomiales, on aura en fait cette égalité sur tout $ℝ$.

analyse. Si $Q\left(t\right)$ est la courbe recherchée alors $\frac{dQ}{dt}\left(2t\right)=\frac{1}{2}\frac{dP}{dt}\left(t\right)$. On trouve $P\left(0\right)=P_0,P\left(1\right)=P_3,\frac{dP}{dt}\left(0\right)=3(P_1-P_0),\frac{dP}{dt}\left(1\right)=3(P_3-P_2)$ et de même pour $Q$. De plus $\frac{dP}{dt}\left(\frac{1}{2}\right)=\frac{3}{4}(P_3+P_2-P_1-P_0)$ et $P\left(\frac{1}{2}\right)=\frac{1}{8}(P_0+3P_1+3P_2+P_3)$. En prenant les égalités entre $Q$ et $P$ et leurs dérivées aux différents points, on obtient finalement $Q_0=P_0,Q_1=\frac{P_0+P_1}{2},Q_2=\frac{P_0+2P_1+P_2}{4},Q_3=\frac{P_0+3P_1+3P_2+P_3}{8}$.

synthèse. en réinjectant les coefficients trouvés, on retrouve bien $Q\left(2t\right)=P\left(t\right)$. □

Le programme Maxima ci-dessous permet de vérifier les égalités pour les cas quadratique et cubique qui nous intéressent :

3.3.4.2. Programme Maxima

/* Courbe de Bézier cubique */

P(t):=(1-t)^3*P0+3*(1-t)^2*t*P1+3*(1-t)*t^2*P2+t^3*P3;
Q(t):=(1-t)^3*Q0+3*(1-t)^2*t*Q1+3*(1-t)*t^2*Q2+t^3*Q3;

/* Fragment 1 */

Q0 : P0;
Q1 : (P0+P1)/2;
Q2 : (P0+2*P1+P2)/4;
Q3 : (P0+3*P1+3*P2+P3)/8;

ratsimp(P(t) - Q(2*t));

/* Fragment 2 */

Q0 : (P0+3*P1+3*P2+P3)/8;
Q1 : (P1+2*P2+P3)/4;
Q2 : (P2+P3)/2;
Q3 : P3;

ratsimp(P(1/2+t) - Q(2*t));

/* Courbe de Bézier quadratique */

P(t):=(1-t)^2*P0+2*(1-t)*t*P1+t^2*P2;
Q(t):=(1-t)^2*Q0+2*(1-t)*t*Q1+t^2*Q2;

/* Fragment 1 */

Q0 : P0;
Q1 : (P0+P1)/2;
Q2 : (P0+2*P1+P2)/4;

ratsimp(P(t) - Q(2*t));

/* Fragment 2 */

Q0 : (P0+2*P1+P2)/4;
Q1 : (P1+P2)/2;
Q2 : P2;

ratsimp(P(1/2+t) - Q(2*t));

La suppression d'un point dans un polyline/polygone est possible jusqu'à un nombre minimum de 2 points. Elle se fait naturellement : on retire le point sélectionné de la liste des points.

Pour un chemin, la suppression est moins évidente puisque ce dernier est décrit comme une liste de segments (ligne, courbe de Bézier ou arc) non comme une liste de points. On supprime alors le segment arrivant sur ce point en s'arrangeant pour que les poignées de Bézier des segments encadrants (si ce sont des courbes de Bézier) ne soient pas modifiées.

Il existe encore quelques problèmes pour la suppression des points. Par exemple la suppression du premier point d'un sous-chemin n'est pas possible (il n'y a pas de segment arrivant à ce point) et la suppression du second point supprime aussi le premier.

3.3.5. Déplacement des points d'une courbe

Le déplacement des points d'une courbe ou d'une poignée se réalise simplement en cliquant sur le point et en le faisant glisser à la nouvelle position. Il n'y a pas de problème particulier pour les <polyline/> ou <polygon/> puisqu'il suffit de mettre à jour le point sélectionné et que le fait que ces figures soient fermée ou ouverte est immédiatement connu. Pour les <path/> cela est plus compliqué :

• Le chemin peut contenir plusieurs sous-chemins.
• Il n'est pas indiqué dans la structure XML que le chemin est ouvert/fermé.
• Il existe différents types de segments : lignes, arcs et courbes de Bézier.
• Il faut mettre à jour les poignées de Bézier en plus des points.

Si un point possède une poignée de Bézier avant et après lui, alors les deux demi-tangentes décrites par ces poignées peuvent être reliés entre elles de trois façons :

• Dur : les poignées peuvent être déplacée indépendemment. C'est le cas si on appuie sur la touche shift pendant l'édition.

  Poignées de Bézier dures

• Doux : les deux demi-tangentes sont alignés. Ce cas n'a pas été mis en place dans Amaya.
• Symétrique : c'est le cas par défaut.

  Poignées de Bézier symétriques

Lorsque l'on déplace une poignée, il faut d'assurer que ces contraintes soient conservées. Lorsque l'on déplace un point, les poignées subissent la même translation.

Comme précédemment, pour savoir si un sous-chemin est fermé on regarde si le premier et dernier point coïncident. Dans ce cas, tout se passe comme si ces deux points n'en formaient qu'un seul, se comportant comme n'importe quel point intermédiaire du sous-chemin : ils sont déplacés simultanéments et leurs poignées de Bézier sont liées.

Une poignée de Bézier peut provenir d'un segment quadratique ou cubique. Dans le cas quadratique, les deux tangentes successives sont "reliées" au point de controle. Si on souhaite conserver l'alignement des points, une succession de courbes quadratiques pourraient conduire à la mise à jour de toute une chaine :

Courbes de Bézier quadratiques Plusieursfragmentsreliésentreeux.Achaquefois,lespoignéesdeBéziersontpartagéesentredeuxfragmentssuccessifs.

Pour simplifier le problème, on effectue une conversion d'une courbe de Bézier quadratique à une courbe de Bézier cubique comme indiqué dans [5]. En notant les points de controle du fragment quadratique $P_k$ et $P_k\text{'}$ ceux du fragment cubique, on effectue le changement $P_k\text{'}=\frac{k}{3}{P}_{k-1}+\left(1-\frac{k}{3}\right)P_k$. On peut ensuite effectuer le traitement comme une courbe cubique normale. Cette conversion n'est pas forcément très discrète puisque l'utilisateur voit les poignées rétrécir avant l'édition d'une courbe quadratique.

Pour les segments de chemin qui sont des lignes ou des arcs, on se contente de mettre à jour les positions des points. Cela est problématique pour les arcs puisque ceux-ci sont décrits par plusieurs paramètres : rayons, angles... J'ai essayé de réaliser une mise à jour pour conserver l'aspect de l'arc mais le résultat n'était pas satisfaisant. Voir l'annexe (5.1.2).

3.4. Transformations

3.4.1. Manipulation des transformations en interne

Thot possède une structure de liste chainée permettant de représenter des compositions de transformations SVG. Des fonctions de manipulation sont disponibles dans le module thotlib/content/contentapi.c. Pour les opérations internes, j'ai réalisé des fonctions permettant de simplifier cette liste en une seule matrice de transformation, d'appliquer une transformation supplémentaire ou encore d'inverser une matrice de transformation. J'ai été amené à étudier la forme générale d'une transformation. Le point de départ de mon investigation est le théorème suivant :

3.4.1.1. Théorème

Toute matrice carré $\left(\begin{array}{cc}a& c\\ b& d\end{array}\right)$ peut se décomposer comme un produit des matrices d'étirement, de rotation et d'inclinaisons. Plus précisément, on peut se limiter à un étirement, une inclinaison selon les X, une inclinaison selon les Y et enfin une rotation de 90° (ou une inclinaison de 45° supplémentaire).

Démonstration :

1. $a\ne 0$. En posant ${\theta }_1=\arctan \frac{b}{a}$ et ${\theta }_2=\arctan \frac{c}{a}$ on a $\left(\begin{array}{cc}a& c\\ b& d\end{array}\right)=I_y\left({\theta }_1\right)S\left(a,d-\frac{bc}{a}\right)I_x\left({\theta }_2\right)$
2. $d\ne 0$. En posant ${\theta }_1=\arctan \frac{c}{d}$ et ${\theta }_2=\arctan \frac{b}{d}$ on a $\left(\begin{array}{cc}a& c\\ b& d\end{array}\right)=I_x\left({\theta }_1\right)S(a-\frac{bc}{d},d)I_y\left({\theta }_2\right)$
3. $a=d=0$. $\left(\begin{array}{cc}a& c\\ b& d\end{array}\right)=\left(\begin{array}{cc}0& c\\ b& 0\end{array}\right)=\left(\begin{array}{cc}0& -1\\ 1& 0\end{array}\right)\left(\begin{array}{cc}b& 0\\ 0& -c\end{array}\right)=R\left(90°\right)S\left(b,-c\right)$

Remarquons pour conclure que les rotations s'écrivent en fonction d'étirement et d'inclinaisons :

$R\left(\theta \right)=\{\begin{array}{c}{I}_x\left(\frac{\pi }{4}\right)I_y(-\frac{\pi }{4})I_x\left(\frac{\pi }{4}\right)\text{pour}\theta =-90°\\ I_y\left(\frac{\pi }{4}\right)I_x(-\frac{\pi }{4})I_y\left(\frac{\pi }{4}\right)\text{pour}\theta =90°\\ I_x\left(-\theta \right)S(\frac{1}{\cos \theta },\cos \theta )I_y\left(\theta \right)\text{sinon}\end{array}$

En particulier, dans le troisième cas ($a=d=0$) on peut substituer la matrice de rotation $R\left(90°\right)$ et écrire $\left(\begin{array}{cc}0& c\\ b& 0\end{array}\right)$ comme produit de deux inclinaisons le long de l'axe des X, d'une le long de l'axe des Y et d'un étirement. □

3.4.1.2. Programme Maxima

Le programme Maxima suivant permet de vérifier les formules données dans le théorème 3.4.1.1 :

S(sx, sy) := matrix([sx,0], [0,sy]);
R(T) := matrix([cos(T),-sin(T)], [sin(T),cos(T)]);
Ix(T) := matrix([1,tan(T)], [0,1]);
Iy(T) := matrix([1,0], [tan(T),1]);

Iy(atan(b/a)).S(a,d-b*c/a).Ix(atan(c/a));
Ix(atan(c/d)).S(a-b*c/d,d).Iy(atan(b/d));
R(%pi/2).S(b,-c);

R(-%pi/2);
Ix(%pi/4).Iy(-%pi/4).Ix(%pi/4);
R(%pi/2);
Iy(%pi/4).Ix(-%pi/4).Iy(%pi/4);
R(T);
trigsimp(trigreduce(Ix(-T).S(1/cos(T), cos(T)).Iy(T)));

3.4.1.3. Corollaire

Une application affine peut s'écrire comme composée des transformations élémentaires comportant au plus une translation, un étirement, une inclinaison selon l'axe des X, une inclinaison selon l'axe des Y et une rotation de 90°.

Démonstration : Le résultat précédent a montré que (sans translation) on pouvait engendrer toutes les applications linéaires. L'adjonction des translations permet donc de généraliser au cas des applications affines. □

3.4.1.4. Corollaire

Les applications affines dans le plan sont engendrées par les translations, étirements, inclinaisons selon les X et inclinaisons selon les Y. Ce résultat est optimal au sens où on ne peut retirer un de ces types de transformations.

Démonstration : On utilise la version de la proposition utilisant l'inclinaison de 45° pour montrer que ces transformations suffisent à engendrer l'ensemble des applications affines. Si on retire les translations, on ne peut plus effectuer que des applications linéaires. Si on retire les étirements, on obtient plus que des matrices de déterminant égal à 1. Si on retire une inclinaison selon un axe, la matrice de la composante linéaire ne peut être que triangulaire. □

Du point de vue théorique, la décomposition du corollaire 3.4.1.3 permet de concevoir plus clairement l'image d'un objet et d'étudier la transformation réciproque (toutes les matrices sont facilement inversibles sauf l'étirement qui l'est si et seulement si les facteurs d'échelle sont non nuls). Du point de vue pratique, cela est utile si l'utilisateur souhaite éditer l'attribut transform dans la vue source, dans la vue structure ou même dans un menu. En effet, sauf dans des cas simples, la matrice de transformation est difficilement compréhensible pour l'utilisateur et une écriture comme composition de transformations élémentaires est donc préférable.

Le corollaire 3.4.1.4 indique quant à lui qu'il suffit simplement de donner à l'utilisateur la possibilité de réaliser trois transformations simples (translations, étirements et inclinaisons) pour qu'il puisse réaliser n'importe quelle transformation affine.

La démonstration est constructive et donne directement un algorithme de décomposition. Bien que l'on puisse se restreindre à l'utilisation d'un pivotement de 90° ou même se passer complètement des rotations, elles sont parfois préférables aux inclinaisons. Ainsi dans le cas où l'utilisateur rentre une valeur du type rotate(45°), il ne souhaite pas qu'elle soit complexifiée en produit d'étirements et d'inclinaisons.

Pour éviter ce problème, on commence par rajouter quelques conditions pour déterminer si on peut mettre la matrice de l'application linéaire sous forme d'une rotation. Si la matrice est de la forme $\left(\begin{array}{cc}a& -b\\ b& a\end{array}\right)\ne 0$, alors la méthode usuelle consiste à prendre un facteur d'échelle $k=\sqrt{a^2+b^2}$ et pour angle $\theta =\mathrm{signe}\left(b\right)\arccos \frac{a}{k}$, la matrice devient $R\left(\theta \right)S\left(k,k\right)$ . Plus généralement, on peut aussi se ramener à la forme précédente en essayant de multiplier les coefficients grâce à une matrice d'étirement. Ainsi si $ab+cd=0$ et $b,c\ne 0$ alors $\left(\begin{array}{cc}a& c\\ b& d\end{array}\right)=S(-\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$b$}\right.,\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$c$}\right.)\left(\begin{array}{cc}-ab& -bc\\ bc& cd\end{array}\right)$ et la première matrice est de la forme désirée. On a un cas similaire pour $a,d\ne 0$. En multipliant à droite par une matrice d'étirement on obtient deux cas supplémentaires (la condition devient $ac+bd=0$).

Ces cas particuliers ainsi que le troisième cas de la décomposition générale ($a=d=0$) et le cas d'un simple étirement ($b=c=0$) conduisent donc à des attributs de la forme "translate scale", "translate scale rotate", "translate rotate scale". Notons que quitte à changer les coefficients de la translations, on peut permuter translation et étirement, puisque "translate(tx,ty) scale(sx,sy)" est équivalent à "scale(sx,sy) translate(tx/sx,ty/sy)". L'intérêt d'une telle permutation est donnée par la proposition suivante :

3.4.1.5. Proposition

Tout attribut transform de la forme "translate(tx,ty) rotate(θ)" peut être simplifiée en un simple "translate(tx,ty)" ou un "rotate(θ,cx,cy)".

Démonstration :

La matrice de "rotate(θ,cx,cy)" est $\left(\begin{array}{ccc}\cos \left(\theta \right)& -\sin \left(\theta \right)& \mathrm{cx}\left(1-\cos \left(\theta \right)\right)+\mathrm{cy}\sin \left(\theta \right)\\ \sin \left(\theta \right)& \cos \left(\theta \right)& -\mathrm{cx}\sin \left(\theta \right)+\mathrm{cy}\left(1-\cos \left(\theta \right)\right)\\ 0& 0& 1\end{array}\right)$

et celle de "translate(tx,ty) rotate(θ)" est $\left(\begin{array}{ccc}\cos \left(\theta \right)& -\sin \left(\theta \right)& \mathrm{tx}\\ \sin \left(\theta \right)& \cos \left(\theta \right)& \mathrm{ty}\\ 0& 0& 1\end{array}\right)$. Pour réduire cette dernière en une rotation avec centre, il suffit donc de trouver $\mathrm{cx},\mathrm{cy}$ satisfaisant :

$\left(\begin{array}{cc}1-c& s\\ -s& 1-c\end{array}\right)\left(\begin{array}{c}\mathrm{cx}\\ \mathrm{cy}\end{array}\right)=\left(\begin{array}{c}\mathrm{tx}\\ \mathrm{ty}\end{array}\right)$ en notant $c=\cos \left(\theta \right)$ et $s=\sin \left(\theta \right)$.

Le déterminant de ce sytème est ${\left(1-c\right)}^2+s^2=1-2c+c^2+s^2=2\left(1-c\right)$ qui est non nul si et seulement si $c\ne 1$. On trouve alors pour solution

$\left(\begin{array}{c}\mathrm{cx}\\ \mathrm{cy}\end{array}\right)=\frac{1}{2\left(1-c\right)}\left(\begin{array}{cc}1-c& -s\\ s& 1-c\end{array}\right)\left(\begin{array}{c}\mathrm{tx}\\ \mathrm{ty}\end{array}\right)=\frac{1}{2}\left(\begin{array}{c}\mathrm{tx}-k\mathrm{ty}\\ k\mathrm{tx}+\mathrm{ty}\end{array}\right)$ avec $k=\frac{s}{1-c}=\frac{\sin \left(\theta \right)}{1-\cos \left(\theta \right)}$.

Enfin, si $c=1$ on a en fait une rotation d'angle $\theta =0°$ et la transformation est en réalité une pure translation. □

A titre d'exemple, le cas $a=d=0$ qui se réduisait à "translate(e,f) rotate(90°) scale(b, -c)" devient maintenant "rotate(90°, [e-f]/2, [e+f]/2) scale(b, -c)". En reprenant toutes les idées énoncées précédemment, on arrive finalement à l'algorithme suivant :

3.4.1.6. Algorithme

DecomposerMatrice (matrix(a, b, c, d, e, f))

<< Complexité en O(1) >>

  resultat := ListeVide

  Si b = c = 0 
      
    * Cas I *

    Ajouter(resultat, translate(e, f))
    Ajouter(resultat, scale(a, d))

    SinonSi a = d = 0

      * Cas II *

      Ajouter(resultat, rotate(90°, [e-f]/2, [e+f]/2))
      Ajouter(resultat, scale(b, -c))

    SinonSi a = d et b = -c

      * Cas III *

      s := racine(a*a + b*b);
      θ := signe(b)*arccos(a/s);

      Si θ = 0
        Ajouter(resultat, translate(e, f))
      Sinon
        k := sin(θ)/(1 - cos(θ))
        Ajouter(resultat, rotate(θ°, [e - k*f]/2, [k*e + f]/2))
      FinSi
      
      Ajouter(resultat, scale(s, s))
      
    SinonSi ab + cd = 0 et (b, c ≠ 0 ou a, d ≠ 0)
      
      * Cas IV *

      Si b, c ≠ 0
        a := -a*b
        d := b*c
        s := racine(a*a + d*d)
        sx := -s/b
        sy := s/c
        θ := signe(d)*arccos(a/s)
      Sinon
        b := a*d
        c := c*d
        s := racine(b*b + c*c)
        sx := s/d
        sy := s/a
        θ := signe(c)*arccos(b/s)
      FinSi

      Si θ = 0
        Ajouter(resultat, translate(e, f))
        Ajouter(resultat, scale(sx, sy))
      Sinon
        Ajouter(resultat, scale(sx, sy))
        e := e/sx
        f := f/sy
        k := sin(θ)/(1 - cos(θ))
        Ajouter(resultat, rotate(θ°, [e - k*f]/2, [k*e + f]/2))
      FinSi

    SinonSi ac + bd = 0 et (b, c ≠ 0 ou a, d ≠ 0)

      * Cas V *

      Si b, c ≠ 0
        a := a*c;
        d := b*c;
        s := racine(a*a + d*d);
        sx := s/c;
        sy := -s/b;
        θ := signe(d)*arccos(a/s);
      Sinon
        b := a*d;
        c := a*c;
        s := racine(b*b + c*c);
        sx := s/d;
        sy := s/a;
        θ := signe(c)*arccos(b/s);
      FinSi

      Si θ = 0
        Ajouter(resultat, translate(e, f))
      Sinon
        Ajouter(resultat, scale(sx, sy))
        k := sin(θ)/(1 - cos(θ))
        Ajouter(resultat, rotate(θ°, [e - k*f]/2, [k*e + f]/2))
      FinSi

      Ajouter(resultat, scale(sx, sy))

    SinonSi a ≠ 0
      
      * Cas VI *

      θ1 := arctan(b/a)
      θ2 := arctan(c/a)
      d := d - b*c/a

      Ajouter(resultat, skewY(θ1°))
      Ajouter(resultat, scale(a, d))
      Ajouter(resultat, skewX(θ2°))
      
    SinonSi d ≠ 0

      * Cas VII *

      θ1 := arctan(c/d)
      θ2 := arctan(b/d)
      a := a - b*c/d

      Ajouter(resultat, skewX(θ1°))
      Ajouter(resultat, scale(a, d))
      Ajouter(resultat, skewY(θ2°))

    FinSi

  Renvoyer(resultat)

FinDecomposerMatrice

Il est intéressant de noter que si l'utilisateur ne déforme pas les objets, c'est-à-dire n'applique que des translations, rotations et des étirements conservant les proportions, alors on reste dans les décompositions n'utilisant pas d'inclinaison (i.e autres que VI et VII) de l'algorithme. En effet, une telle composition de transformations donne une similitude dont on sait qu'elle peut s'écrire sous forme "réduite". La proposition suivante montre que l'algorithme fournit effectivement cette écriture :

3.4.1.7. Proposition

L'algorithme 3.4.1.6 décompose toute similitude en un attribut utilisant des translate, rotate et scale.

Démonstration :

Soit $A=\left(\begin{array}{cc}a& c\\ b& d\end{array}\right)$ la partie linéaire de la similitude, notons $\Delta =ad-bc$ le déterminant de $A$ et $k$ le rapport de similitude, c'est-à-dire tel que pour tout vecteur $v$, $\parallel Av\parallel =k\parallel v\parallel$. Si $A$ est non inversible, alors en prenant $v\in \mathrm{Ker}A$ non nul, on obtient $k=0$. Réciproquement, si $k=0$, alors clairement $A=0$ est non inversible. On s'intéresse donc au cas où $A$ est inversible (i.e $k,\Delta \ne 0$), on a alors$A^{-1}=\frac{1}{\Delta }\left(\begin{array}{cc}d& -c\\ -b& a\end{array}\right)$ et pour tout vecteur $v$, $\parallel A^{-1}v\parallel =\frac{1}{k}\parallel v\parallel$.

Comme $A\left(\begin{array}{c}1\\ 0\end{array}\right)=\left(\begin{array}{c}a\\ b\end{array}\right)$ et $A\left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}c\\ d\end{array}\right)$ on obtient en passant au carré des normes : $k^2=a^2+b^2=c^2+d^2$.

De même, de $A^{-1}\left(\begin{array}{c}1\\ 0\end{array}\right)=\frac{1}{\Delta }\left(\begin{array}{c}d\\ -b\end{array}\right)$ et $A^{-1}\left(\begin{array}{c}0\\ 1\end{array}\right)=\frac{1}{\Delta }\left(\begin{array}{c}-c\\ a\end{array}\right)$ on déduit $\frac{{\Delta }^2}{k^2}=b^2+d^2=c^2+a^2$

En effectuant des combinaisons linéaires judicieuses de ces deux égalités, on obtient finalement $c^2=b^2$ et $d^2=a^2$ c'est-à-dire $c=\pm b$ et $d=\pm a$. De plus ces égalités donnent aussi $k=\sqrt{\mid \Delta \mid }$. Les différents cas possibles sont :

Le troisième cas, correspond au cas III de l'algorithme. Dans le deuxième cas, sachant que le déterminant n'est pas nul, on a soit $a$ soit $b$ non nul (et donc $a,d\ne 0$ ou $b,d\ne 0$) qui est le cas IV (et V) de l'algorithme. Pour les cas restants, on sait que $A\left(\begin{array}{c}b\\ d\end{array}\right)=\left(\begin{array}{c}ab+cd\\ b^2+d^2\end{array}\right)$ et à nouveau en passant au carré des normes, $(b^2+d^2)k^2={\left(ab+cd\right)}^2+{\left(b^2+d^2\right)}^2$. Avec les données du tableau, on trouve $(a^2+b^2)\mid a^2-b^2\mid =(4a^2{b}^2+{(a^2+b^2)}^2)$. Selon le signe de $a^2-b^2$ cette égalité se simplifie en :

• $2a^2(a^2+3b^2)=0$ et comme $a$ et $b$ ne sont pas simultanément nuls (ou sinon on aurait $A=0$) on obtient $a=0$. La matrice est alors de la forme $\left(\begin{array}{cc}0& \pm b\\ b& 0\end{array}\right)$ qui est le cas II de l'algorithme.
• $2b^2(3a^2+b^2)=0$ et donc $b=0$. On obtient donc une matrice d'étirement $\left(\begin{array}{cc}a& 0\\ 0& \pm a\end{array}\right)$, qui est le cas I de l'algorithme.

□

Remarquons que les transformations décomposées par l'algorithme sans utiliser d'inclinaisons ne sont pas restreintes aux similitudes. Il suffit par exemple de considérer une transformation de composante linéaire $A=\left(\begin{array}{cc}-2& 1/2\\ 1& 4\end{array}\right)$ (ce n'est pas une similitude puisque $\parallel A{e}_1\parallel =\sqrt{5}\ne \frac{\sqrt{5}\sqrt{13}}{2}=\parallel A{e}_2\parallel$ alors que les vecteurs $e_1$ et $e_2$ de la base canonique ont même norme). La question de savoir quelles transformations sont décomposables sans inclinaison est ouverte, mais le présent algorithme est pour l'instant largement satisfaisant.

Pour conclure, la décomposition peut être désactivée via la variable d'envionnement ENABLE_DECOMPOSE_TRANSFORM. Dans ce cas, Amaya génère un attribut transform="matrice(a, b, c, d, e, f)".

3.4.2. Transformations simples sur un objet

Nous allons maintenant voir des transformations simples que l'utilisateur peut effectuer en lançant une commande. La situation est la suivante : l'utilisateur veut transformer un objet SVG, fils direct d'un <svg/>. En rouge, on a dessiné la boite englobante qui nous sert de référence.

Unecourbequelconqueencadréparuneboiteenpositionx,yetdedimensionslargeurethauteur. élément SVG boite englobante x,y largeur hauteur canevas <svg/>

Les transformations de bases décrites dans cette section sont :

1. La symétrie horizontale :

2. La symétrie verticale :

3. Le pivotement de 90° (dans le sens horaire ou anti-horaire)

Pour les symétries, l'algorithme consiste à se placer dans le repère du centre $(c_x,c_y)$ de la boite englobante par des translations avant d'appliquer une symétrie selon l'axe des abscisses ou des ordonnées dont la matrice est respectivement $\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right)$ et $\left(\begin{array}{cc}-1& 0\\ 0& 1\end{array}\right)$.

3.4.2.1. Algorithme

AppliquerSymetrie (element, est_horizontale)

<< Complexité en O(1) >>

ObtenirBoiteEnglobante(&x, &y, &largeur, &hauteur)

cx := x + largeur / 2
cy := y + hauteur / 2
AppliquerTransformation(element, translate(-cx, -cy))

Si est_horizontale
  AppliquerTransformation(element, matrix(1, 0, 0, -1, 0, 0))
Sinon
  AppliquerTransformation(element, matrix(-1, 0, 0, 1, 0, 0))
FinSi

AppliquerTransformation(element, translate(+cx, +cy))
      
FinAppliquerSymetriee

L'algorithme pour les pivotements de 90° est identique, sauf que l'on applique la transformation rotate(±90°, cx, cy). On conçoit aussi facilement une fonction DeplacerObjet (element, x, y) qui nous servira pour les alignements et les distributions.

Pour conclure, si plusieurs objets ont été sélectionnés avant la commande chaque objet est transformé individuellement. Les algorithmes décrits dans cette section s'adapte facilement en ajoutant une boucle.

3.4.3. Transformations simples sur plusieurs objets

On décrit dans cette section des transformations se réalisant sur une sélection de plusieurs objets. Comme précédemment, chaque objet à sa propre boite englobante. En prenant le min et max selon chaque direction on obtient facilement une boite englobante de l'ensemble des objets.

Les deux types d'opérations considérés sont :

1. Les alignements. Ici, l'alignement se fait selon le bord supérieur, indiqué par une ligne violette. L'alignement peut aussi se réaliser selon les bords inférieur, gauche, droit et les axes centraux horizontal et vertical. Dans le cas particulier où un seul objet est sélectionné, l'alignement se fait par rapport au canevas <svg/>.

2. Les distributions. Ici, on distribue équitablement les objets, en prenant leur axe vertical comme référence. Comme pour les alignments, il existe en tout 6 distributions possibles selon les différents bords/axes. A ces types de distributions, on ajoute deux autres qui distribue équitablement l'espacement entre les bords des objets.

L'algorithme pour les alignements est le suivant :

3.4.3.1. Algorithme

AlignerObjets (canvas, objets[], nombre, type)

<< Complexité en O(nombre) >>

Si nombre = 1
      
  ObtenirTaille(canvas, &xmax, &ymax)
  ObtenirBoiteEnglobante(element, &x, &y, &largeur, &hauteur)

  ChoisirSelon type

    Cas Gauche
      DeplacerObjet(objets[0], 0, y)
    FinCas

    Cas Centre
      DeplacerObjet(objets[0], (xmax-largeur)/2, y)
    FinCas

    Cas Droite
      DeplacerObjet(objets[0], xmax-largeur, y)
    FinCas

    Cas Haut
      DeplacerObjet(objets[0], x, 0)
    FinCas

    Cas Milieu
      DeplacerObjet(objets[0], x, (ymax-hauteur)/2)
    FinCas

    Cas Bas
      DeplacerObjet(objets[0], x, ymax-hauteur)
    FinCas
      
  FinChoisirSelon

  SinonSi nombre > 1
      
    ObtenirBoiteEnglobante(objets[0], &x, &y, &largeur, &hauteur)
    xmin := x
    xmax := x + largeur
    ymin := y
    ymax := y + hauteur
    Pour i de 1 à nombre - 1
      ObtenirBoiteEnglobante(objets[i], &x, &y, &largeur, &hauteur)

      Si x < xmin 
        xmin := x
      FinSi

      Si y < ymin 
        ymin := y
      FinSi

      Si x + largeur > xmax
        xmax := x + largeur
      FinSi

      Si y + hauteur > ymax
        ymax := y + hauteur
      FinSi

    FinPour
      
    xcentre := (xmin + xmax)/2
    ycentre := (ymin + ymax)/2

    Pour i de 1 à nombre - 1

      ObtenirBoiteEnglobante(objets[i], &x, &y, &largeur, &hauteur)

      ChoisirSelon type

      Cas Gauche
        DeplacerObjet(objets[i], xmin, y)
      FinCas

      Cas Centre
        DeplacerObjet(objets[i], xcentre - largeur/2, y)
      FinCas

      CasDroite
        DeplacerObjet(objets[i], xmax - largeur, y)
      FinCas

      Cas Haut
        DeplacerObjet(objets[i], x, ymin)
      FinCas

      Cas Milieu
        DeplacerObjet(objets[i], x, ycentre - hauteur/2)
      FinCas

      Cas Bas
        DeplacerObjet(objets[i], x, ymax - hauteur)
      FinCas
      
    FinChoisirSelon
      
  FinPour
      
FinSi

FinAlignerObjets

L'idée est la même pour les distributions. On ignore le cas où le nombre d'objets nombre est strictement inférieur à 3, qui ne change rien à la distribution des objets.

Pour les distributions selon les bords/axes, il faut aussi prendre garde à l'ordre des objets (de gauche à droite et de haut en bas) qui doit être conservé. On commence donc par calculer les coordonnées caractéristiques position[i] pour chaque objet: abcisse gauche/centre/droite ou ordonnée haut/milieu/bas selon le type de distribution attendue. On trie ensuite les objets dans l'ordre croissant des valeurs de position[i].

La nouvelle position du i-ème objet est alors donnée par la formule : $\mathrm{nouvelle}\_\mathrm{position}=\mathrm{position}\left[0\right]+i\times \mathrm{ecart}$ avec un pas entre chaque position successive égal à $\mathrm{ecart}=\frac{\mathrm{position}[n-1]-\mathrm{position}\left[0\right]}{n-1}$ ($n$ est le nombre d'objets).

Pour les distributions selon les espacements, il n'y a a priori pas d'ordre naturel sur les objets. Comme généralement l'utilisateur applique une telle opération sur des objets qui ne se chevauchent pas (i.e. les écarts $e_i$ définis plus loin sont positifs), les ordres utilisés précédemment sont équivalents et on peut choisir un ordre arbitraire par exemple selon les axes centraux. Étudions le problème dans le cas horizontal, le cas vertical en découlant. Pour chaque objet $i\in [0,n-1]$, $g_i,d_i,l_i$ représentent respectivement les abscisses des bords gauche, droits et la longueur de l'objet :

Schéma de positionnementdes boites englobantes $g_i$ foreignObject not supported $d_i$ foreignObject not supported $l_i$ foreignObject not supported $g_{i+1}$ foreignObject not supported $d_{i+1}$ foreignObject not supported $l_{i+1}$ foreignObject not supported $e_i$ foreignObject not supported

L'espacement entre deux objets successifs est donné par $e_i=g_{i+1}-d_i$. On utilise les même notations avec des primes pour les valeurs après transformation. Les conditions désirées sont :

1. Les objets gardent la même longueur : $l_i\text{'}=l_i$
2. Les bords extrèmes sont inchangés : $g_0\text{'}=g_0$ et $d_{n-1}\text{'}=d_{n-1}$.
3. L'espace entre chaque objet est constant : $e=e_i\text{'}=g_{i+1}\text{'}-d_i\text{'}$

La troisième égalité s'écrit $e=g_{i+1}\text{'}-g_i\text{'}-l_i\text{'}=g_{i+1}\text{'}-g_i\text{'}-l_i$ ce qui donne en sommant de 0 à $n-2$ :

$\left(n-1\right)e=g_{n+1}\text{'}-g_0\text{'}-\sum _{i=0}^{n-2}{l}_i=d_{n-1}\text{'}-l_{n-1}\text{'}-g_0\text{'}-\sum _{i=0}^{n-2}{l}_i=d_{n-1}-g_0-\sum _{i=0}^{n-1}{l}_i$ et finalement :

$e=\frac{d_{n-1}-g_0-\sum _{i=0}^{n-1}{l}_i}{n-1}$

L'algorithme consite donc à calculer l'espacement $e$ à partir des bords extrêmes et des longueurs des boites, ce qui se fait en une boucle. Ensuite, on calcul récursivement les nouvelles positions gauches, via la relation :

$\{\begin{array}{c}{g}_0\text{'}=g_0\\ g_{i+1}\text{'}=g_i\text{'}+l_i+e\end{array}$

où encore $g_i\text{'}=g_0+\sum _{k=0}^{i-1}{l}_k+ie$. Cette dernière écriture permet de réutiliser l'algorithme des distributions par rapport au bord gauche/supérieur, en mettant à jour l'origine à chaque étape (ajout de $l_i$).

3.4.4. Transformations générales

On s'intéresse maintenant à des transformations plus générales nécessitant une interaction avec l'utilisateur : tourner (rotation d'angle quelconque), incliner (<skew*/>), redimensionner (<scale/>) et déplacer (<translate/>). A nouveau pour simplifier, ces opérations n'agissent que sur un objet à la fois. On pourrait les améliorer en passant au module de transformation une liste des objets à transformer et en y ajoutant des boucles for. Les commandes sont disponibles dans la palette SVG mais comme elles sont très utilisées on les retrouve aussi dans le menu contextuel accessible en effectuant un clic droit :

Le déplacement peut être effectué plus rapidement en faisant un glisser-déposer de l'objet SVG. Toutefois on conserve la commande spécifique qui est utile pour certains cas particuliers :

• Si l'objet est un <text/> ou un objet étranger, le mouvement glisser-déposer rentre en conflit avec la sélection.
• Lorsque l'objet à déplacer est difficilement sélectionnable en vue formattée (caché par d'autres, trop petit...).

Toutes les transformations sont effectuées en calculant la différence entre deux positions de souris (reportées dans le repère local) et non les positions effectives. Ainsi pour les rotations et translations il n'est pas utile de cliquer exactement sur l'objet. Pour les redimensionnement et inclinaison il faut par contre cliquer sur des flèches ou sinon l'interaction s'arrête. On peut quitter l'interaction à tout moment en effectuant un double-clic. Les modules se présentent ainsi :

• Déplacer : l'utilisateur fait un glisser déposer d'une position initiale à une position finale. L'objet suit le curseur de la souris. Si le module n'a pas été appelé par la commande des menus, l'utilisateur peut relacher la souris et redéplacer l'objet autant de fois qu'il le souhaite, sans quitter le module.
• Tourner : une croix indiquant le centre de rotation s'affiche au centre de la boite englobante de l'objet. L'utilisateur peut déplacer cette croix par un glisser-déposer. Si il effectue un glissement de souris autre part, l'objet tourne.
• Incliner : quatre flèches s'affichent le long des cotés de la boite englobante. Si l'utilisateur clique sur une flèche et maintient le bouton appuyé, il peut incliner l'objet dans la direction verticale ou horizontale selon la direction de la flèche sélectionnée.
• Redimensionner : 8 flèches de redimensionnement s'affichent autour de la boite englobante. Les flèches horizontales, verticales et diagonales permettent d'effectuer des redimensionnement selon ces directions. L'appui de la touche shift permet de conserver le rapport des dimensions de la boite englobante.

3.4.4.1. Algorithme

On note (x1, y1) et (x2, y2) les coordonnées entre deux mouvements successifs de souris. Certains cas sont similaires et ne seront donc pas tous détaillés. cx et cy sont les centres de la boite englobante ou de la rotation. haut, bas, gauche, droite les coordonnées de la boite englobante.

AppliquerTransformation (element, x1, y1, x2, y2, type)
      
 ChoisirSelon

   Cas Translation
     AppliquerTransformation(element, translation(x2 - x1, y2 - y1))
   FinCas

   Cas Rotation
    dx1 := x1 - cx
    dx2 := x2 - cx
    dy1 := y1 - cy
    dy2 := y2 - cy
    d := Racine((dx1^2 + dy1^2)*(dx2^2 + dy2^2));
      
    Si d > 0

      det := dx1*dy2 - dy1*dx2;
      theta := Signe(det)*arccos((dx1*dx2 + dy1*dy2)/d)
      AppliquerTransformation(element, translation(-cx, -cy))
      AppliquerTransformation(element,
                              matrice(cos(theta), sin(theta),
                                      -sin(theta), cos(theta),
                                      0, 0))
      AppliquerTransformation(element, translation(+cx, +cy))

    FinSi

  FinCas

  Cas InclinerSelonAxeDesX_FlecheDuHaut

    AppliquerTransformation(element, translation(-cx, -cy))
      
    x1 := x1 - cx
    x2 := x2 - cx

    y1 := Haut - cy
    y1 := y2

    AppliquerTransformation(element, matrice(1, 0,
                                             θ, 1,
                                             0, 0))

    AppliquerTransformation(element, translation(+cx, +cy))

  FinCas

  Cas RedimensionnerVertical_FlecheDuHaut

    y1 := y1 - Bas
    y2 := y2 - Bas

    Si y1, y2 ≠ 0

      AppliquerTransformation(element, translation(-cx, -Bas))
      sy := y2/y1

      Si GarderProportion
        sx := sy
      Sinon
        sx := 1
      FinSi

    AppliquerTransformation(element, matrice(sx, 0,
                                             0, sy,
                                             0, 0))
    AppliquerTransformation(element, translation(+cx, +Bas))

    FinSi
      
  FinCas

  Cas RedimensionnerDiagonal_FlecheEnHautAGauche

    x1 := x1 - droite
    x2 := x2 - droite
    y1 := y1 - bas
    y2 := y2 - bas

    Si x1, x2, y1, y2 ≠ 0

      AppliquerTransformation(element, translation(-Droite, -Bas))
      sx := x2/x1
      sy := y2/y1

      Si GarderProportion
        Si |sx| < |sy|
          sy := Signe(sy)*|sx|  
        Sinon
          sx := Signe(sx)*|sy|
        FinSi
      FinSi

      AppliquerTransformation(element, matrice(sx, 0,
                                               0, sy,
                                               0, 0))
      AppliquerTransformation(element, translation(+Droite, +Bas))

    FinSi

  FinCas

  [...]

  FinChoisirSelon

FinAppliquerTranformation

3.5. Édition du style

3.5.1. Le panneau de style

Lorsque l'utilisateur sélectionne un élément SVG, des commandes spécifiques apparaissent dans le panneau de style. Seuls des attributs simples qui peuvent être rendus par Amaya sont disponibles. Ils concernent la couleur, l'opacité et l'épaisseur des traits :

Le premier champs donne le pourcentage d'opacité de l'élément. On a ensuite deux catégories de style qui s'appliquent au remplissage et au contour. Ceux-ci peuvent être désactivés (la valeur de la couleur est alors none) ou activés (la valeur de la couleur prend celle affichée dans le panneau). Les remplissages et contour ont chacun leur valeur d'opacité qui s'ajoute à l'opacité globale. Enfin on peut préciser une épaisseur pour le contour.

Lorsque l'utilisateur souhaite modifier le style d'un objet, il s'attend à pouvoir récupérer les valeurs courantes. Ainsi, chaque fois qu'un objet SVG est sélectionné, son style de présentation est chargé dans la palette.

Tous les styles sont appliqués dans un attribut style (pour lequel il existait déjà des fonctions de manipulation) et non les attributs de présentation. Le passage entre les deux syntaxes n'a pas été pris en compte. Cependant si un objet comporte des attributs de présentation SVG alors son style peut tout de même être chargé dans la palette. En le modifiant, on regénère tout l'attribut style dont les valeurs sont prioritaires sur les attributs de présentation déjà existantes (voir section 6.4 de [14]). Ainsi le résutat visuel n'est pas choquant pour l'utilisateur même si il y a des informations redondantes dans le code source.

3.5.2. Style des objets créés

Les éléments SVG sont par défaut sans bordure et remplis en noir. Lors de la création d'un nouvel objet, il convient de le modifier pour le rendre plus agréable. Le panneau de style prenant les valeurs du dernier objet sélectionné, si on utilise ces valeurs pour les nouveaux éléments créés alors on peut tracer plusieurs éléments avec le même style. Cette méthode pose toutefois quelques problèmes :

1. Certains objets n'ont pas de style précisé. Si on les sélectionnent, les valeurs par défaut du style SVG seront intégrées dans la palette et les dessins suivants seront en noirs.
2. Si on souhaite créer un nouvel objet, on ne peut pas sélectionner son style dans la palette avant sa création ou sinon on modifie celui de l'objet couramment sélectionné.
3. Certaines combinaisons de style permettent de dessiner des éléments invisibles.

Par conséquent on préfère donner un style par défaut à chaque création et on laisse ensuite le soin à l'utilisateur de modifier ce style. Pour la plupart des objets, ce style est un remplissage bleu et une bordure noir. Certains n'ont pas de remplissage par exemple les courbes ouvertes ou encore les composants de schémas où la mise en couleur n'est pas pertinente (symbole de circuit électrique par exemple).

3.5.3. Héritage du style et composants prédéfinis

Lorsque l'on applique ou récupère le style d'un groupe on le fait comme tout élément SVG : on prend les valeurs de l'attribut style attaché au groupe. Un objet héritant les propriétés CSS de ses parents, la modification du style du groupe permet de modifier celui de ses descendants. Cela ne fonctionne pas si les descendants ont déjà eux-même un style appliqué : dans ce cas leur style local est prioritaire sur le style du groupe. Si on souhaite appliquer un style à plusieurs éléments il ne faut donc pas les grouper mais simplement les sélectionner. L'application du style sur un groupe est donc pour l'instant réservé à des utilisateurs avancés pour tirer profit des méthodes d'héritage.

L'héritage est utilisé pour permettre à l'utilisateur de styler les composants prédéfinis. Ces éléments ne possèdent pratiquement aucun style, de façon à ce qu'ils héritent le style du groupe. De plus les zones distinctes sont tracées avec plusieurs éléments pour que l'utilisateur puisse leur appliquer des styles différents. A titre d'exemple, un cube est dessiné avec 6 polygones représentant ses faces. Si on applique une couleur au groupe, elle sera directement appliquée à toutes les faces du cube. L'utilisateur peut aussi donner des couleurs pour chaque face puisqu'elles sont dessinées avec des éléments différents. Un autre exemple concerne les verreries de chimie qui peuvent contenir des liquides. Dans ce cas, le flacon a localement un remplissage none pour que la couleur ne s'applique qu'au liquide.

4. Conclusion

L'objectif du stage était de mettre en place la création et l'édition de formes élémentaires SVG dans Amaya ainsi que d'y ajouter des fonctionnalités comparables à ce que l'on trouve dans les autres éditeurs d'images vectorielles. A l'issue de ces trois mois de stage, la mission qui m'était attribuée a été remplie puisque les méthodes d'édition indispensables sont dorénavant intégrées. Certains modules pourront reservir pour d'autres fonctionnalités d'Amaya telle que l'édition des images mappées. L'outil est actuellement utilisable comme en témoigne les schémas que j'ai réalisé dans mon rapport. Il reste toutefois quelques bogues mineurs à corriger et des fonctionnalités dont on peut espérer qu'elles seront améliorées :

• terminer l'édition des parallélogrammes/trapèzes.
• proposer l'édition des "marqueurs" SVG et la gestion de connecteurs. Cela est particulièrement important pour les flèches dans les schémas.
• améliorer le parcours en profondeur grâce à une commande entrer/sortir du groupe.
• compléter le panneau de style.
• améliorer et compléter les commandes d'éditions des chemins ou de figures élémentaires.

En contrepartie, un certain nombre de fonctionnalités inédites et de résultats nouveaux ont été mis en place dans Amaya. Rappelons que les deux derniers algorithmes sont "en temps constant" et peuvent être désactivés en éditant un fichier de configuration.

• Amaya peut directement éditer du SVG à l'intérieur d'une page XHTML.
• Amaya peut insérer à une position précise des objets étrangers à l'intérieur d'une image SVG pour y éditer du XHTML ou du MathML. En particulier des formules mathématiques peuvent être utilisées dans les schémas.
• Amaya peut générer une description spatiale du contenu d'un élément SVG de façon à assister les auteurs pour la description des images et les encourager à produire des contenus accessibles.
• Amaya possède un algorithme de reconnaissance de formes, qui lui permet de manipuler les figures géométriques élémentaires absentes du SVG, sans avoir recours à une extension du langage.
• Amaya possède un algorithme de décomposition matricielle, qui permet de simplifier l'écriture de la matrice de transformation affine contenue dans l'attribut transform en un produit d'au plus trois transformations SVG simples. Si la transformation est une similitude, elle est décomposée en produit d'au plus un translate, rotate et d'un scale.

Ce stage a été pour moi l'occasion de travailler sur un gros projet, fruit de dix ans de travail de recherche pour Amaya et encore davantage pour Thot. J'ai ainsi pu mettre en pratique les connaissances que j'avais acquises au cours de ma première année à l'ENSIIE. Le sujet de stage permettait une liste de fonctionnalités d'édition assez vaste et j'ai pu constaster l'importance de la phase d'analyse en effectuant l'état de l'art et en dressant le plan de travail. J'ai pu expérimenter davantage le travail en équipe et l'usage d'un gestionnaire de conflit comme cvs. Le fait qu'Amaya soit un gros projet m'a montré l'importance des outils comme gdb pour ne pas être perdu dans le code. Amaya possède une liste de diffusion ouverte avec une communauté active d'utilisateurs. Les membres du W3C et du projet PALETTE sont aussi des testeurs potentiels. Cette confrontation avec des utilisateurs m'a sensibilisé aux problèmes d'utilisabilité du logiciel.

En ce qui concerne les connaissances théoriques, j'ai pu approfondir un peu plus ce que je savais du langage XML. La programmation des fonctionnalités classiques d'édition SVG m'ont permis d'étudier plus en profondeur ce langage. J'ai aussi pu travaillé sur des sujets de développement actuels comme le mélange de plusieurs grammaires XML, en prenant le cas de l'édition du SVG avec du MathML/XHTML. Enfin j'ai fait un usage important des mathématiques pour l'analyse et la programmation d'algorithmes non triviaux.

5. Annexes

5.1. Algorithmes et idées non retenus

5.1.1. Boite englobante d'une courbe de Bézier

Pour toutes les transformations opérées sur un objet SVG, il est nécessaire de déterminer une boite englobante. Lorsque j'ai réalisé les modules de transformations, j'ai remarqué que le calcul de cette boite n'était pas effectué pour les chemins et ai donc commencé à le programmer. Il s'est averé par la suite que ce calcul était déjà fait lors du tracé des chemins : les courbes sont approximées par des segments de droites et il suffit de prendre le min et le max (horizontaux et verticaux) des différents sommets. Néanmoins voici le travail que j'ai effectué pour l'encadrement de courbe de Bézier.

Les courbes de Bézier peuvent être décrites comme des courbes paramètrées par $t\in [0,1]$. Comme elle utilise la notion de barycentre, les coordonnées $\left(X,Y\right)$ des points de la courbe sont des fonctions de même forme. Donnons-les pour l'abscisse (les $x_i$ sont les abcisses des points de controle de la courbe) :

• $X\left(t\right)=x_0{\left(1-t\right)}^2+2x_1\left(1-t\right)t+x_2{t}^2$ pour les courbes de Bézier quadratiques.
• $X\left(t\right)=x_0{\left(1-t\right)}^3+3x_1{\left(1-t\right)}^{2}t+3x_2\left(1-t\right)t^2+{x_{3}t}^3$ pour les coubes de Bézier cubiques.

Les dérivées de ces fonctions sont $t\mapsto \left(2a_2-4a_1+a_0\right)t+(2a_1-2a_0)$ et $t\mapsto (3a_3-9a_2+9a_1-3a_0)t^2+(6a_2-12a_1+6a_0)t+(3a_1-3a_0)$comme on peut le vérifier avec le programme maxima suivant :

5.1.1.1. Programme Maxima

f2(t) := a2*t^2 + 2*a1*(1-t)*t + a0*(1-t)^2;
diff(f2(t), t);
partfrac(%, t);

f3(t) := a3*t^3+3*a2*(1-t)*t^2+3*a1*(1-t)^2*t+a0*(1-t)^3;
diff(f3(t), t);
partfrac(%, t);

Il ne reste ensuite plus qu'à regarder les min/max pour des valeurs de $t\in [0,1]$ qui annulent les dérivées. Ces valeurs sont faciles à trouver par un algorithme de résolution d'équation du second degré. La méthode est beaucoup plus économique que celle consistant à approximer la courbe par un polygone. Cependant en pratique l'approximation par un polygone se réalise très rapidement et est de toute façon indispensable au tracé de la courbe ou encore pour vérifier que l'utilisateur clique sur un point de la courbe.

5.1.2. Édition des arcs elliptiques

Dans cette partie, on reprend les notations de l'appendix F.6 "Elliptical arc implementation notes" de la spécification SVG [14]. Un chemin SVG, un arc est un fragment d'ellipse décrit par les paramètres suivants :

1. $(x_1,y_1)$et$(x_2,y_2)$ les coordonnées du point de départ et d'arrivée de l'arc
2. $r_X$ et $r_Y$ les demi-axes de l'ellipse contenant l'arc.
3. $\phi$ l'angle que fait l'axe des X de l'ellipse contenant l'arc avec celui du système de coordonnées courant.
4. $f_A$ et $f_S$ des booléens indiquant respectivement si on trace un grand arc (couvrant plus de 180° dans l'ellipse) et si l'ellipse est tracé dans le sens anti-horaire.

La spécification donne une paramétrisation alternative des coordonnées $\left(x,y\right)$ des points de l'arc pour en faciliter le tracé :

$\left(\begin{array}{c}x\\ y\end{array}\right)=\left(\begin{array}{cc}\cos \phi & -\sin \phi \\ \sin \phi & \cos \phi \end{array}\right)\left(\begin{array}{c}{r}_X\cos \theta \\ r_y\sin \theta \end{array}\right)+\left(\begin{array}{c}{c}_X\\ c_Y\end{array}\right)$ où θ varie entre deux angles ${\theta }_1$ et ${\theta }_2$ et $(c_X,c_Y)$ est le centre de l'ellipse.

Lorsque l'utilisateur édite le chemin en déplaçant le point $(x_2,y_2)$ en $(x_3,y_3)$ on souhaite mettre à jour les paramètres de façon à conserver une forme d'arc similaire. Les angles de départ et d'arrivée ${\theta }_1$ et ${\theta }_2$ sont donc inchangés (les booléens $f_A$ et $f_S$ aussi). Notons $p_i=\left(\begin{array}{c}{x}_i\\ y_i\end{array}\right)$ et supposons que $p_1\ne p_2$ et $p_1\ne p_3$. On agrandit l'ellipse par le rapport $k=\frac{\parallel p_3-p_1\parallel }{\parallel p_2-p_1\parallel }$ (qui est bien défini et non nul par les hypothèses précédentes), ce qui revient à multiplier les demi-axes $r_X$ et $r_Y$ par ce coefficient. Il reste donc à trouver la bonne orientation $\psi$ de l'ellipse. On note $(c_x\text{'},c_Y\text{'})$ les nouvelles coordonnées du centre de l'ellipse recherchée.

5.1.2.1. Proposition

Il existe au plus un angle ψ (modulo $2\pi$) satisfaisant les conditions :

1. $\left(\begin{array}{c}{x}_1\\ y_1\end{array}\right)=\left(\begin{array}{cc}\cos \phi & -\sin \phi \\ \sin \phi & \cos \phi \end{array}\right)\left(\begin{array}{c}{r}_X\cos {\theta }_1\\ r_y\sin {\theta }_1\end{array}\right)+\left(\begin{array}{c}{c}_X\\ c_Y\end{array}\right)$
2. $\left(\begin{array}{c}{x}_2\\ y_2\end{array}\right)=\left(\begin{array}{cc}\cos \phi & -\sin \phi \\ \sin \phi & \cos \phi \end{array}\right)\left(\begin{array}{c}{r}_X\cos {\theta }_2\\ r_y\sin {\theta }_2\end{array}\right)+\left(\begin{array}{c}{c}_X\\ c_Y\end{array}\right)$
3. $\left(\begin{array}{c}{x}_1\\ y_1\end{array}\right)=\left(\begin{array}{cc}\cos \psi & -\sin \psi \\ \sin \psi & \cos \psi \end{array}\right)\left(\begin{array}{c}{kr}_X\cos {\theta }_1\\ {kr}_y\sin {\theta }_1\end{array}\right)+\left(\begin{array}{c}{c}_X\text{'}\\ c_Y\text{'}\end{array}\right)$
4. $\left(\begin{array}{c}{x}_3\\ y_3\end{array}\right)=\left(\begin{array}{cc}\cos \psi & -\sin \psi \\ \sin \psi & \cos \psi \end{array}\right)\left(\begin{array}{c}{kr}_X\cos {\theta }_2\\ {kr}_y\sin {\theta }_2\end{array}\right)+\left(\begin{array}{c}{c}_X\text{'}\\ c_Y\text{'}\end{array}\right)$

Démonstration :

On note $M_f=\left(\begin{array}{cc}\cos f& -\sin f\\ \sin f& \cos f\end{array}\right)$ et $R_i=\left(\begin{array}{c}{r}_X\cos {\theta }_i\\ r_Y\sin {\theta }_i\end{array}\right)$. Supposons qu'un tel angle $\psi$ existe et commençons par éliminer les centres des ellipses par soustraction : $p_2-p_1=M_{\phi }(R_2-R_1)$ et $p_3-p_1=M_{\psi }k(R_2-R_1)$, d'où $R_2-R_1=M_{-\phi }\left(p_2-p_1\right)=\frac{M_{-\psi }}{k}\left(p_3-p_1\right)$ et enfin $M_{\psi }k(p_2-p_1)=M_{\phi }(p_3-p_1)$.

On peut réécrire cette égalité de façon équivalente, en posant des coefficents $a,b,c,d$ qui conviennent : $\left(\begin{array}{cc}\cos \psi & -\sin \psi \\ \sin \psi & \cos \psi \end{array}\right)\left(\begin{array}{c}a\\ b\end{array}\right)=\left(\begin{array}{c}c\\ d\end{array}\right)$. On obtient alors une équation d'inconnues $x=\cos \psi$ et $y=\sin \psi$ : $\left(\begin{array}{cc}a& -b\\ b& a\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)=\left(\begin{array}{c}c\\ d\end{array}\right)$. Comme $k\left(p_2-p_1\right)$ est non nul par hypothèse, le déterminant du système $a^2+b^2$ est strictement positif et on obtient une solution $\left(x,y\right)$. L'angle $\psi$, s'il existe est donc entièrement déterminé par son cosinus $x$ et son sinus $y$. □

Remarquons que l'on peut expliciter $\left(x,y\right)$ à partir des données initiales ($x_1,x_2,y_1,y_2,r_X,r_Y$). Le programme Maxima suivant calcule la valeur de $x^2+y^2$ :

5.1.2.2. Programme Maxima

p1 :  matrix([x1], [y1]);
p2 :  matrix([x2], [y2]);
p3 :  matrix([x3], [y3]);

k : sqrt(((x1-x3)^2+(y1-y3)^2)/((x1-x2)^2+(y1-y2)^2));

M(f) := matrix(
cos(f),-sin(f)], 
sin(f),cos(f)]
);

a: (k*(p1-p2))[1][1];
b: (k*(p1-p2))[2][1];

Y: (M(f).(p1-p3));

A : matrix(
[a,-b], 
[b,a]
);

X : invert(A).Y;

x : X[1][1];
y : X[2][1];

trigsimp(radcan(x^2 + y^2));

Le programme trouve effectivement $x^2+y^2=1$ ce qui permet de toujours calculer une valeur $\psi$. Je n'ai pas vérifié la réciproque à savoir que l'angle $\psi$ trouvé permettait bien de tracer un fragment d'arc de $p_1$ à $p_3$ sous les conditions désirées. J'ai tenté d'introduire cette mise à jour dans mon module d'édition, mais le résultat n'est pas toujours satisfaisant et l'arc dégénère parfois (en ligne ou en point) sûrement à cause de l'accumulation des erreurs d'arrondis.

5.2. Travail externe à Amaya

Le travail que j'ai effectué dans Amaya m'a conduit à regarder d'autres projets utilisant SVG pour assurer la compatibilité des différents outils et leurs conformités vis-à-vis de la spécification.

5.2.1. Rayons incorrects dans les arcs elliptiques

Dans la description d'un arc elliptique entre deux points, il se peut que les rayons soient trop petits. L'appendix F.6.6 de [14] indique qu'il faut alors appliquer une homothétie sur l'arc pour que la jonction puisse se faire. Si un des rayons est nul, on transforme l'arc en ligne droite. A titre d'exemple, le fichier XML décrit trois demi-arcs de cercle : un bleu en haut, un noir au milieu que l'on transforme en ligne droite et enfin un rouge en bas que l'on ajuste à la bonne taille.

<?xml version="1.0" encoding="UTF-8"?>
<svg xmlns="http://www.w3.org/2000/svg" version="1.0" width="500" height="500"> 
  <title>Test F.6.6 - Correction of out-of-range radii</title>

    <!-- blue arc: rx = ry = 250. -->
    <path d="M 0,250 A 250,250 0 0 1 500,250" fill="none" stroke="blue"/>

    <!-- black arc: rx = ry = 0.
         It's actually a straight line from (0, 250) to (500, 250) 
     -->
    <path d="M 0,250 A 0,0 0 0 0 500,250" fill="none" stroke="black"/>

    <!-- red arc: rx = ry = 1.
         Arc is not large enough. Take rx = ry = 250    
     -->
    <path d="M 0,250 A 1,1 0 0 0 500,250" fill="none" stroke="red"/>
</svg>

Dans Amaya la correction des rayons était bien effectuée mais aucun tracé n'était réalisé si un des rayons était nul. De plus l'algorithme de tracé utilisait un arccosinus qui pouvait être indéfini : l'erreur de calcul avec les nombres flottants conduisait à des arguments légèrement inférieur à -1 ou supérieur à +1. Cela se traduisait dans le tracé par une ligne droite. Enfin, les rayons des arcs n'étaient pas agrandis avec le zoom. Des utilisateurs ont reporté ces problèmes sur la liste de diffusion d'Amaya, ce qui m'a amené à les corriger.

En réalisant des dessins SVG, j'avais aussi remarqué ce type d'erreurs dans le visionneur d'image de Gnome. Ainsi, dans le fichier XML ci-dessus, seul l'arc bleu est correctement affiché car aucune correction des rayons n'est effectuée. Le problème vient en réalité de Librsvg, une librairie utilisée dans d'autres projets. Grâce à l'expérience acquise avec Amaya, j'ai pu proposer un patch aux développeurs de Librsvg.

5.2.2. Extensions requises dans les objets étrangers

Les <foreignObject/> comportent un attribut requiredExtensions qui sert à indiquer les capacités necessaires pour afficher l'élément. J'ai néanmoins constaté un problème de compatibilité, du au fait que les spécifications ne précisent pas les valeurs de l'attribut requiredExtensions à utiliser avec le XHTML et le MathML. L'élément <svg/> dans le fichier XHTML ci-dessous contient ainsi un <foreignObject/> avec une fraction $\raisebox{1ex}{$a$}\!\left/ \!\raisebox{-1ex}{$b$}\right.$ écrite en MathML et un texte "a/b" en SVG. En théorie, l'URI MathML dans le requiredExtensions indique les capacités nécessaires pour afficher l'objet étranger. Si le navigateur ne les possède pas il affichera le texte alternatif.

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1 plus MathML 2.0 plus SVG 1.1//EN"
      "http://www.w3.org/2002/04/xhtml-math-svg/xhtml-math-svg.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta http-equiv="content-type"
  content="application/xhtml+xml; charset=UTF-8" />
  <title>Test requiredExtensions</title>
  <meta name="generator" content="Amaya, see http://www.w3.org/Amaya/" />
</head>

<body>

<svg:svg xmlns:svg="http://www.w3.org/2000/svg" width="120" height="120">
  <svg:switch>
    <svg:foreignObject width="120" height="120"
                   requiredExtensions="http://www.w3.org/1998/Math/MathML">

      <math xmlns="http://www.w3.org/1998/Math/MathML">
        <mfrac bevelled="true">
          <mi>a</mi>
          <mi>b</mi>
        </mfrac>
      </math>
    </svg:foreignObject>
    <svg:text>a/b</svg:text>
  </svg:switch>
</svg:svg>

</body>
</html>

Amaya génère et affiche correctement ce type de structure. Toutefois, Firefox n'affiche pas l'objet étranger si un attribut requiredExtensions lui est attaché, quelle que soit la valeur de l'attribut. Par conséquent dans l'exemple, il n'affichera pas le MathML même s'il en est capable !

J'ai reporté ce problème au groupe de travail SVG du W3C. Je leur ai proposé de préciser dans la spécification que les URI du MathML et du XHTML devaient être utilisés dans l'attribut requiredExtensions. J'ai aussi soumis un patch pour que Gecko reconnaisse ces valeurs.

5.3. Références

1. Aide à la création de graphiques structurés avec AMAYA

   Rapport de stage deuxième année ISIMA (2002) - Étienne Bonnet

2. Amaya (http://www.w3.org/Amaya/)

   W3C's Editor/Browser

3. An XHTML + MathML + SVG Profile
   (http://www.w3.org/TR/XHTMLplusMathMLplusSVG/)

   W3C Working Draft 9 August 2002 - 石川 雅康 (Ishikawa Masayasu).

4. Authoring Tool Accessibility Guidelines 1.0 (http://www.w3.org/TR/ATAG/)

   W3C Recommendation 3 February 2000

   Jutta Treviranus, Charles McCathieNevile, Ian Jacobs and Jan Richards

5. Bézier curve(http://en.wikipedia.org/wiki/Bézier_curve)

   Article Wikipedia

6. Dia (http://live.gnome.org/Dia)

   A diagram creation program

7. Editing SVG with other XML languages (http://www.svgopen.org/2002/papers/cheyrou__amaya/)

   Paper SVG.Open/Carto.net 2002, Zurich - Paul Cheyrou-Lagrèze

8. ePrep (http://www.eprep.org/)
9. Guidelines for Graphics in MathML 2
   (http://www.w3.org/Math/Documents/Notes/graphics.xml)

   W3C Note 01 July 2003

   Michael Kohlhase and David Carlisle

10. Inkscape (http://www.inkscape.org/)

    Open Source Scalable Vector Graphics Editor

11. Maxima (http://maxima.sourceforge.net/)

    A Computer Algebra System

12. Open Office (http://www.openoffice.org/)

    The free and open productivity suite

13. Palette (http://palette.ercim.org/)

    Pedagogically sustained Adaptive Learning through the Exploitation of Tacit and Explicit Knowledge

14. Scalable Vector Graphics (SVG) 1.1 Specification
    (http://www.w3.org/TR/SVG/)

    W3C Recommendation 14 January 2003

15. The W3C Markup Validation Service (http://validator.w3.org/)

Cette page est conforme aux normes du W3C - Auteur : Frédéric WANG - Dernière mise à jour : vendredi 12 septembre 2008