===== TD2 Remplissage =====

==== Tracer un disque ====

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 [[fain_cercles#algorithme_de_bresenham|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;

==== Remplir un Polygône par Balayage ====

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

=== Structures de données ===

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;

=== Les Coupes ===

La demi-droite horizontale y=Y<sub>0</sub> coupe le polygone en n points <jsm>x_j</jsm>. 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.

== corrigé ==

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.
  - Trier les intersections par ordre croissant
  - InterA = tête de liste;
  - InterB = InterA->next;
  - Répéter jusqu' la fin de la liste (==InterB)
    - SegHori(InterA, InterB, y);
    - InterA=InterB->next;
    - InterB=InterA->next;

==== Calcul des autres points d'intersection ====


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.

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

==== Remplissage du tout ====

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;

  - ET = liste triée des arêtes (d type arete_t) n__non__-horizontales de P dans l'ordre croissant de inf.y.
  - AET = liste vide (initialement) d'arêtes actives.
  - 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?).
  - Tant qu'on n'a pas fini
    - FIXME à completer plus tard.

==== Navigation ====

[[fain_td1| ]] -- [[fain_td3|]]