5.6.3 Calcul de la taille du pas et de la position initiale

Trop souvant en expérimentant nos L-systèmes, nous avons eu des problèmes avec la taille du dessin – soit qu’il dépassait le canevas et on ne le voyait qu’en partie, soit qu’il était trop petit et trop de détails étaient cachés. De même avec la position et l’orientation initiale de la tortue – le dessin pouvait être mal placé sur le canevas, ou il se dessinait seulement partialement ou pas du tout dans le canevas. Attaquons nous alors au problème de trouver automatiquement une bonne longueur pour l’avancement de la tortue ainsi qu’une bonne position et orientation de départ.

Comment faire? Puisque nous avons, avant de lancer le dessin, une description complète du dessin, sous forme d’une chaîne de caractères donnant toutes les instruction Logo pour le dessiner, nous pouvons faire précéder le dessin par une simulation de l’activité de dessiner la courbe. Cette simulation nous servira à

calculer le rectangle englobant le dessin, la boîte englobante, ou encore – en anglais cette fois – sa bounding box;
cette bounding box nous servira, à la fois pour déterminer la longueur du trait qu’un simple F doit dessiner, pour que la totalité du dessin tienne dans le canevas, et pour determiner la position initiale de la tortue.

Pour calculer la boîte englobante, nous allons commencer par un rectangle de taille très petite, disons de longueur 0 et de hauteur 0. Ce rectangle sera à coup sûr trop petit pour contenir un dessin quelconque! Ensuite, nous allons supposer que la tortue se trouve à la seule et unique position que ce rectangle permet: la position horizentale et verticale égale à 0. La tortue aura l’orientation initiale correspondant à l’angle 0.

Enfin, nous allons lire la chaîne de description de la courbe, caractère par caractère, et si nous rencontrons

: un caractère “+”, nous allons ajouter l’angle à l’orientation de la tortue.
: un caractère “-” nous allons soustraire l’angle de l’orientation de la tortue.
: un caractère F, la position horizontale de la tortue sera augmentée du sinus de l’angle et sa position verticale sera augmentée du cosinus de ce même angle.²⁵

FIG. 5.27:

Un rectangle de point d’origine α@β

Pour faciliter notre discours, supposons que notre boîte englobante soit définie avec un point d’origine aux coordonnées ((α,β) ) et le point diagonalement opposé, le point extent, aux coordonnées (γ, δ), comme montré dans la figure 5.27. Nous savons qu’au début α, β γ et δ valent tous 0.

Si, après un mouvement simulé de la tortue, sa nouvelle position horizontale est plus petite que α, la coordonnée horizontale de l’origine de notre rectangle englobant, alors cette coordonnée α prendra comme nouvelle valeur la position horizontale de la tortue. Si la position horizontale de la tortue est supérieure à γ, la coordonnée horizontale du point extent, alors γ prendra comme nouvelle valeur la position horizontale de la tortue. Nous procéderons d’une manière analogue pour les coordonnées verticales, β et δ.

Si ce processus se répète pour chacun des déplacements simulés de la tortue, il est évident que le rectangle sera à chaque instant exactement de la taille du dessin simulé jusqu’à cet instant. Bien entendu, à la fin de la simulation, le rectangle aura la taille du dessin final – si le dessin est dessiné avec une longueur de pas égal à 1.

Revenons alors vers l’implémentation: pour simuler les mouvements de la tortue nous avons besoin d’une tortue simulée. Celle-ci se caractérise par une position horizontale et verticale et une orientation. Nous avons le choix soit:

: de creer une nouvelle classe pour représenter une telle tortue avec ses trois variables d’instances, une pour chacune des charactéristiques,
: de mettre ces variables d’instances directement dans notre classe Lsystem.

Optons pour la deuxième solution et ajoutons trois variables d’instance supplémentaires à notre classe. Ce seront la variable sh et sv, pour garder la Situation Horizontale et V erticale de la tortue, ainsi que la variable sdir, donnant la direection de la tortue simulée. Il nous faut également une variable d’instance pour la boîte englobante, la bounding box, que nous appelerons box.

Ce qui nous donne la nouvelle définition de la classe Lsystem que voici:²⁶

DessinsLogo subclass: #Lsystem
   instanceVariableNames: ’niveau reglesDerivation
                           axiome angle longueur
                           box sh sv sdir’
   classVariableNames: ’’
   poolDictionaries: ’’
   category: ’Cours-Smalltalk’

Ensuite, nous avons besoin de calculer la boîte englobante. Ceci doit être fait après avoir généré la chaîne de caractères représentant la courbe et, naturellement, avant l’affichage de cette courbe. Ce qui, sous l’hypothèse que la méthode boiteMin: calcule la boîte englobante, nous oblige à modifier notre méthode lanceLsystem pour obtenir la version ci-dessous:

Lsystem>>lanceLsystem
   | tmp |
   self initImage.
   pen place: 200@390.
   tmp := self remplace: axiome times: niveau.
   self boiteMine: tmp.
   self automate: tmp.
   self afficheImage

Pour calculer la bounding box, donc pour simuler les mouvements de la tortue, nous pouvons prendre une approche analogue à celle que nous avons prise pour faire le dessin: un parcours de la représentation de la courbe et l’activation d’une méthode specifique pour chacun des caractères correspondant à une activité de la tortue. Il suffit d’adapter la méthode automate: à nos nouveaux besoins.

Dans l’adaptation ci-dessous nous supposons connues les trois méthodes avanceS, plusS et moinsS, qui correspondent, pour notre simulation, aux methodes avance, plus et moins de notre vraie tortue de dessin.

Voici alors notre méthode boiteMin::

Lsystem>>boiteMin: aString
   sh := sv := 0.
   sdir := 0.
   box := Rectangle origin: 0 @ 0 corner: 0 @ 0.
   aString
      do: [:ele | (’F+-’ indexOf: ele)
               > 0
            ifTrue: [self
                  perform: (#(#avanceS #plusS #moinsS)
                        at: (’F+-’ indexOf: ele))]]

Cette méthode se charge également de l’initialisation des variables d’instances nécessaires pour la simulation: les trois variables représentant l’état de la tortue simulée sont toutes initialisées à 0: la tortue commence au point 0@0 dans la direction 0. La variable box, représentant la boîte englobante, est initialisée à une instance de la classe Rectangle.²⁷ C’est justement le message origin:corner:, transmis à la classe Rectangle, qui crée cette instance. L’argument origin:, le point 0@0, correspond au point α@β de la figure 5.27, page 417. L’agument corner:, qui est ici également le point 0@0, correspond au point γ@δ de cette même figure. C’est donc bien un rectangle réduit à sa taille minimale.

Voici alors les trois méthodes de simulation des mouvements de la tortue.

Lsystem>>plusS
sdir := sdir + angle

Lsystem>>moinsS
sdir := sdir - angle

Lsystem>>avancefS
   sh := sh + sdir degreeSin.
   sv := sv + sdir degreeCos.
   self boxUpdate

Bien sûr, la simulation de + et - doit juste changer l’orientation de la tortue, par une simple addition ou soustraction. Par contre, la simulation de F doit à la fois calculer le déplacement, c’est le calcul de sinus et cosinus,²⁸ et mettre à jour les dimensions de notre boîte englobante, ce qui est fait par la méthode boxUpdate ci-dessous:

Lsystem>>boxUpdate
   sh < box origin x
      ifTrue: [box := box withLeft: sh].
   sh > box corner x
      ifTrue: [box := box withRight: sh].
   sv < box origin y
      ifTrue: [box := Rectangle origin: box origin x @ sv
                                corner: box corner].
   sv > box corner y
      ifTrue: [box := box withBottom: sv]

Sachant que la méthode withLeft: change, dans notre dessin d’un rectangle page 417, la valeur de

, que la méthode withRight: change

et que la méthode withBottom: change

, cette méthode boxUpdate se comporte exactement comme nous l’avons décrit ci-dessus, page 417.

Ayant maintenant la boîte englobante à notre disposition, nous pouvons – enfin – calculer la position initiale de la tortue ainsi que la longueur d’un pas (d’une instruction F) pour que le dessin tienne à l’intérieur de notre canevas et qu’il le remplisse le mieux possible. C’est ce calcul qui est fait par la méthode normalise ci-dessous:

Lsystem>>normalise
1    | stepX stepY step |
2    stepX := box corner x - box origin x.
3    stepY := box corner y - box origin y.
4    step := (form extent x - 20 / stepX)
5               min: (form extent y - 20 / stepY).
6    "rectangle:
7         origin: point de départ de la tortue
8         corner: longueur d’un pas @ 0"
9    ^ Rectangle origin: form extent x -
10                          (step *
11                            (box origin x + box corner x))
12                           / 2
13                     @ (form extent y +
14                          (step *
15                            (box origin y + box corner y))
16                          / 2)
17                corner: step @ 0

Commentaire:

Ligne 1: déclaration de trois variables temporaires: stepX contiendra la taille horizontale de la boîte englobante, stepY sa taille verticale et step contiendra la valeur que longueur devra prendre pour que le dessin de la courbe tienne dans le canevas de dessin. Supposons, comme tout le long de cette section, que notre boîte englobante ait l’origine au point α@β et que l’extension (l’extent) soit donnée par le point γ@δ. Notons que tel que nous avons écrit le programme jusqu’à maintenant, α ∈ [−∞,γ], β ∈ [−∞,δ], γ ∈ [0,+∞] et δ ∈ [0,+∞].

Ligne 2: stepX prendra comme valeur −α + δ, correspondant bien à la taille horizontale de la boîte englobante, à la distance de la coordonnée horizontale α et γ.

Ligne 3: stepY prendra comme valeur la taille verticale de la boîte englobante, donc la distance entre la coordonnée verticale de β et δ.

Lignes 4 et 5: Jusqu’à maintenant nous avons dans stepX et stepY la taille d’un F pour un canevas d’unité, un canevas dont la taille est déterminée de manière telle qu’un F correspond à un mouvement de la tortue de longueur 1. Nous devons adapter cette longueur à la taille de notre canevas réel, à la taille de notre form. C’est cela que nous faisons dans ces deux lignes, où nous calculons la taille d’un F dans le dessin couvrant le canevas, tout simplement en prenant la taille minimum de la taille verticale et horizontale.²⁹ Une telle taille est simplement le résultat de la division de la longueur (ou hauteur) du canevas réel (moins une petite constante pour éviter des débordements des bordures dûs aux erreurs d’arrondi) et de stepX (ou stepY).

FIG. 5.28:

Une courbe de Koch placée correctement sur le canevas

Lignes 9 à 17: Puisque nous voulons retourner deux valeurs: la taille du pas et la position initiale de la tortue, nous retournons ces valeurs dans la structure d’un rectangle qui a comme origine la position initiale de la tortue et comme extension la taille du pas.³⁰

step * (box origin x + box corner x) / 2

La coordonnée x de la position de la tortue sera alors le milieu (d’où la division par 2 dans l’expression ci-dessus) des coordonnées réelles (prenant en compte les valeurs négatives éventuelles) de α et β multiplié par la taille du pas, step. La coordonnée y est calculée de manière analogue avec les coordonnées β et δ.

Si nous faisons maintenant les adaptations pour prendre en compte ces calculs de placement et de pas dans le reste du programme, nous pouvons, sans nous préoccuper ni de la longueur, ni de la position initiale de la tortue, dessiner des systèmes de Lindenmayer dans des fenêtres de dimensions quelconques. La figure 5.28 montre une courbe de Koch quadratique dans un canevas rectangulaire automatiquement mise aux “bonnes” dimensions et placée correctement au milieu du rectangle.

Ces adaptations sont très simples. D’abord nous devons lancer le calcul de la boîte englobante, initialer la variable d’instance longueur et positionner la tortue aux coordonées initiales calculées. Ces activités doivent se situer entre la génération de la chaîne de caractères correspondant à la description de la courbe et son interprétation géométrique. Ceci nous donne la nouvelle version de la méthode lanceLsystem que voici:

Lsystem>>lanceLsystem
   | tmp tmp1 |
   self initImage.
   tmp := self remplace: axiome times: niveau.
   self boiteMin: tmp.
   tmp1 := self normalise.
   pen place: tmp1 origin.
   longueur := tmp1 corner x.
   self automate: tmp.
   self afficheImage

Ensuite, nous devons éliminer dans la méthode lsystem la lecture interactive d’une valeur pour la variable longueur: nous n’en avons plus besoin maintenant, elle est calculée automatiquement par normalise. Pour simplifier l’interaction avec l’utilisateur, changeons aussi la lecture des règles de dérivation de manière à l’initialiser avec une règle lors de la lecture de la première règle, et de l’initialiser à la chaîne vide lors des lectures suivantes. Ce qui nous donne:

Lsystem>>lSystem
   | tmp |
   axiome := FillInTheBlank request: ’axiome?’
                      initialAnswer: ’F’.
   reglesDerivation := Dictionary new.
   tmp := FillInTheBlank request: ’derivation 1 ?’
                   initialAnswer: ’F:F+F--F+F’.
   tmp := tmp copyWithout: $ .
   tmp = ’’
      ifFalse: [reglesDerivation
            at: (tmp at: 1)
            put: (tmp copyFrom: 3 to: tmp size).
         self
            getDerivations: (tmp = ’’
                  ifTrue: [1]
                  ifFalse: [2])].
   angle := (FillInTheBlank request: ’angle?’
                      initialAnswer: ’60’) asNumber.
   niveau := 5.
   self encore

Voilà. Nous avons enlevé la première limitation, enoncée sur la page 412, de notre interprète des systèmes de Lindenmayer. Attaquons nous alors à la deuxième: permettre à nos règles de réécriture de contenir aussi des caractères correpondant à des commandes concernant non pas le tracé graphique mais l’interprète même.

[next] [prev] [prev-tail] [front] [up]