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?
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=Y0 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.
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.
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;