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 …
L'ordinateur 8 bits que j'ai le plus décortiqué, sur lequel j'ai le plus programmé en son temps, est un CPC 6128. J'y ai débuté le Pascal et abordé légèrement le C. J'y ai aussi fait mes premiers essais en assembleur.
Un ordinateur élégant, sobre, avec un clavier très agréable, qui pouvait servir dans de nombreux domaines. Son principal et historique défaut reste son format de disquettes, particulier, rare et cher.
Si vous avez fait un peu de trigonométrie à l'école, vous devez savoir que, pour un angle α allant de 0 à 2π, tracer des points aux coordonnées (cos(α), sin(α)). Ces coordonnées sont multipliées par le rayon et déplacées au centre du cercle. Et c'est comme cela qu'il peut sembler de prime abord intéressant de tracer un cercle.
Cela ressemble à quelque chose comme ça.
initialiser cx et cy avec les coordonnées du centre du cercle, r avec son rayon
initialiser a à 0
tant que \(a < 2\pi\)
\(x = cx + r.cos(a)\)
\(y = cy + r.sin(a)\)
tracer un point en (x, y)
augmenter a
fin
Super simple.
Mais trop simple.
Dans l'algorithme ci-dessus, la ligne qui indique augmenter a n'indique pas de combien il faudrait augmenter a.
Ah les monoblocs bien lourds, mais au design tellement reconnaissable. Cet ordinateur a aussi la particularité d'avoir un clavier particulièrement... pas pratique. Les modèles suivant troqueront le lecteur/enregistreur à cassette par un clavier de nettement meilleur qualité.
Après avoir décrit un algorithme de tracé de segment de droite de manière générique, voyons un peu comment traduire ça en BASIC sur le VG5000µ. Pour ce premier article, il s'agira d'une implémentation simpliste, qui servira de base.
Pour rappel, voici l'algorithme générique :
En entrée, on a deux points de coordonnées (x, y) et (x', y')
Si x' est plus petit que x, échanger les valeurs de x et x' ainsi que de y et y'
Choix de l'octant en fonction de |y' - y| et de |x' - x|
Si on fait un balayage des x, alors
Calculer la pente \(a = \frac{(y' - y)}{(x' - x)}\)
Calculer \(b = \frac{x'y - xy'}{x'-x}\)
Pour tous les x'' de x à x', calculer \(y'' = ax'' + b\).
Tracer un pixel en (x'', y'').
Si on fait un balayage des y, alors
Si y' est plus petit que y, échanger les valeurs de x …
