Licence d'Informatique
Devoir 1 - à rendre le 27 avril 1998
L'objet de ce devoir est la mise en oeuvre d'un algorithme de tracé de contour avec un pinceau.
Un pinceau est défini par une forme géométrique arbitraire. On représente un pinceau par l'ensemble des bandes horizontales correspondant à son intersection avec chaque ordonnée y. On se restreint aux pinceaux dont l'intersection avec toute horizontale est soit vide soit réduite à un seul intervalle. La figure ci-dessous montre deux exemples de pinceaux, les bandes horizontales correspondantes, et le point de référence (pixel blanc).
L'algorithme à réaliser doit permettre de tracer la forme obtenue en déplaçant le pinceau le long d'un contour polygonal. Cette forme doit être affichée de telle sorte que chaque pixel appartenant à la forme n'est dessiné qu'une seule fois. A cet effet, on utilisera une structure de données semblable à celle utilisée pour le remplissage de polygones : pour chaque ordonnée y, on stocke l'ensemble des bandes correspondant à l'intersection de la forme avec cette ordonnée. L'algorithme consiste donc à placer le point de référence du pinceau sur chaque point du contour et à faire l'union des bandes du pinceau et des bandes de la forme en cours de calcul. L'affichage n'a lieu qu'à la fin, lorsque toutes les bandes ont été calculées.
L'algorithme devra également réaliser le clipping de la forme sur une zone rectangulaire. La figure ci-dessous montre le tracé (approximatif) d'une étoile avec les deux pinceaux ci-dessus.
On pourra réutiliser les programmes vus en TDs, notamment ceux du tracé de segment par l'algorithme du point médian et ceux permettant de définir interactivement un polygone.
Les documents à rendre sont :