Triceraprog
La programmation depuis le Crétacé

Articles de la catégorie Algorithmes.

  • Après la ligne, le cercle ()

    Après avoir tracé des segments de droite à l'écran grâce au BASIC du VG5000µ, passons au cercle.

    Si vous avez fait un peu de trigonométrie à l'école, vous devez savoir que, pour un angle α allant de 0 à , 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.

    Lorsque l'on trace un cercle avec un crayon sur une feuille, on prend quelques points de références bien choisi, puis on interpole entre ces points pour tracer la courbe. Si on utilise un compas, c'est encore plus simple, il suffit de deux points de référence : le centre et un point du rayon.

    Nous avons ici le même problème que lorsque l'on cherchait à tracer un segment de droite : l'espace de tracé des points à l'écran n'est pas continu. Il s'agit dans notre cas d'allumer des pixels de manière à provoquer l'illusion de la continuité.

    S'ils sont trop tassés, c'est moche. S'ils sont trop espacés, ça fait des trous.

    Prenons un exemple avec cx = 6, cy = 5 et r = 5. Augmentons a d'un dixième de π à chaque fois. Voilà ce que cela donne :

    a 0.pi/101.pi/102.pi/103.pi/104.pi/105.pi/106.pi/10 7.pi/108.pi/109.pi/10
    x 1111109864321
    y 5789101010987
    a 10.pi/1011.pi/1012.pi/1013.pi/10 14.pi/1015.pi/1016.pi/1017.pi/1018.pi/1019.pi/10
    x 112346891011
    y 5321000123

    Traçons cela sur une grille.

    Cercle 1

    Tout comme avec le segment de droite au début, il y a des trous. Et si le rayon augmente, il y aura encore plus de trous. On peut se dire alors qu'on augmente a par de plus petites valeurs. Mais on voit sur le dessin qu'à certains endroits, les pixels sont adjacents. Cela signifierait qu'il faudrait, suivant les endroits, augmenter a différemment.

    Arrêtons-nous là pour deux raisons : la première est que l'on sent bien que cela va nous amener vers des choses vraiment complexes. La seconde est que calculer le cosinus et le sinus sur une machine ancienne de ce type, c'est lent, très lent. Certes, notre affichage de pixel est lent lui aussi, n'ajoutons pas du lent au lent.

    Mais alors que faire ?

    Changer de stratégie, et surtout, d'équation de départ. L'équation d'un cercle est aussi celle-ci : \(x^2 + y^2 - r^2 = 0\). Où r est le rayon. Un tel cercle est centré sur les coordonnées (0, 0) mais il suffit d'y ajouter les coordonnées du centre du cercle voulu pour le déplacer dans l'espace.

    Équation sur le cercle

    La deuxième chose que l'on va faire est, comme avant pour le segment de droite, de simplifier le problème en utilisant des octants, c'est-à-dire une division en huit secteurs. Ces secteurs sont choisis pour leurs axes de symétries sur le cercle de manière à ce que, pour un octant donnée, nous puissions nous occuper d'un cas très simple.

    Je vous invite à aller voir l'image plus bas pour repérer les axes de symétries utilisés.

    Une méthode

    En commençant par le point le plus haut du cercle et sur l'octant en haut à droite, on peut réduire le problème à une courbe qui part dans la direction générale entre la droite et la diagonale droite-bas. Dans ce secteur, un pixel aura pour voisin suivant soit le pixel juste à sa droite, soit le pixel juste au-dessous celui à sa droite.

    Si on trouve comment tracer ce petit morceau de courbe, il suffit de tracer les huit courbes symétriques sur le cercle pour obtenir la forme complète.

    Comment choisir si le pixel suivant le pixel courant doit être celui à sa droite ou celui en diagonal ? En utilisant la partie gauche de la formule ci-dessus pour évaluer la position du cercle parfait par raport à un point situé entre les deux points éligibles.

    Si le résultat est inférieur à 0, alors c'est que le point médian est à l'intérieur du cercle. On choisi alors le pixel à droite comme coordonnée suivante.

    Si le résultat est supérieur à 0, alors c'est que le point médian est à l'extérieur du cercle. On choisi alors le pixel en bas à droite comme coordonnée suivante.

    Et ainsi de suite jusqu'à ce que la coordonnée x soit supérieure à la coordonnée y, ce qui signal la fin de l'octant, puisque nous aurons alors atteint la diagonale.

    Reprenons :

    • 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

    Voyons ce que cela donne avec les même entrées que précédemment :

    x 6789
    y 1010109
    m -3.75
    (suivant à droite)
    -0.75
    (suivant à droite)
    4.25
    (suivant en bas à droite)
    3.25

    Le cercle n'a plus de trous, les pixels sont voisins et forment une illusion de continuité. Ce qui donne sur du papier quadrillé, avec en noir les coordonnées ci-dessus et en gris les différents symétriques.

    Cercle 2

    Note : cet algorithme n'est pas le seul possible et nous verrons lors de son implémentation qu'il peut être simplifié au niveau de ses calculs. Mais ceci est une autre histoire.

    Note 2 : le second algorithme présenté est l'algorithme de tracé de cercle de Bresenham, du nom de son auteur.


  • Après le point, la ligne ()

    Après avoir vu le point, si nous passions à la ligne ? Ou plus exactement, au segment de droite.

    Sur une feuille de papier, tracer un segment de droite entre deux points est une chose simple : un crayon, un règle, on positionne la règle sur les deux points et l'on trace un trait en tenant fermement cette dernière.

    Le trait a alors une allure continue ; du moment que l'on n'utilise pas un microscope pour en détailler la composition. Et c'est une représentation suffisante, dans la plupart des cas, de l'objet mathématique sous-jacent.

    Sur un écran d'ordinateur, c'est un tout autre problème. En effet, un écran traditionnel est constitué d'une matrice de petits carreaux, les pixels. Les pixels des écrans récents sont très petits et malgré cela, tracer un beau segment de droite n'est pas si simple. Alors imaginez avec les gros carreaux formant les affichages d'anciens ordinateurs ?

    Plutôt que de l'imaginer, vous pouvez même faire une expérience.

    Prenez une feuille à petits carreaux, choisissez un point de départ que vous coloriez en noir, un point d'arrivée que vous coloriez en noir. L'exercice consiste alors à colorier les carreaux intermédiaires afin de tracer un segment de droite.

    Si la réalisation est très simple pour des segments de droite horizontaux, vertiaux ou diagonaux, les droites plus quelconques, elles, demandent un peu plus d'attention afin d'obtenir un beau tracé, équilibré.

    Lignes à carreaux

    Une stratégie peut être de prendre une règle, de tracer un trait fin entre les milieux des deux cases d'extrémités et de colorier ensuite les cases traversées par le trait.

    Lignes à problèmes

    Il y a de l'idée, mais la droite, avec certaines orientations, est épaisse par endroit. Avec des gros pixels, cela ne va pas bien rendre.

    Une autre idée est d'utiliser la forme mathématique d'une droite : \(y = ax + b\). En ajustant correctement a et b et faisant varier x sur les coordonnées de l'écran, on devrait trouver y.

    Coordonnées

    x0123456
    y11,522,533,544,5

    La solution fonctionne bien... jusqu'à ce que a soit supérieur à 1. Au-delà de 1, le tracé du segment à l'écran n'est plus continu, mais comporte des trous !

    Des trous

    Et c'est sans parler du cas où l'on voudrait tracer un segment vertical. En effet, avec l'idée de faire varier les x, pour un segment vertical, x ne prend qu'une valeur. Et donc y une seule valeure aussi. Ce qui donne... un beau point. C'est normal puisqu'à une valeur de x on associe une et une seule valeur de y.

    Cette manière de tracer des segments de droite semble ne pas fonctionner, et pourtant, c'est première idée n'est pas si mauvaise. Elle nécessite juste un petit ajustement.

    Puisque la méthode de balayage des x fonctionne sur les segments de droites allant d'une pente nulle, l'horizontale, à une pente de 1, la diagonale, peut-être faut-il changer un peu d'angle pour les segments de droite allant de la diagonale à la verticale ?

    Pour cette partie-là, est-ce qu'il ne suffirait pas de poser : \(x = a'y + b'\) ? C'est-à-dire balayer les y pour obtenir les x, avec des coefficients ajustés en conséquence.

    Coordonnées

    y0123456
    x22 + 1/32 + 2/333 + 1/33 + 2/34

    Plus de trous

    Ça fonctionne plutôt bien.

    Par un jeu de symétries, le problème peut être résolu en séparant l'espace autour du point de départ en huit espaces qui induiront l'utilisation d'un balayage des x ou des y. Ces secteurs étant au nombre de huit, on les appelle des octants.

    Pour simplifier le problème, on peut limiter les cas à deux d'entres eux en prenant pour extrémité de départ le point le plus à gauche sur l'axe des x, par exemple. Il reste alors à considérer dans lequel des quatre octants à la droite de ce point le segment va être tracé, et choisir entre le balayage des x ou le balayage des y.

    Octants

    Pour décider de la méthode à appliquer, on peut commencer par calculer la pente de la droite. Si les deux points sont (x, y) et (x', y'), alors la pente de la droite est \(\frac{(y' - y)}{(x' - x)}\), le a dans \(y = ax + b\).

    Cependant, en cas de droite verticale, on se retrouve avec une division par 0 (x' étant égal à x). Si la droite est presque verticale, on peut aussi se retrouver avec des valeurs assez grandes et des problèmes de capacités de calcul de la machine.

    En fait, il n'est pas nécessaire de calculer la pente, car ce que l'on cherche à savoir où se situe la droite portant le segment par rapport à une horizontale, une verticale et une diagonale.

    Et pour cela, il suffit d'une part de comparer les valeurs absolues de \((y' - y)\) et de \((x' - x)\). Si dans le cas d'un balayage des y, on part du point le plus bas (tout comme on part du point le plus à gauche pour le balayage des x), alors les secteurs sont utilisés de cette manière :

    Décision


    Un premier algorithme

    J'obtiens donc une première idée d'algorithme qui ressemble grossièrement à ça :

    • 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 et x' ainsi que de y et y'
      • Calculer la pente \(a = \frac{(x' - x)}{(y' - y)}\)
      • Calculer \(b = \frac{y'x - yx'}{y'-y}\)
      • Pour tous les y'' de y à y', calculer \(x'' = ay'' + b\)
      • Tracer un pixel en (x'', y'')


    Voici un algorithme de tracé de segment de droite qui fonctionne. Mais qui est aussi extrêmement lent. Dans un prochain article, nous verrons comment rendre ça sur le VG5000 en BASIC.