De la droite discrète

jj.up8.site/droites

Attention, j’ai probablement fait des erreurs en recopiant, de toute façon le prof l’a noté en gros sur son site

Table des matières

• Définition
• De l’évidence à la référence
• Améliorations
• PGCD
• Chercher ailleurs et autrement
  • “Sous les pavés”
  • Euclide et applications
    • Dulucq et Bourdin
    • Green et Pitteway
    • Berstel
  • Plages (Spans)
  • Récapitulation et algorithme rapide

Définition

En maths, une droite est un objet définie car il passe par 2 points et qu’il est infini dans les 2 sens.

En info, c’est un ensemble de pixels qui ont la qualité d’être proche de la droite réelle relativement proche de la droite réel (celle des maths), ces pixels forment un chemin biconnexe.

void droite (int x0, int y0, int x1, int y1) {
  for (int x = x0; x <= x1; x++) {
     flat yf = (float) (x - x0) * (y1 - y0);
     yf /= (x1 - x0);
     yf += y0;
     int y = (int) (yf + .5);
     affiche(x,y);
  }
}
 
Copier

$$\frac{x-x_{p}}{x_{q} - x_{p}} = \frac{y - y_{p}}{y_{q} - y_{p}}$$
$$y = y_{p} + \frac{(x-x_{p})(y_{q} - y_{p})}{x_{q} - x_{p}}$$

De l’évidence à la référence

$$|y-y_{n}| > |y+1 - y_{2}| \Rightarrow y++$$
$$y_{2} = \frac{x\times dy}{dx}$$
$$\underbrace{\left| y - \frac{x\times dy}{dx} \right|}_A > \underbrace{\left| y+1 - \frac{x\times dy}{dx} \right|}_B \Rightarrow y++$$
On a donc $A > B \Rightarrow 0 > A+B$

Il y ça aussi :
$$A + B < 0 \Rightarrow y++$$
$$2y + 1 - \frac{2x\times dy}{dx} < 0 \Rightarrow y++$$
$$\underbrace{2y\times dx + dx - 2x \times dx}_{\text{delta(x, y)}} < 0 \Rightarrow y++$$

delta(x+1, y)   = delta(x, y) - 2dy
delta(x+1, y+1) = delta(x, y) - 2dy - 2dx
 
Copier

En C :

void droitebr(int dx, int dy) {
    int delta, incD, incH;
    incH = dy << 1;
    delta = incH - dx;
    incD = delta - dx;
    for (int x = 0, y = 0; x <= dx; ++x) {
        affiche(x, y);
        if (delta > 0) {
            y++;
            delta += incD;
        } else {
            delta = incH;
        }
    }
}
 
Copier

Améliorations

Optimisation de l’algorithme en coupant en 2 le problème, et donc en faisant un pas de 2 dans la boucle-for. Pareil avec un pas de 3 et un pas de 4.

• Rappel pour la droitebr :
  $$\begin{cases} \text{delta}(x, y) = 2xdy - 2ydx - dx \\\\ \text{si delta} >= 0 \text{ alors } y++ \end{cases}$$

Alors pour le pas de 2 :
$$\text{delta}(x+2, y) = 2xdy + 2ydx + 4dy - dx$$
$$delta(x+1, y) = delta(x + 2, y) - 2dy$$

if (delta >= 0) {
	if (delta - 2dy >= 0) {
Copier

Pour le pas de 3, c’est toujours la même équation, on adapte juste l’équation avec un $x+3$, par contre il peut pas avoir 2 partie oblique consécutives (conséquence de propriété, cf. plus bas dans le cours).

On fait *4 pour y parce que on a un pas de 2 pour x, donc x croit 2 fois plus vite, donc pour y il faut *2 aussi, donc *4

Il y a ensuite le pas adaptaif, le prof explique ça comme quand on monte une pente, on fait des plus grands pas quand on monte, bah là c’est pareil mais à l’envers. Dans notre cas de la droite, on regarde si la pente est importante, dans ce cas on fait des petits pas, et si la pente est petite genre plate, on fait des grands pas.

PGCD

Angel et Morrison disent qu’ils peuvent tout simplifier et aller plus vite.
Avec $y = \frac{x \times dy}{dx}$, ils se demandent si ils pourrait pas simplifier en calculant le PGCD, par exemple si $y = \frac{22}{6} = \frac{11}{3}$.
Malheureusement 60% du temps on a un PGCD qui vaut 1, mais 40% du temps le PGCD c’est 10.

Chercher ailleurs et autrement

“Sous les pavés”

Citation de Wu

Sur 8 mouvements possible, seulement 2 sont utilisés

There are at most two basic directions and these ones can differ only by unity, modulo eight.

Sur ces 2 mouvements, l’un apparaît toujours de façon solitaire, l’autre apparaît de façon groupé (le prof appelle ça une plage)

One of these values always occurs “singly”.

Le pas solitaire est aussi bien répartie que possible, c’est à dire qu’ils peuvent pas être tous regroupés au même endroit, ils doivent être dispersés (autrement dit : les plages ont toutes la même longueur à 1 près)

Successive occurrences of the principal direction occurring singly are as uniformly spaced as possible.

Euclide et applications

Dulucq et Bourdin

Donc par exemple :

• $|w| = dx$

• $|w|_{1} = dy$

• $|w|_{0} = dx-dy$

• Nombre de plages = $dy$

• Longue plages = $\begin{cases} \frac{dx-dy}{dy} \\\\ \frac{dx-dy}{dy} + 1 \end{cases}$

  • Seulement des plages courtes : $dyx \frac{dx-dy}{dy}$ $\Rightarrow$ 0 utilisés
    Il en reste $dx-dy - dyx \frac{dx-dy}{dy}$, qui est le nombre de plages longues

  • $\frac{dx-dy}{dy} \texttt{-=} \frac{dx}{dy}$, le nombre de plages courtes est $\frac{dx-dy}{dy}$

• $\varphi_{n}(0) = O^{n+1}1$

• $\varphi_{n}(1) = O^{n}1$

• $w(dxdy)=\varphi(w(p-q))$

• $n = \frac{dx-dy}{dy} ; p = dy ; q = dy - \frac{dx}{dy}$

• $\varphi_{m}(O) = 0\ 1^{m}$

• $\varphi_{m}(1) = 0\ 1^{m+1}$

• $w(x+dy) = \Psi_{n}(w(p, q))$

• $m = \frac{dy}{dx+dy} ; p = dx-dy ; q = dy-dy \mod (dx-dy)$

Green et Pitteway

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

Berstel

W   = 00100010001
W'  = 01000100010
W'' = 10010001000
 
Copier

C’est conjugés

• $\exists f ; w'f = fw$
• $\exists g ; w'g = gw'$
• $|f| = l$
• $dy \times l + \frac{dx}{2} \equiv 0$ (dx)
• $3\Delta l + \frac{11}{2} mod 11 = 0$
• $(3l + 5) mod 11 = 0$
• $l$ peut être égale à $2$, $-9$, etc… le plus intéressant étant le plus petit, soit $2$

Fraction continue
$\frac{3}{11}= [0, 3, 1, 2]$, ça peut s’écrire aussi comme ça : $a+\frac{1}{b+\frac{1}{c+\frac{1}{d+\frac{1}{e+\frac{1}{f+\frac{1}{g+\frac{1}{h+\frac{1}{i+\frac{1}{j+\frac{1}{k+\frac{1}{\dots}}}}}}}}}}}$,
Soit $[a, b, c, d, e, f, g, h, i, j, k]$

• $\frac{dx}{dy}\Rightarrow 0$

• $\frac{v}{u} = \frac{1}{\frac{u}{v}} = \frac{1}{\frac{u}{v} + \frac{\frac{u}{v}}{v}}$

• $w_{0} = 0$

• $w_{1} = O^{u_{i-1}}1$

• $w_{2} = w^{u}\_{i-1} w_{i-2}$, $i$ impair

• $w_{3} = w_{i-2} \times w^{u}_{i-1}$, $i$ pair

• $w_{0} = 0$

• $w_{1} = 001$

• $w_{2} = 0001$

• $w_{3} = 00010001001$

Plages (Spans)

• $w_{0} = 0$
• $w_{dx} = 1$
• $w_{i} = w_{dx}\dots$

$\Rightarrow$ Symétrie interne

• $w_{i}(u, v) = w_{v}(u, u-v)$ sauf pour $w_{0}$ et $w_{n}$ (le premier et le dernier)
  $$2dy > dx$$

Récapitulation et algorithme rapide

• PGCD
• Pas de 2
• Symétrie interne
• Plage
• Partie basse de l’octant
  $$\approx 20x \text{ bresenham}$$