Algorithme de génération de ligne

Une ligne relie deux points. C'est un élément de base dans les graphiques. Pour tracer une ligne, vous avez besoin de deux points entre lesquels vous pouvez dessiner une ligne. Dans les trois algorithmes suivants, nous référons le point de ligne par $ X_ {0}, Y_ {0} $ et le deuxième point de ligne par $ X_ {1}, Y_ {1} $.

Algorithme DDA

L'algorithme de l'analyseur différentiel numérique (DDA) est l'algorithme de génération de ligne simple qui est expliqué étape par étape ici.

Step 1 - Obtenez l'entrée de deux points d'extrémité $ (X_ {0}, Y_ {0}) $ et $ (X_ {1}, Y_ {1}) $.

Step 2 - Calculez la différence entre deux extrémités.

dx = X1 - X0
dy = Y1 - Y0

Step 3- Sur la base de la différence calculée à l'étape 2, vous devez identifier le nombre d'étapes pour mettre le pixel. Si dx> dy, alors vous avez besoin de plus d'étapes en coordonnée x; sinon en coordonnée y.

if (absolute(dx) > absolute(dy))
   Steps = absolute(dx);
else
   Steps = absolute(dy);

Step 4 - Calculez l'incrément en coordonnée x et coordonnée y.

Xincrement = dx / (float) steps;
Yincrement = dy / (float) steps;

Step 5 - Mettez le pixel en incrémentant avec succès les coordonnées x et y en conséquence et terminez le dessin de la ligne.

for(int v=0; v < Steps; v++)
{
   x = x + Xincrement;
   y = y + Yincrement;
   putpixel(Round(x), Round(y));
}

Génération de ligne de Bresenham

L'algorithme de Bresenham est un autre algorithme de conversion par balayage incrémentiel. Le gros avantage de cet algorithme est qu'il n'utilise que des calculs entiers. Déplacement sur l'axe x par intervalles unitaires et à chaque étape, choisissez entre deux coordonnées y différentes.

Par exemple, comme le montre l'illustration suivante, à partir de la position (2, 3), vous devez choisir entre (3, 3) et (3, 4). Vous souhaitez le point le plus proche de la ligne d'origine.

À la position d'échantillon $ X_ {k} + 1, $ les séparations verticales de la ligne mathématique sont étiquetées comme $ d_ {supérieur} $ et $ d_ {inférieur} $.

D'après l'illustration ci-dessus, la coordonnée y sur la ligne mathématique à $ x_ {k} + 1 $ est -

Y = m ($ X_ {k} $ + 1) + b

Ainsi, $ d_ {supérieur} $ et $ d_ {inférieur} $ sont donnés comme suit -

$$ d_ {inférieur} = y-y_ {k} $$

$$ = m (X_ {k} + 1) + b - Y_ {k} $$

et

$$ d_ {supérieur} = (y_ {k} + 1) - y $$

$ = Y_ {k} + 1 - m (X_ {k} + 1) - b $

Vous pouvez les utiliser pour prendre une décision simple sur le pixel le plus proche de la ligne mathématique. Cette décision simple est basée sur la différence entre les deux positions de pixel.

$$ d_ {inférieur} - d_ {supérieur} = 2m (x_ {k} + 1) - 2y_ {k} + 2b - 1 $$

Remplaçons m par dy / dxdx et dy sont les différences entre les extrémités.

$$ dx (d_ {inférieur} - d_ {supérieur}) = dx (2 \ frac {\ mathrm {d} y} {\ mathrm {d} x} (x_ {k} + 1) - 2y_ {k} + 2b - 1) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + 2dy + 2dx (2b-1) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + C $$

Ainsi, un paramètre de décision $ P_ {k} $ pour le k ème pas le long d'une ligne est donné par -

$$ p_ {k} = dx (d_ {inférieur} - d_ {supérieur}) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + C $$

Le signe du paramètre de décision $ P_ {k} $ est le même que celui de $ d_ {inférieur} - d_ {supérieur} $.

Si $ p_ {k} $ est négatif, alors choisissez le pixel inférieur, sinon choisissez le pixel supérieur.

N'oubliez pas que les changements de coordonnées se produisent le long de l'axe x par pas d'unités, vous pouvez donc tout faire avec des calculs d'entiers. A l'étape k + 1, le paramètre de décision est donné par -

$$ p_ {k +1} = 2dy.x_ {k + 1} - 2dx.y_ {k + 1} + C $$

En soustrayant $ p_ {k} $ de ceci, nous obtenons -

$$ p_ {k + 1} - p_ {k} = 2dy (x_ {k + 1} - x_ {k}) - 2dx (y_ {k + 1} - y_ {k}) $$

Mais, $ x_ {k + 1} $ est identique à $ (xk) + 1 $. Alors -

$$ p_ {k + 1} = p_ {k} + 2dy - 2dx (y_ {k + 1} - y_ {k}) $$

Où, $ Y_ {k + 1} - Y_ {k} $ vaut 0 ou 1 selon le signe de $ P_ {k} $.

Le premier paramètre de décision $ p_ {0} $ est évalué à $ (x_ {0}, y_ {0}) $ est donné comme -

$$ p_ {0} = 2j - dx $$

Maintenant, en gardant à l'esprit tous les points et calculs ci-dessus, voici l'algorithme de Bresenham pour la pente m <1 -

Step 1 - Entrez les deux extrémités de la ligne, en stockant l'extrémité gauche dans $ (x_ {0}, y_ {0}) $.

Step 2 - Tracez le point $ (x_ {0}, y_ {0}) $.

Step 3 - Calculez les constantes dx, dy, 2dy et (2dy - 2dx) et obtenez la première valeur du paramètre de décision comme -

$$ p_ {0} = 2j - dx $$

Step 4 - À chaque $ X_ {k} $ le long de la ligne, en commençant à k = 0, effectuez le test suivant -

Si $ p_ {k} $ <0, le point suivant à tracer est $ (x_ {k} +1, y_ {k}) $ et

$$ p_ {k + 1} = p_ {k} + 2dy $$ Sinon,

$$ (x_ {k}, y_ {k} +1) $$

$$ p_ {k + 1} = p_ {k} + 2dy - 2dx $$

Step 5 - Répétez l'étape 4 (dx - 1) fois.

Pour m> 1, déterminez si vous devez incrémenter x tout en incrémentant y à chaque fois.

Après la résolution, l'équation pour le paramètre de décision $ P_ {k} $ sera très similaire, seuls les x et y de l'équation sont interchangés.

Algorithme du point médian

L'algorithme du point médian est dû à Bresenham qui a été modifié par Pitteway et Van Aken. Supposons que vous ayez déjà placé le point P à la coordonnée (x, y) et que la pente de la ligne soit 0 ≤ k ≤ 1 comme indiqué dans l'illustration suivante.

Vous devez maintenant décider de placer le point suivant à E ou N. Cela peut être choisi en identifiant le point d'intersection Q le plus proche du point N ou E. Si le point d'intersection Q est le plus proche du point N alors N est considéré comme le point suivant; sinon E.

Pour le déterminer, calculez d'abord le point médian M (x + 1, y + ½). Si le point d'intersection Q de la ligne avec la ligne verticale reliant E et N est en dessous de M, alors prenez E comme point suivant; sinon, prenez N comme point suivant.

Afin de vérifier cela, nous devons considérer l'équation implicite -

F (x, y) = mx + b - y

Pour m positif à tout X donné,

  • Si y est sur la ligne, alors F (x, y) = 0
  • Si y est au-dessus de la ligne, alors F (x, y) <0
  • Si y est en dessous de la ligne, alors F (x, y)> 0