===== FAIN TD 1 =====

==== Exercice 1 ====

Reconnaitre des figures 4-connexes et 8-connexes.

|7|  ||||||||7|  ^^ b^b ^b ^b |  ||7 |  ||||||||7 |  ||||||||
|6|  ||||||||6| ^c |  ^^^^ d| |6 |  ||||||||6 |  ||||||||
|5|  ||||||||5| ^c | ^ a| |^d | |5 |  ||||||||5 |  ^^ ^ ^ ^ | ||
|4|  ||||||||4| ^c | ^ a| |^d | |4|  |^  ||||  ||4|  |||^ | |||
|3|  |^ | |^ | ||3| ^ c| ^ a| |^d | |3|  |^ | |^ | ||3|  ^ | |^ | |||
|2|  |^ | |^ | ||2| ^c |  ^^^^d | |2|  |^ | |^ | ||2|  ^ | |^ | |||
|1|  |^ ^ ^ ^ | ||1|  ^^d^d ^d ^d ^d | |1|  ||^ ||| ||1|  |^ ^ ^ | |||
|0|  ||||||||0|  ||||||||0|  ||||||||0|  ||||||||
|  | 0 |1|2|3|4|5|6|7| | 0 |1|2|3|4|5|6|7|  | 0 |1|2|3|4|5|6|7|  | 0 |1|2|3|4|5|6|7|
| | ensemble 1 |||||||| | ensemble 2 |||||||| | ensemble 3 ||||||||  | ensemble 4 ||||||||

  - ensemble 1 est 4-connexe, et donc 8-connexe (aussi)
  - ensemble 2 n'est ni 4-connexe, ni 8-connexe puisque la "barre à l'intérieur" n'est pas 8-adjacent à un des pixels du reste. Mais on peut reconnaître un ensemble 4-connexe [(3,3),(3,4),(3,5)] est une figure 8-connexe, ou 4 ensembles 4-connexes. 
  - ensemble 3 est 4-connexe, et donc 8-connexe (aussi).
  - ensemble 4 est 8-connexe, ou deux ensembles 4-connexes.

Notons que:
  * le complémentaire de l'ensemble #1 est 4-connexe mais le complémentaire de l'ensemble #3 n'est pas 4-connexe, seulement 8-connexe.

Pour mémoire:
  * 2 pixels (x,y) et (x',y') sont __4-adjacents__ si (x-x', y-y') est (1,0) ou (-1,0) ou (0,1) ou (0,-1)
  * 2 pixels (x,y) et (x',y') sont __8-adjacents__ s'ils sont 4-adjacents ou si (x-x', y-y') est (1,-1) ou (-1,-1) ou (1,1) ou (-1,1)
  * un __4-chemin__ est une suite de pixels telle que 2 pixels consécutifs sont 4-adjacents.







==== Exercice 2 ====

Objectif: S'approprier l'algorithme de Besenham pour la tracé de segments, et réussir sa généralisation aux autres octants.

On rappelle que l'algorithme de Bresenham (en pseudo-C) est le suivant:

  segment(xA,yA,xB,yB) {
    dx=xB-xA; dy=yB-yA;
    incrd1=2*dy; incrd2=2*(dy-dx);
    x=xA; y=yA; d=2*dy-dx;
    while (x<xB) {
      AfficherPixel(x,y);
      x=x+1;
      if (d<0) then {d=d+incrd1;} else {y=y+1;d=d+incrd2;}
    }
    AfficherPixel(x,y);
  }

  - Dessiner le segment tracé par cet algorithme pour les points A(0,0) et B(4,3).
  - Indiquer si l'ensemble suivant est un segment tracé grâce à cet algorithme.
  - Quels sont les segments que permet de tracer cet algorithme? Généraliser l'algorithme pour qu'il dessine des segments de toute pente.
  - Quelle connexité ont les segments tracés?  Modifier l'algorithme pour qu'il trace des segments 4-connexes (pour cette question, on se limitera à des pentes dans le premier octant).

=== 2.1 ===
Pour dessiner le segment (00)-(4,3) nous avons déroulé l'algorithme :

| initialisation: | dx=4 | dy=3 | incrd1=6 | incrd2=-2 | d=2 |
^ Itération ^ x ^ y ^ d ^ Commentaire ^ AffichePixel ^
| 1 | 0 | 0 | 2 | d>=0 donc on execute "else": y=y+1 et d=d+incrd2 | (0,0) |
| 2 | 1 | 1 | 0 | d>=0 donc on execute "else": y=y+1 et d=d+incrd2 | (1,1) |
| 3 | 2 | 2 | -2 | d<0 donc on ne change pas y et d=d+incrd1 | (2,2) |
| 4 | 3 | 2 | 4 | d>=0 donc on execute "else": y=y+1 et d=d+incrd2 | (3,2) |
| 5 | 4 | 3 | 2 | fin de "where" (x=xB) | (4,3) |

=== 2.2 ===

Le segment illustré n'a pas pu être tracé par cet algorithme, car une colonne affiche des pixels dans plus d'une ligne.

|  |  |  | | | | | |* ^* |
|  |  |  | | | | * ^* ^ | |
|  |  | | ^ * ^* ^ | | | |
|  |  ^ * ^ * ^ | | | | | |
^ * ^ * | | | | | | | | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

Si nous supposons que le segment va de (0,0) à (9,4) et nous déroulons l'algo, nous obtenons :

| dx=9 | dy=4 | incrd1=8 | incrd2=-10 | d<sub>0</sub>=-1 | et ainsi

^ x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
^ y | 0 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 5 |
^ d |-1 | 7 |-3 | 5 |-5 | 3 |-7 | 1 |-9 | -1|

ce qui correspond aux ''*'' rajouté à l'illustration.

=== 2.3 ===

L'algorithme est construit pour les segments a faible pente positive, donc premier octant.  Pour le généraliser, il nous faut
  * inverser les rôles de x et y lorsque la pente est forte
  * traiter les pentes négatives (faibles et fortes)
  * traiter les segments à tracer de droite à gauche (c'est à dire, xA>xB).

=== 2.4 ===

Quelle connexité ont les segments tracés? __8-connexité, puisqu'il change de ligne et de colonne en même temps__ lorsqu'il change de ligne. 

Modifions l'algorithme pour qu'il trace des segments 4-connexes (cas du premier octant).

  segment(xA,yA,xB,yB) {
    dx=xB-xA; dy=yB-yA;
    incrd1=2*dy; incrd2=2*(dy-dx);
    x=xA; y=yA; d=2*dy-dx;
    while (x<xB) {
      AfficherPixel(x,y);
      x=x+1;
      if (d<0) then {d=d+incrd1;} else {
        AfficherPixel(x,y); // pixel d'angle (x+1,y) fournissant 4-connexité à (x,y) et (x+1,y+1)
        y=y+1;d=d+incrd2;
      }
    }
    AfficherPixel(x,y);
  }

<pagebreak>

==== Exercice 3 ====

Parabole P d'axe (Oy) passant par les points O=(0,0)et A=(2h,h).

  - Trouver une équation de (P) de la forme y=f(x) avec f à préciser.
  - On représente la parabole (P) entre les points O et A par l'ensemble (P') des pixels de coordonné <jsm>\left(x,\lfloor f\left(x\right) + \frac{1}{2}\rfloor\right)</jsm> où x parcourt les entiers entre 0 et 2h. Justifier ce choix.
  - Soit (x,y) un point de (P') avec x < 2h. 
    - Montrer qu'il existe un unique point M de (P) d'abscisse x+1 qui est soit <jsm>M_1 = \left(x+1,y\right)</jsm>, soit <jsm>M_2 = \left(x+1,y+1\right)</jsm>. 
    - Montrer que <jsm>M=M_2 \quad\Leftrightarrow\quad D\left(x,y\right)\geq 0</jsm> où D est un polynôme de degré 2 en x et y.
  - Calculer D(x,y) - D(x-1,y-1) et D(x,y)-D(x-1,y).
  - En déduire un algorithme de tracé de (P') ne comportant que des additions et des décalages.

=== 1). ===
 Nous allons supposer que notre parabole est de la forme <jsm>y=a x^2 + bx + c</jsm> et non <jsm>x = a y^2 + b y +c</jsm>
  * <jsm>a \times 0^2 + b\times 0 +c = 0 \Rightarrow c=0 </jsm>
  * <jsm> h = a\times \left( 2h \right)^2 + b\times \left( 2h \right) = 4ah^2 + 2bh \quad \Rightarrow \quad 4ah +2b -1 = 0</jsm>
  * On arrive à une équation en deux inconnnues : <jsm>\displaystyle a=\frac{1-2b}{4a}</jsm>. Si l'on pose b=0 (l'axe de la parabole sera 0y) on trouve <jsm>\displaystyle a=\frac{1}{4h}</jsm> et donc <jsm>\displaystyle f\left(x\right) = y =\frac{x^2}{4h}</jsm>

=== 2). ===
Ensuite, <jsm>\left(x,\lfloor f\left(x\right) + \frac{1}{2}\rfloor\right)</jsm> nous fourni l'arrondi à l'entier le plus proche de f(x).  Dans cette partie de la courbe, <jsm>dy = \frac{2x}{4h} \lt \frac{2\times 2h}{4h}= 1</jsm> car <jsm>x\leq 2h</jsm>. Ainsi, il s'agit d'une partie de courbe du premier octant et un pixel par colonne nous fournira une tracée 8-connexe.
  * Soit <jsm>F\left(n\right) = \lfloor f\left(n\right) + \frac{1}{2}\rfloor</jsm>
  * <jsm>\forall n \in \left[0, 2h-1\right]\;:\; 0 \leq f\left(n+1\right)-f\left(n\right)\leq 1 </jsm>
  * <jsm>F\left(n\right)-\frac{1}{2} \leq f\left(n\right) \lt F\left(n\right)+\frac{1}{2}</jsm> par la définition de <jsm>\lfloor\;\rfloor</jsm>
  * <jsm>F\left(n+1\right)-\frac{1}{2} \leq f\left(n+1\right) \lt F\left(n+1\right)+\frac{1}{2}</jsm> : idem.
  * <jsm>-F\left(n\right)-\frac{1}{2} \gt -f\left(n\right) \geq -F\left(n\right)+\frac{1}{2}</jsm> : multiplication par -1 => inversion des inégalités.
  * <jsm>-f\left(n\right)-\frac{1}{2} \leq -F\left(n\right) \lt -f\left(n\right)+\frac{1}{2}</jsm> : pourquoi? définition de <jsm>\lfloor\;\rfloor</jsm>?
  * <jsm>-f\left(n+1\right)-\frac{1}{2} \leq -F\left(n+1\right) \lt -f\left(n+1\right)+\frac{1}{2}</jsm>
  * <jsm>-1 \leq f\left(n+1\right)-f\left(n\right)\lt 1 \lt F\left(n+1\right)-F\left(n\right)\lt f\left(n+1\right)-f\left(n\right)+1\leq 2</jsm>
  * donc <jsm>-1 \lt F\left(n+1\right)-F\left(n\right)\lt 2</jsm> et puisque <jsm>F\left(n+1\right)-F\left(n\right)</jsm> est entier, <jsm>0\leq F\left(n+1\right)-F\left(n\right)\leq 1</jsm>, et la courbe est 8-connexe.

=== 3).  ===

  * <jsm>M=M_2 \Leftrightarrow F\left(x+1\right)=y+1=\lfloor f\left(x+1\right)+\frac{1}{2}</jsm>
  * <jsm>\Leftrightarrow y+1 \leq f\left(x+1\right) +\frac{1}{2} \lt y+2</jsm>
  * <jsm>\Leftrightarrow y+\frac{1}{2} \leq f\left(x+1\right) \lt y + \frac{3}{2} </jsm>
  * <jsm> \displaystyle \Leftrightarrow y+\frac{1}{2} \leq \frac{\left(x+1\right)^2}{4h}</jsm>
  * Soit D(x,y) une fonction de décision telle que pour D < 0 on choisit <jsm>M_1</jsm> et pour <jsm>D\geq 0</jsm> on choisit <jsm>M_2</jsm>? Il faut qu'elle satisfasse la condition 
    * <jsm>D\left(x,y\right)=\left(x+1\right)^2 - \left(y+\frac{1}{2}\right)4h \geq 0</jsm>
    * <jsm>D\left(x,y\right)-D\left(x-1,y-1\right)= \left(x+1\right)^2-2h\left(2y+1\right)-x^2 + 2h\left(2y-1\right) = 2x+1-4h</jsm>
    * <jsm>D\left(x,y\right)-D\left(x-1,y\right)=2x+1</jsm>

=== 5. ===

Au final, nous trouvons l'algorithme suivant :


  x <- 0; y <- 0; D <- 1-2h;
  tantque (x < 2h) faire
    allumePixel (x,y));
    x <- x+1;
    si D >= 0 { y <- y+1;D <- D+2x+1-4h;}
    sinon {D <-D+2x+1;}

==== Navigation ====

[[fain_3|]] [[fain_4|]] [[fain_td2|]]