Jean-Jacques BOURDIN
jj NOSPAM @ up8.edu
(enlever le NO Spam)
De la Droite Discrète
De droite il n'est pas question, seulement de chemin discret approximant un segment de droite entre deux points, oui.
It‘s not a straight line we'll be working on, only a discrete path between two given points.
Notons qu‘on peut ne s‘intéresser qu‘au seul premier octant, les valeurs dans les autres octants sont obtenues par symétrie.
void droite (int x0, int y0, int x1, int y1) {
int x, y;
float yf;
for (x = x0; x <= x1; x++) {
yf = (float) (x - x0) * (y1 - y0);
yf /= (x1 - x0);
yf += y0;
y = (int) (yf + 0.5); /* approximation à l’entier le plus proche*/
affiche(x,y);
}
}
|
C‘est à la fois simple et peu efficace. Jack Bresenham a présenté un travail fort différent en 1963 (publié en 1965).
L‘idée principale est de trouver une mesure de l‘écart entre un point et le point précis qui devrait être affiché. En x la valeur réelle de y doit êtreyr = (x * dy) / dxSi vous avez le choix entre y et y+1, valeurs entières, il faut comparer :
Si | y - yr | > | y + 1 - yr | alors il faut prendre y + 1 comme nouvelle valeur.
Il ne reste plus alors qu'à étuder cette inégalité, la simplifier et comprendre qu‘elle est équivalente à
delta (x,y) = 2 * x * dy - 2 * y * dx - dx
Si delta > 0 y++
de là l'algorithme suivant :
void droite_br (int u, int v) {
/* u est dx, v est dy */
int x, y, delta, incD, incH;
incH = v << 1;
delta = incH - u;
incD = delta - u;
for (x = 0, y = 0; x <= u; x++) {
affiche(x, y);
if (delta > 0) {
y++;
delta += incD;
}
else {
delta += incH;
}
}
}
|
Améliorer la référence
Pour réussir ce programme, il "suffit" de remarquer que la fonction delta reste la même
delta (x,y) = 2 * x * dy - 2 * y * dx - dx
Il suffit donc de compter que, quand on regarde en x+2, on calcule delta(x+2,y) qui se déduit assez facilement de delta, non ?
Si on est dans la partie haute de l‘octant, il faut regarder delta(x+2, y+1)
Avez-vous encore besoin d‘aide pour écrire cette fonction ?
Vous trouverez ici le TP sur les droites.
Ils annoncent être trois fois plus rapides que Bresenham. Comme le pgcd moyen est 4, ce serait un résultat un peu faible. Le problème est que le pgcd moyen est bien environ 4 mais plus de 60% des couples d'entiers ont un pgcd égal à 1. Pour 60% des couples, il n'y a aucune accélération. Donc le temps passé à faire des calculs ne peut pas être inférieur à 60% du temps initial !
Il faut rajouter à cela le calcul du pgcd et les 40% de couples de nombres pour lesquels l'accélération est forte (10). On doit être à plus de 64% du temps initial. L'accélération est forte, sans doute une vitesse de 1.5, ce qui est très faible par rapport à ce qui est annoncé.
White.local: a.out 1001 le nombre de gcd valant 1 est 608383 le nombre de gcd different de 1 est 393618 soit 39.283194 % la moyenne de tous les gcd est 3.833826 la moyenne des gcd non un est 9.759455 |
Chercher ailleurs et autrement
- There are at most two basic directions and these ones can differ only by unity, modulo eight. - One of these values always occurs “singly”. - Successive occurrences of the principal direction occurring singly are as uniformly spaced as possible. |
Notons 0 et 1 ces deux directions, la droite suit donc un chemin décrit par un mot de l‘alphabet {0,1}. Notons ce mot w(dx,dy).
droite (dx, dy) {
dx -= dy;
s = "0";
t = "1";
while (dx != dy) {
if (dx > dy) {
dx -= dy;
t = s . t;
}
else {
dy -= dx;
s = s . t;
}
}
return ( s . t ) ^dx;
}
La version suivante calcule la droite "meilleure approximation".
droitebest (dx, dy) {
dx -= dy;
s = "0";
t = "1";
while (dx != dy) {
if (dx > dy) {
dx -= dy;
t = s . t ^(-1);
}
else {
dy -= dx;
s = t . s ^(-1);
}
}
return ( s . t ^ (-1) ) ^dx;
}
dy/dx = [u0; u1, u2, u3, ..., un]
on pourra se référer à la page wikipedia sur les séries de fractions continues.
L’algorithme suivant peut alors être utilisé.w(0) = 0 w(1) = 0^(u1-1) . 1 w(i) = w(i-1)^ui . w(i-2) (i impair) w(i) = w(i-2) . w(i-1)^ui (i pair). est l’opérateur de concaténation tandis que "w^n" est la duplication n fois du mot w. Exemple d’utilisation : soit la droite de pente 3/11. La décomposition est [0; 3, 1, 2]. On a :
w(0) = 0 w(1) = 0 0 1 w(2) = 0 0 0 1 w(3) = 0 0 0 1 0 0 0 1 0 0 1Reste à savoir comment on obtient la décomposition d’une fraction en série de fractions continues.
Plages (Spans)
Récapitulation et algorithme rapide
De tout cela découle un algorithme particulièrement rapide (près de 20 fois plus rapide que celui de Bresenham en 1965), qui est présenté dans cet article à Eurographics, en 1999.Dernière mise à jour : 2/10/2024 (19h)