Infographie 2D - TP 2

mar. 16 septembre 2014

Géométrie algorithmique - Génération de tracés

Algorithme de Bresenham

Exercice 1. Un segment de droite peut être défini par deux points, à partir desquels on peut déterminer son equation : \(y = ax + b\) .

Ecrire le programme "naïf" de tracé de segments de droite dans l'espace écran, reliant deux points quelconques \(P_1(x_1,y_1)\) et \(P_2(x_2,y_2)\) , définis dans l'espace objet, en utilisant cette équation et en calculant les valeurs de y pour x dans \([x_1, x_2]\) (avec un majorant du pas).

Exercice 2. Cette méthode n'est pas assez rapide pour les systèmes graphiques interactifs (manipulation dynamique des objets de la visu). Il faut donc adopter une solution plus efficace : l'algorithme de Bresenham pour la droite.

Ecrire le programme de tracé de segments de Bresenham pour un segment de droite défini dans le premier octant et dont l'un des sommets est confondu avec l'origine.

Exercice 3. Adapter ce programme pour le tracé d'un segment de droite quelconque en conservant son caractère optimal.

Exercice 4. Comparer en temps (voir pour cela le module time) les tracés de 1000 segments engendrés aléatoirement et construits par l'un et l'autre des programmes de tracés.