Reconnaitre des figures 4-connexes et 8-connexes.

1. ensemble 1 est 4-connexe, et donc 8-connexe (aussi)
2. 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.
3. ensemble 3 est 4-connexe, et donc 8-connexe (aussi).
4. 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.

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);
}

1. Dessiner le segment tracé par cet algorithme pour les points A(0,0) et B(4,3).
2. Indiquer si l'ensemble suivant est un segment tracé grâce à cet algorithme.
3. Quels sont les segments que permet de tracer cet algorithme? Généraliser l'algorithme pour qu'il dessine des segments de toute pente.
4. 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).

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

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

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

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

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).

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);
}

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

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

Nous allons supposer que notre parabole est de la forme y=a x^2 + bx + c et non x = a y^2 + b y +c

• a \times 0^2 + b\times 0 +c = 0 \Rightarrow c=0
• h = a\times \left( 2h \right)^2 + b\times \left( 2h \right) = 4ah^2 + 2bh \quad \Rightarrow \quad 4ah +2b -1 = 0
• On arrive à une équation en deux inconnnues : \displaystyle a=\frac{1-2b}{4a}. Si l'on pose b=0 (l'axe de la parabole sera 0y) on trouve \displaystyle a=\frac{1}{4h} et donc \displaystyle f\left(x\right) = y =\frac{x^2}{4h}

Ensuite, \left(x,\lfloor f\left(x\right) + \frac{1}{2}\rfloor\right) nous fourni l'arrondi à l'entier le plus proche de f(x). Dans cette partie de la courbe, dy = \frac{2x}{4h} \lt \frac{2\times 2h}{4h}= 1 car x\leq 2h. 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 F\left(n\right) = \lfloor f\left(n\right) + \frac{1}{2}\rfloor
• \forall n \in \left[0, 2h-1\right]\;:\; 0 \leq f\left(n+1\right)-f\left(n\right)\leq 1
• F\left(n\right)-\frac{1}{2} \leq f\left(n\right) \lt F\left(n\right)+\frac{1}{2} par la définition de \lfloor\;\rfloor
• F\left(n+1\right)-\frac{1}{2} \leq f\left(n+1\right) \lt F\left(n+1\right)+\frac{1}{2} : idem.
• -F\left(n\right)-\frac{1}{2} \gt -f\left(n\right) \geq -F\left(n\right)+\frac{1}{2} : multiplication par -1 ⇒ inversion des inégalités.
• -f\left(n\right)-\frac{1}{2} \leq -F\left(n\right) \lt -f\left(n\right)+\frac{1}{2} : pourquoi? définition de \lfloor\;\rfloor?
• -f\left(n+1\right)-\frac{1}{2} \leq -F\left(n+1\right) \lt -f\left(n+1\right)+\frac{1}{2}
• -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
• donc -1 \lt F\left(n+1\right)-F\left(n\right)\lt 2 et puisque F\left(n+1\right)-F\left(n\right) est entier, 0\leq F\left(n+1\right)-F\left(n\right)\leq 1, et la courbe est 8-connexe.

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

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;}

fain_3 fain_4 TD2 Remplissage