Objectif : réalisation d'une application de construction d'entrelacs celtes.

Les noeuds et entrelacs remontent à la civilisation celte qui, déjà au IV^e siècle avant notre ère, sculptait des motifs d'entrelacs sur ses menhirs dressés. Un entrelacs est composé de différents noeuds entrelacés. On réalise un noeud avec une corde que l'on emmêle et dont on soude les deux bouts ; on peut ensuite la déformer à loisir.

Pour représenter un entrelacs, on étale les cordes sur une surface plane en ne gardant que des croisements de deux cordes ou plus, et on dessine le tout en notant soigneusement à chaque croisement laquelle est au-dessus et laquelle est en dessous. Autrement dit, on réalise une projection régulière de celui-ci sur le plan. Le dessin est un graphe dont les sommets sont les points de croisement de quatre arêtes, où l'on indique l'information des dessus-dessous en arrêtant le trait qui passe en dessous, juste avant d'arriver au sommet. On peut enrichir la structure, épaissir le trait, orienter chaque noeud, ne pas tous les fermer et maintenir leur extrémité fixe (on parle alors d'enchevêtrement), ou encore attacher une couleur à chaque noeud ou à chaque croisement.

Pour visualiser la géométrie d'un entrelacs, on construit un graphe planaire à arêtes signées de la manière suivante. A noter que cette méthode permet seulement de construire des entrelacs de façon automatique et de ce fait est assez limitée. Etant par nature déterministe, elle doit être considérée comme une première approximation mais peut se révéler néanmoins plaisante à regarder lorsque le nombre de croisements est important, c'est à dire lorsque l'impression générale domine l'exécution proprement dite.

La première étape pour construire le graphe consiste à définir la taille du maillage qui servira de support au graphe. Cette grille doit obligatoirement comporter un nombre pair de "cases" dans les deux directions (elle doit donc être de dimension 2m x 2n). Les noeuds du graphe sont ensuite disposés sur ce maillage aux coordonnées x et y telles que la somme x+y = 1 mod 2.

La deuxième étape consiste à marquer les noeuds externes comme infranchissables a priori. Graphiquement, on représente de tels noeuds par un "mur". Ces murs ont pour centre un noeud et peuvent être horizontaux ou verticaux.

Troisième étape : on peut définir d'autres noeuds (internes) de la même façon. Ces séparations vont déterminer la forme de l'entrelacs. Ainsi, une disposition symétrique de ces nouveaux murs donne généralement une forme agréable à l'oeil. Voici les règles de construction des séparations internes : celles-ci doivent être soit horizontales soit verticales et une seule séparation par noeud est autorisée.

La quatrième étape marque le début du traitement automatique par le programme. Elle consiste à parcourir l'ensemble des noeuds de la grille et à distinguer trois cas. Avant de les détailler, il faut définir la notion de voisin d'un noeud : ce sont les i-voisins c.à.d. les noeuds voisins immédiatement adjacents au noeud considéré sur les deux diagonales. Plus formellement, en supposant qu'un noeud a pour coordonnées (x1, y1), un "voisin" de ce noeud, de coordonnées (x2, y2), doit vérifier la relation : |x2 - x1| + |y2-y1| = 2.

• cas noeud non marqué/voisin non marqué : des segments diagonaux doivent relier les noeuds non marqués. Ceux-ci représentent les lieux de croisement de l'entrelacs (pour lesquels il faudra distinguer les dessus des dessous). Graphiquement, le segment diagonal ne doit pas relier complétement les deux noeuds, de façon à pouvoir construire par la suite les dessus-dessous.

  

• cas noeud non marqué/voisin marqué : pour ces couples de noeuds, on trace une portion de courbe, parallèle à un mur et qui doit se terminer au niveau du noeud non marqué, à la même distance que dans l'étape précédente. Ces portions de courbe sont en fait des courbes de Bézier, dont vous devrez déterminer les équations.

• cas noeud marqué/voisin marqué : construction des angles droits et des segments horizontaux et verticaux. Si les murs associés forment un angle droit, on construit un angle droit ; si par contre ils sont parallèles, on construit un segment horizontal ou vertical.

La dernière étape consiste à traiter les cas des "dessus-dessous". Pour ce faire, une stratégie simple, mais néanmoins justifiée par le type ce construction est d'alterner ceux-ci sur une droite horizontale. Ainsi, sur les colonnes d'indices impaires, on tracera un segment qui reliera la portion d'entrelacs inférieure-droite avec la portion d'entrelacs supérieure-gauche et sur les colonnes d'indices paires, on tracera un segment qui reliera la portion d'entrelacs inférieure-gauche avec la portion d'entrelacs supérieure-droite. La simplicité de la méthode permet malgré tout la construction d'un entrelacs du plus bel effet !

L'interface à réaliser doit comporter une barre de menus indépendante (comportant obligatoirement les menus "File", "Edit" et "Help") et une fenêtre graphique, elle aussi indépendante. Cette interface graphique doit permettre :

• de choisir la taille du graphe sur lequel on va travailler
• de construire le graphe par ajout, modification (i.e changement d'orientation) et suppression de "murs",
• de respecter l'ordre de construction (par exemple : inhibition du tracé de l'entrelacs tant que le graphe n'est pas défini),
• de sauvegarder, de charger et d'initialiser un graphe,
• d'associer des préférences à une session de travail (pas du maillage, épaisseur des traits, couleurs intérieures et extérieures de l'entrelacs, ...).

set com [open |./celte r+]

puts $com \"segment 10 10 10 110\"
flush $com