Dessine moi...
Cette feuille en Postscript

1  Dessine moi un cercle

Le but de cet exercice est le dessin d'un cercle à l'écran, en suivant le principe de l'algorithme de Bresenham pour le tracé des droites. On cherche à produire une approximation de Freeman : lorsque la courbe traverse une des lignes de la grille, on « allume » le point de la grille qui est le plus proche de l'intersection.
On note que l'approximation de Freeman est conservée par les transformations qui laissent la grille invariante.

En pratique on construit l'approximation de proche en proche en suivant les mouvements du roi sur un échiquier. On pose que la courbe est définie par une fonction continue et suffisamment lisse y = f(x) sur un certain domaine.
  1. On suppose que f est telle que, sur le domaine concerné et pour tout point de la courbe, la courbe est entièrement comprise dans les octants W-NW et E-SE (cela doit revenir à une hypothèse f décroissante, convexe et de dérivée comprise entre 0 et -1)

    Montrer que les mouvements possibles sont limités à deux et concevoir un test simple pour choisir.

  2. Considérer le cas d'un cercle centré à l'origine et de rayon R entier, on définira un domaine adéquat, un premier point et la condition de passage au point suivant.

  3. Écrire un premier jet du programme qui dessine la fraction de cercle définie ci-dessus. On suppose donnée une méthode pxl(int x, int y) pour allumer le point (x,y).

  4. Modifier le programme simple afin qu'il n'effectue que des calculs entiers et aucune multiplication entre deux termes non-constants.

  5. Examiner sérieusement la délicate question de la limitation du domaine. On pourra s'inspirer des dessins de quarts de cercle donnés par la figure 1.

    Figure 1 : Quelques quarts de cercle pour des rayons entiers


    Cette figure illustre l'approximation de Freeman. Les points gris (x0,y0) sont construits par une marche du roi sous condition x0 ≤ y0 et les point blancs sont les symétriques (y0,x0) des gris pour x0 < y0.

  6. Examiner la question bien plus facile du dessin d'un cercle de rayon entier R centré en un point de coordonnées entières (xc, yc). On supposera que l'écran est en mode XOR, c'est à dire qu'allumer un point allumé revient à éteindre.
Solution.

2  Enveloppe convexe incrémentale

Le but de cet exercice est la présentation d'une méthode finalement simple pour construire l'enveloppe convexe d'un ensemble de points donnés au fur et à mesure. Dans tout l'exercice on suppose que les points sont en position générale c'est à dire qu'il n'existe pas 3 points alignés.

Les polygones (convexes) seront représentés par la liste de leurs points pris dans le sens trigonométrique. On note Cn un polygone à n côtés. Voici par exemple un polygone C5 = A0, A1, A2, A3, A4.
  1. Caractériser les points P intérieurs à Cn à l'aide des déterminants det(AiP, AiAi+1) (on considère aussi la dernière arête An-1A0).

    On remarquera que chaque vecteur AiAi+1 divise le plan en deux demi-plans caractérisés par le signe du déterminant det(AiP, AiAi+1)

  2. On se donne un point supplémentaire P, donner une méthode pour construire l'enveloppe convexe des points A0, A1, A2, A3, A4, P.

  3. En déduire une méthode pour construire l'enveloppe convexe de n points donnés au fur et à mesure. Estimer le coût de cette méthode.

  4. Montrer que si les points sont présentés triés selon l'ordre lexicographique, alors on peut concevoir un algorithme linéaire en le nombre de points. Bien identifier la structure de données nécessaire.

  5. On se donne une classe des points (et listes de points).
    class Point {
          int x, y ;
          PointList next ;

          PointList (int x, int y, PointList next) {
           this.x = x ; this.y = y ; this.next = next ;
      }
    }
    Programmer la méthode d'extension du polygone convexe p par un point q.

  6. Se passer de l'hypothèse de la position générale.
Solution.
En bonus une un programme complet qui réalise l'exercice.

Ce document a été traduit de LATEX par HEVEA et HACHA.