Triceraprog
La programmation depuis le Crétacé

Avec de passer à l'implémentation en BASIC du cercle décrit dans un article précédent, passons un peu par une phase de simplification. Cet article va contenir quelques lignes de mathématiques.

L'outil mathématique le plus complexe utilisé est celui des factorisations et développements de carrés. Les identités remarquables seront d'un grand secours. Niveau de fin de collège je crois.

Pour rappel, voici l'algorithme de tracé de cercle de Bresenham :

• initialiser cx et cy avec les coordonnées du centre du cercle, r avec son rayon
• initialiser (x, y) à (0, r), c'est à dire le point au sommet du cercle.
• tant que x ≤ y
  • tracer le pixel(x + cx, y + cy) et ses sept symétries.
  • calculer $m = (x+1)^2 + (y-0.5)^2 - r^2$
  • si m ≥ 0 alors $x \leftarrow x + 1$ et $y \leftarrow y - 1$
  • sinon $x \leftarrow x + 1$
• fin

On pourrait l'implémenter tel quel. Mais je veux d'abord attirer votre attention sur un détail assez simple. Dans les deux cas de la condition, que m soit ou non supérieur à zéro, x est augmenté de 1. En effet, si vous vous souvenez, quoi qu'il arrive, on trace les pixels en prenant toujours le suivant sur la colonne à sa droite.

On pourrait donc réécrire :

• initialiser cx et cy avec les coordonnées du centre du cercle, r avec son rayon
• initialiser (x, y) à (0, r), c'est à dire le point au sommet du cercle.
• tant que x ≤ y
  • tracer le pixel(x + cx, y + cy) et ses sept symétries.
  • calculer $m = (x+1)^2 + (y-0.5)^2 - r^2$
  • si m ≥ 0 alors $y \leftarrow y - 1$
  • $x \leftarrow x + 1$
• fin

Cela aura le même résultat, et un peu moins d'instructions.

Une petite pause ici : avec des langages compilés et des outils de compilation récents, il est très probable que ce genre de simplification soit fait automatiquement par le compilateur. Ce qui n'empêche pas d'écrire un code plus simple, mais sans aller jusqu'à simplifier au point que le lecteur humain ne comprenne plus rien. Ici, dans le monde BASIC interprété des années 1980, c'est une simplification intéressante que l'on doit faire à la main.

Cette simplification fait partie des optimisations. Avec moins d'instructions, le programme ira probablement plus vite. Dans notre cas ici, le routine d'affichage de pixel est tellement lente que l'effet est négligeable. Mais tout de même.

Simplifions encore

Un autre type d'optimisation peut venir d'une simplification des calculs à effectuer. Le BASIC du VG5000µ n'est pas très rapide en calculs et on demande ici dans la boucle de tracé sept opérations dont trois multiplications. Et les multiplications générique, c'est lent.

Plutôt que de calculer m complètement à chaque fois, il est possible d'en calculer la valeur à partir de la valeur précédente. Attention, un peu de mathématiques.

Disons que $m_i$ est la valeur de m à l'itération i. Et $m_{i+1}$ la valeur à l'itération suivante. Avec la même notation pour x et y à chaque itération (le rayon r ne bouge pas), on peut poser : $m_i = (x_i+1)^2 + (y_i-0.5)^2 - r^2$.

Et pour le calcul de m à l'itération suivante : $m_{i+1} = (x_{i+1}+1)^2 + (y_{i+1}-0.5)^2 - r^2$

Il y a deux cas dans l'algorithme, d'abord celui où l'on sélectionne le pixel de droite. Dans ce cas là, x est augmenté de 1, et y ne change pas. Cela donne ces deux égalités : $x_{i+1} = x_i + 1$ et $y_{i+1} = y_i$.

Avec l'objectif de calculer $m_{i+1}$ à partir de $m_i$, remplaçons dans l'équation :

• $m_{i+1} = (x_{i+1}+1)^2 + (y_{i+1}-0.5)^2 - r^2$
• $m_{i+1} = (x_{i+1}+1+1)^2 + (y_{i}-0.5)^2 - r^2$, (par substitution des termes à l'itération précédente)
• $m_{i+1} = (x_i^2 + 4x_i + 4) + (y_{i}-0.5)^2 - r^2$, (par développement du premier carré)
• $m_{i+1} = ((x_i^2 + 2x_i + 1) + (y_{i}-0.5)^2 - r^2) + 2x_i + 3$, (par commutativité et associativité)
• $m_{i+1} = ((x_i + 1)^2 + (y_{i}-0.5)^2 - r^2) + 2x_i + 3$, (par factorisation)
• $m_{i+1} = m_i + 2x_i + 3$, (par substitution du premier groupe qui est la définition de $m_i$)

Ou bien, si l'on préfère calculer $m_{i+1}$ par rapport aux coordonnées à la même itération :

• $m_{i+1} = m_i + 2(x_{i+1} - 1) + 3$, (par substitution)
• $m_{i+1} = m_i + 2x_{i+1} - 2 + 3$, (par développement)
• $m_{i+1} = m_i + 2x_{i+1} + 1$, (par simplification)

Dans le deuxième cas où l'on prend le pixel en diagonal, on a x toujours augmenté de 1, mais aussi y qui est réduit de 1. Cela donne ces deux égalités : $x_{i+1} = x_i + 1$ $y_{i+1} = y_i - 1$.

Remplaçons dans l'équation suivant le même principe :

• $m_{i+1} = (x_{i+1}+1)^2 + (y_{i+1}-0.5)^2 - r^2$
• $m_{i+1} = (x_{i}+1+1)^2 + (y_{i}-1-0.5)^2 - r^2$, (par substitution des termes à l'itération précédente)
• $m_{i+1} = (x_{i}+2)^2 + (y_{i}-\frac{3}{2})^2 - r^2$, (par simplification)
• $m_{i+1} = (x_{i}^2+4x_{i}+4) + (y_{i}^2-3y_{i}+(\frac{3}{2})^2) - r^2$, (par développement des deux carrés)
• $m_{i+1} = ((x_{i}^2+2x_{i}+1) + (y_{i}^2-y_{i}+(\frac{1}{2})^2) - r^2) + 2x_{i} + 3 - 2y_{i} + \frac{8}{4}$, (par commutativité et associativité)
• $m_{i+1} = m_i + 2x_{i} + 3 - 2y_{i} + \frac{8}{4}$, (par substitution du premier groupe qui est la définition de $m_i$)
• $m_{i+1} = m_i + 2x_{i} + 3 - 2y_{i} + 2$, (par simplification, mais pas trop, pour garder la forme du premier cas visible dans l'équation)

Ou bien, si l'on préfère calculer $m_{i+1}$ par rapport aux coordonnées à la même itération :

• $m_{i+1} = m_i + 2(x_{i+1}-1) + 3 - 2(y_{i+1}+1) + 2$, (par substitution)
• $m_{i+1} = m_i + 2x_{i+1} - 2 + 3 - 2y_{i+1} - 2 + 2$, (par développement)
• $m_{i+1} = m_i + 2x_{i+1} + 1 - 2y_{i+1}$, (par simplification, mais pas trop, pour garder la forme du premier cas visible dans l'équation)

Dans les deux cas, il s'agit donc d'ajouter à l'ancienne valeur de m un calcul qui dépend des nouvelles coordonnées. La multiplication est une multiplication par 2, ce qui est beaucoup plus rapide pour un ordinateur qu'une multiplication générale. Bon, pas en BASIC VG5000µ, mais je vous assure que dans le future, nous serons heureux d'avoir cette simplification.

Une autre étape intéressante peut-être de relier les deux équations, en cherchant à exprimer le résultat du choix du pixel en diagonal par le résultat lorsque le choix est celui du pixel à droite.

Voilà la raison de ne pas trop simplifier les équations à la fin des calculs. Le calcul final est :

• $m_{i+1} = m_i + 2x_{i+1} + 1 - D$, (D pour diagonale)
• $D = 0$ si l'on choisi le point de droite,
• $D = 2y_{i_+1}$ si l'on choisi le point en diagonale.

Point de départ

Maintenant que l'on sait compter la valeur de m à une itération donnée par rapport à sa valeur précédente, il nous faut bien un point de départ. Le tout premier m, que l'on note $m_0$ est la valeur pour le premier pixel tracé. Pour rappel, dans l'algorithme, le premier pixel est celui en haut du cercle, c'est-à-dire aux coordonnées x = 0 et y = r.

Il suffit de remplacer ces valeurs dans l'équation qui nous donne la valeur de m :

• $m = (x+1)^2 + (y-0.5)^2 - r^2$
• $m = (0+1)^2 + (r-0.5)^2 - r^2$, (par substitution)
• $m = 1^2 + r^2-r+(\frac{1}{4})^2 - r^2$, (par développement)
• $m = \frac{5}{4} - r$, (par simplification)

Aïe, une fraction. Une fraction, c'est très bien tant qu'on est dans le calcul. Par contre, une fois que l'on doit passer à l'implémentation, cela se corse. Mieux vaut garder des calculs sur des entiers, surtout sur des machines de cette époque.

Heureusement, tout ce qui nous intéresse dans m pour choisir le pixel suivant est son signe. Est-ce un nombre positif ou négatif ? Cette information restera valide même si la valeur de m est multipliée par un nombre positif.

L'astuce ici sera donc, à l'implémentation, de ne pas calculer m, mais 4m, c'est-à-dire quatre fois la valeur de m. L'algorithme reste valide, et l'on se débarrasse de la fraction. En gardant des multiplications par multiples de 2, on garde la facilité à multiplier des entiers rapidement.

• $4m_0 = 5 - r$

Conclusion

Cet article est un passage presque entièrement dédié à des mathématiques. Celles-ci nous ont aidé à réduire les calculs nécessaires à la résolution d'un algorithme.

Transformer un problème en un équivalent plus simple est une des bases de l'optimisation. Cela fait parfois appel aux mathématiques, parfois à la connaissance de la machine utilisée, parfois au langage de programmation en lui-même.

Au final, voici le nouvel algorithme, qui sera transformé en BASIC dans l'article suivant.

• initialiser cx et cy avec les coordonnées du centre du cercle, r avec son rayon
• initialiser (x, y) à (0, r), c'est à dire le point au sommet du cercle.
• initialiser M à $5 - r$
• tant que x ≤ y
  • tracer le pixel(x + cx, y + cy) et ses sept symétries.
  • calculer $m = (x+1)^2 + (y-0.5)^2 - r^2$
  • si m ≥ 0 alors $y \leftarrow y - 1$, $M \leftarrow M - 8y_{i+1}$
  • $x \leftarrow x + 1$, $M \leftarrow M + 8x_{i+1} + 4$
• fin