On supposera disposer d'une fonction SegHori(x1, x2, y) trançant un segment horizontal. Ecrire un algorithmes qui n'utilise que des opérations sur les entiers pour tracer un disque (constitué de pixels à l'intérieur d'un cercle).

Stratégie : rajouter des appels à SegHori dans l'algo de tracer de cercle de Bresenham.

 disque (rayon R, couleur C)
  x=0; y=R; d=3-2*R;  // initialisation
  tant que (x =< y) faire
    SegHori(-x,  x,  y, C);  // octants II et III
    SegHori(-x,  x, -y, C);  // octants VI et VII
    SegHori(-y, -x,  x, C);  // octant IV
    SegHori( x,  y,  x, C);   // octant I
    SegHori(-y, -x, -x, C);  // octant V
    SegHori( x,  y, -x, C);  // octant VIII
    si ( d>0 ) {d=d+4*x+6;}
    sinon {d=d + 4*(x-y) + 10; y=y-1; }
    x=x+1;

Soit un polygône quelconque, qui peut n'être ni régulier, ni convexe, ni simple.

Pour le sommet, l'arête et le polygone : comment organiser le stockage des données?

• sommet : un point? ou un point et la liste des arêtes incidents? juste un point
• arêtes : deux extrémités donc deux points? oui, c'est ça
• polygone : liste chainée des arêtes? oui, plus le nombre d'arêtes.

Le corrigé propose

typedef struct point_t {
  int x,y; } point_t;
 
typedef struct arete_t {
  point_t p1, p2; } arete_t;

typedef struct polygone_t {
  int nb_aretes;
  arete_t *arete; } polygone_t;

La demi-droite horizontale y=Y₀ coupe le polygone en n points x_j. Comment stocker ces intersections? Comment s'en servir pour colorier les points de la droite horizontale qui appartiennent à l'intérieur du polygone?

En fait, ce sera la liste des pixels (point_t) appartenant aux arêtes, triés (ordre croissant) par y et puis par x. Pour un y donné, la liste fournira les points d'instersection successifs.

Le corrigé propose une liste chainée mais des seuls xj. Voyons où ça nous menera.

typedef struct Xintersection_t {
  int xj;
  struct Xintersection_t *next; } Xintersection_x_t;

Ensuite, on va supposer qu'il n'y a pas d'intersections avec des sommets : comment serait-ce possible? Mais on traitera cette question plus tard.

1. Trier les intersections par ordre croissant
2. InterA = tête de liste;
3. InterB = InterA→next;
4. Répéter jusqu' la fin de la liste (==InterB)
   1. SegHori(InterA, InterB, y);
   2. InterA=InterB→next;
   3. InterB=InterA→next;

Plusieurs méthodes sont proposées dans le corrigé, dont deux avec des calculs flottants. Passons tout de suite à l'algorithme entier. Le but est de calculer les xj pour y+1; on se limite à l'ensemble des arêtes actives…on verra plus tard comment gérer les entrées en, et sorties d'activité.

typedef struct arete_active_t {
  int xj;
  int DyFoisDistCD;
  int DX, Dy;
  struct arete_active_t *next; } arete_active_t;

Le principe est d'utiliser la connaissance de la pente de l'arête pour calculer l'incrément en x lorsque y augment par 1.

1. y = quelque chose
2. Tant que y n'a pas été augmenté
   1. trier les arêtes actives par xj croissant
   2. AA = PremièreAreteActive
   3. BB = AA.next
   4. Repeter jusqu'à epuisement des arêtes actives :
      1. SegHori (AA.xj, BB.xj, y);
      2. AA = BB.next
      3. BB = AA.next
   5. pour toutes les aretes actives (AA) :
      1. AA.DyFoisDistCD = AA.DyFoisDistCD + AA.Dx
      2. Tant que AA.DyFoisDistCD >= AA.Dy / 2
         1. AA.xj = AA.xj + 1
         2. AA.DyFoisDistCD = AA.DyFoisDistCD - AA.Dy
      3. Tant que AA.DyFoisDistCD < - AA.Dy / 2
         1. AA.xj = AA.xj - 1
         2. AA.DyFoisDistCD = AA.DyFoisDistCD + AA.Dy
      4. AA = AA.next
   6. y = y+1 (fin de boucle, goto 2)

On rajoute deux types de structures pour gérer les ensembles d'arêtes actives et inactives

typedef struct arete_t {
  point_t inf, sup;
  struct arete_t *next; } arete_t;

typedef struct arete_active_t {
  int xj;
  int ymax;
  int DyFoisDistCD;
  int DX, Dy;
  struct arete_active_t *next; } arete_active_t;

1. ET = liste triée des arêtes (d type arete_t) nnon-horizontales de P dans l'ordre croissant de inf.y.
2. AET = liste vide (initialement) d'arêtes actives.
3. y = PremiereArete(ET).inf.y : la plus faible valeur de y qui peut avoir une intersection avec un arete (un sommet en l'occurrence, non?).
4. Tant qu'on n'a pas fini
   1. à completer plus tard.

FAIN TD 1 – Géométrie Discrète