Algorithmique Avancée 2021

De la Droite Discrète

1. Définition
   De droite il n'est pas question, de chemin discret approximant un segment de droite entre deux points, oui.
   
2. De l'évidence à la référence
   

   void droite (int x0, int y0, int x1, int y1) { int x, y; float yf; for (x = x0; x <= x1; x++) { yf = (float) (x - x0) * (y1 - y0); yf /= (x1 - x0); yf += y0; y = (int) (yf + 0.5); /* approximation à l’entier le plus proche*/ affiche(x,y); } }

   Est à la fois simple et peut efficace. Jack Bresenham a présenté un travail fort différent en 1962 (publié en 1965) :

   void droite_br (int u, int v) { /* u est dx, v est dy */ int x, y, delta, incD, incH; incH = v << 1; delta = incH - u; incD = delta - u; for (x = 0, y = 0; x <= u; x++) { affiche(x, y); if (delta > 0) { y++; delta += incD; } else { delta += incH; } } }

3. Améliorer la référence
   
   1. Rokne, Wyvill et Wu (CG&A 1993) via le pas de deux
      Vous trouverez cet article dans le catalogue de la bibliothèque. Il faut se connecter à votre compte sur le portail de l'Université, puis, dans l'onglet BU en ligne, tout en bas, consulter les bases de données. La seconde est "l’ACM digital library", vous y allez et, là, en haut à gauche vous trouvez un champ recherche, tapez le titre "Fast line scan-conversion" et c’est la permière entrée.
   2. Graham et Iyengar (CG&A 1994) via le pas de trois : "Double- and triple-step incremental generation of lines"
      Vous le trouverez de la même manière.
   3. Gill (CG&A 1994) via le pas de 4, ou 5 ou N
      
   4. B. et B. (CG&A 2000) via le pas auto-adaptatif.
   Exercice : tester les algorithmes précédents en temps et qualifier le gain effectif.
4. Angel et Morrison (CG&A 1991) via le pgcd
   /* u est dx, v est dy */
   • Calculer g le pgcd de u et v.
   • Calculer ug= u/g et vg= v/g
   • Calculer la droite de pente (ug, vg).
   • Pour l’affichage, réitérer g fois le chemin trouvé.

     Ils annoncent être trois fois plus rapides que Bresenham. Comme le pgcd moyen est 4, ce serait un résultat un peu faible. Le problème est que le pgcd moyen est bien environ 4 mais plus de 60% des couples d'entiers ont un pgcd égal à 1. Pour 60% des couples, il n'y a aucune accélération. Donc le temps passé à faire des calculs ne peut pas être inférieur à 60% du temps initial !

     Il faut rajouter à cela le calcul du pgcd et les 40% de couples de nombres pour lesquels l'accélération est forte (10). On doit être à plus de 64% du temps initial. L'accélération est forte, sans doute une vitesse de 1.5, ce qui est très faible par rapport à ce qui est annoncé.

5. Chercher ailleurs et autrement
   
   1. "Sous les pavés"
      
   2. Euclide et applications
      
      1. Berstel
      Une fois connue la décomposition de la fraction dy/dx en série de fractions continues

      dy/dx = [u0; u1, u2, u3, ..., un]

      l’algorithme suivant peut être utilisé.

      	       w(0) = 0
      	       w(1) = 0^(u1-1) . 1
      	       w(i) = w(i-1)^ui . w(i-2)  (i impair)
      	       w(i) = w(i-2) . w(i-1)^ui  (i pair)
      	     

      . est l’opérateur de concaténation tandis que "w^n" est la duplication n fois du mot w. Exemple d’utilisation : soit la droite de pente 3/11. La décomposition est [0; 3, 1, 2]. On a :

      	       w(0) = 0
      	       w(1) = 0 0 1
      	       w(2) = 0 0 0 1
      	       w(3) = 0 0 0 1 0 0 0 1 0 0 1
      	     

      Reste à savoir comment on obtient la décomposition d’une fraction en série de fractions continues.
      D'abord remarquons que, dans ce qui nous intéresse, la fraction v/u est plus petite que 1. Donc la fraction v/u vaut 0+1/(u/v)
      Mais u/v c'est u divisé par v plus u modulo v divisé par v.
      vi/ui = 1/(mi + vj/uj), avec
      j = i + 1
      mi = (int) (ui / vi)
      vj = ui % vi
      uj = vi
      On continue ainsi jusqu’à ce que vj soit inférieur à 2.
      la suite [m0; m1, m2, m3,...,mn] est une représentation de la fraction v/u.
      
      2. Green and Pitteway
         

                droite (dx, dy) {
                   dx -= dy;
                   s = "0";
                   t = "1";
                   while (dx != dy) {
                      if (dx > dy) {
                         dx -= dy;
                         t = s . t;
                      }
                      else {
                         dy -= dx;
                         s = s . t;
                      }
                   }
                   return ( s . t ) ^dx;
                 }
                 

         La version suivante calcule la droite "meilleure approximation", contrairement à ce que nous avons vu en cours le 4/10.

                droitebest (dx, dy) {
                   dx -= dy;
                   s = "0";
                   t = "1";
                   while (dx != dy) {
                      if (dx > dy) {
                         dx -= dy;
                         t = s . t ^(-1);
                      }
                      else {
                         dy -= dx;
                         s = t . s ^(-1);
                      }
                   }
                   return ( s . t ^ (-1) ) ^dx;
                 }
                 

      3. Dulucq et Bourdin Principe général :
         
         • la fonction phi de m transforme un 1 en une plage de m 0 suivis d'un 1.
         • la fonction phi de m transforme un 0 en une plage de (m+1) 0 suivis d'un 1.
         • la fonction psi de m transforme un 0 en un 0 suivi d'une plage de m 1.
         • la fonction psi de m transforme un 1 en un 0 suivi d'une plage de (m+1) 1.
         • la fonction db traite des cas particuliers, pour éviter les nombreuses fois où on voudrait relancer une récursivité inutile.
         Algorithme dans le premier octant :
         • si u > 2 * v
           w(u,v)=phi(m,w(p,q))
           avec
           m = (u-v)/v
           p = v
           q = v - u % v
           phi (m,"0") = "000...01" (m+1) fois 0 et un 1
           phi (m,"1") = "00...01" (m) fois 0 et un 1
           
         • si u < 2 * v
           w(u,v)=psi(m,w(p,q))
           avec
           m = v/(u-v)
           p = u-v
           q = v % (u - v)
           psi (m,"0") = "011...1" 0 et (m) fois 1
           psi (m,"1") = "0111...1" 0 et (m+1) fois 1
           
   3. Plages (Spans)
   4. Récapitulation et algorithme rapide
      De tout cela découle un algorithme particulièrement rapide (près de 20 fois plus rapide que celui de Bresenham en 1965), qui est présenté dans cet article à Eurographics, en 1999.

Dernière mise à jour : 15/11/2021 (15h)