Benjamin Dupont et Jean-Jacques BOURDIN
Benjamin.Dupont NOSPAM @ univ-paris8.fr
(enlever le NO Spam)
jj NOSPAM @ up8.edu
(enlever le NO Spam)
Présentation et Complexité
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 peut efficace. Jack Bresenham a présenté un travail fort différent en 1962 (publié en 1965).
L‘idée principale est de trouver une mesure de l‘écart entre un point et le point qui devrait être juste. 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;
}
}
}
|
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 |
- 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. |
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]
l’algorithme suivant peut ê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.
Dernière mise à jour : 3/10/2022 (19h)