AA2022

Benjamin Dupont et Jean-Jacques BOURDIN

TP2 et TP3 : Droites

Voici une base de programme qui permettra de tester les fonctions que vous allez écrire.
Notez que nous faisons deux fonctions, une pour tester les valeurs et pouvoir afficher la droite, une pour tester le temps passé en calculs effectifs. 

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<assert.h>
#include<string.h>

#define MAX 2000
typedef unsigned char uchar;
typedef unsigned char monplan [MAX][MAX];

void droite_triviale (int u, int v, monplan pl) {
  int x, y;
  float z;
  for (x = 0; x <= u; x++) {
    z = ((float) x * v / u) + 0.5;
    y = (int) z;
  }
}
void droite_triviale_verif (int u, int v, monplan pl) {
  int x, y;
  for (x = 0; x <= u; x++) {
    y = (int) (((float) x * v / u) + 0.5);
    pl [x][y] = '.';
  }
}

void affiche (int sizex, int sizey, monplan pl) {
  int i, j;
  for(j = sizey; j >= 0; j--) {
    for (i = 0; i <= sizex; i++) 
      printf("%c", pl[i][j]);
    printf("\n");
  }
}
	     
int main (int argc, char ** argv) {
  int sizex, sizey, dx, dy, i, j;
  monplan plan;
  clock_t t0, t1, dt;
  
  dx = 100;
  dy = 100;
  if (argc == 3) {
    dx = atoi (argv[1]);
    dy = atoi (argv[2]);
  }
  if (dx < 0)
    dx = 0 - dx;
  if (dy < 0)
    dy = 0 - dy;
  if (dx < dy) {
    dx += dy;
    dy = dx - dy;
    dx = dx - dy;
  } /* nous restons dans le premier octant */
  if (dx >= MAX)
    dx = MAX - 1;
  if (dy >= MAX)
    dy = MAX - 1;
  memset (plan, ' ', MAX*MAX);
  droite_triviale_verif (11, 3, plan);
  printf("Triviale\n");
  affiche (11, 3, plan);
  memset (plan, ' ', MAX*MAX);
  droite_triviale_verif (24, 10, plan);
  affiche (24, 10, plan);
  memset (plan, ' ', MAX*MAX);
  droite_br_verif (11, 3, plan);
  printf("Bresenham\n");
  affiche (11, 3, plan);
  memset (plan, ' ', MAX*MAX);
  droite_br_verif (24, 10, plan);
  affiche (24, 10, plan);
  memset (plan, ' ', MAX*MAX);
  droite_rvw_verif (11, 3, plan);
  printf("Rokne\n");
  affiche (11, 3, plan);
  memset (plan, ' ', MAX*MAX);
  droite_rvw_verif (24, 10, plan);
  affiche (24, 10, plan);

  t0 = clock();
  for (i = 0; i < dx; i++) {
    for (j = 0; j < dy; j++) {
      droite_triviale (i, j, plan);
    }
  }
  t1 = clock();
  printf("triviale %d\n", (int) (t1 - t0));
  t0 = clock();
  for (i = 0; i < dx; i++) {
    for (j = 0; j < dy; j++) {
      droite_br (i, j, plan);
    }
  }
  t1 = clock();
  printf("Bresenham %d\n", (int) (t1 - t0));
  t0 = clock();
  for (i = 0; i < dx; i++) {
    for (j = 0; j < i; j++) {
      droite_rvw (i, j, plan);
    }
    for (j = 0; j < i; j++) {
      droite_rvw (i, j, plan);
    }
  }
  t1 = clock();
  printf("Rokne %d\n", (int) (t1 - t0));

}

Écrivez les fonctions suivantes et testez-les en valeurs (dessins identiques) puis enlevez les affectations de la matrice pour les tester en temps.

  1. Algorithme de Bresenham
  2. Algorithme du pas de deux, Rokne, Wyvill et Wu (CG&A 1993)
    Pour réussir ce programme, il "suffit" de remarquer que la fonction delta reste la même 

    delta (x,y) = 2 * x * dy - 2 * y * dx - dx

    Il suffit donc de compter que, quand on regarde en x+2, on calcule delta(x+2,y) qui se déduit assez facilement de delta, non ?

    Si on est dans la partie haute de l‘octant, il faut regarder delta(x+2, y+1)

  3. Algorithme du pas de trois, Graham et Iyengar (CG&A 1994)
  4. (facultatif) Algorithme du pas de quatre, Gill (CG&A 1994)
  5. Algorithme avec pas auto-adaptatif, B. et B. (CG&A 2000)
  6. Algorithme utilisant le pgcd, Angel et Morrisson (CG&A 1991)
  7. Algorithme Dulucq-Bourdin, non publié
  8. Algorithme d‘Euclide, Castle and Pitteway (1985)
  9. Algorithme de Berstel, J. Berstel. Mots, Mélanges offerts à MP. Schützenberger, chapter Tracés de droites, fractions continues et morphismes itérés, Hermès 1990.

Dernière mise à jour : 3/10/2022 (14h)