Algoritmul liniei Bresenham

Algoritmul de linie Bresenham (de unii numit algoritmul punctului mediu sau chiar cercurile Bresenham ) este un algoritm de rasterizare a liniei . În prezent este cel mai utilizat algoritm pentru rasterizarea liniilor , în principal datorită cererii sale reduse de resurse de calcul.

Descriere

Pentru a înțelege algoritmul , simplificăm problema presupunând că $m={\frac {\Delta y}{\Delta x}}$ ${\ displaystyle m = {\ frac {\ Delta y} {\ Delta x}}}$ ${\ displaystyle m = {\ frac {\ Delta y} {\ Delta x}}}$ este între $0<m<1$ ${\ displaystyle 0 <m <1}$ ${\ displaystyle 0 <m <1}$ .

Să ne imaginăm că suntem la un pas $the$ ${\ displaystyle i}$ $the$ algoritm, adică tocmai am stabilit ce pixel să „pornim”, de exemplu $p_{1}(x_{1},y_{1})$ ${\ displaystyle p_ {1} (x_ {1}, y_ {1})}$ ${\ displaystyle p_ {1} (x_ {1}, y_ {1})}$ .

Acum trebuie să determinăm următorul pixel care să „pornească”, să-l numim $p_{2}(x_{2},y_{2})$ ${\ displaystyle p_ {2} (x_ {2}, y_ {2})}$ ${\ displaystyle p_ {2} (x_ {2}, y_ {2})}$ , unde este $x_{2}=x_{1}+1$ ${\ displaystyle x_ {2} = x_ {1} +1}$ ${\ displaystyle x_ {2} = x_ {1} +1}$ .

Situația este cea prezentată în figura 1, unde din punctul 1 (cel în verde) trebuie să mergem la punctul 2, care poate fi găsit imediat în dreapta, cazul A sau în partea dreaptă sus, cazul B.

figura 1

În cazul A avem $y_{2}=y_{1}$ ${\ displaystyle y_ {2} = y_ {1}}$ ${\ displaystyle y_ {2} = y_ {1}}$ ;
În cazul B avem $y_{2}=y_{1}+1$ ${\ displaystyle y_ {2} = y_ {1} +1}$ ${\ displaystyle y_ {2} = y_ {1} +1}$ .

Să luăm în considerare punctul $M(x_{1}+1,y_{1}+{1 \over 2})$ ${\ displaystyle M (x_ {1} + 1, y_ {1} + {1 \ peste 2})}$ ${\ displaystyle M (x_ {1} + 1, y_ {1} + {1 \ peste 2})}$ (Figura 2), punctul de mijloc între A și B. Dacă linia de rasterizat trece peste, vom evidenția pixelul superior B, altfel pixelul inferior A.

Figura 2

Pentru a determina dacă $M.$ ${\ displaystyle M}$ $M.$ se află sub sau deasupra liniei, luați în considerare forma explicită a ecuației liniei:

$y={\frac {\Delta y}{\Delta x}}\cdot x+q$ ${\ displaystyle y = {\ frac {\ Delta y} {\ Delta x}} \ cdot x + q}$ ${\ displaystyle y = {\ frac {\ Delta y} {\ Delta x}} \ cdot x + q}$

care poate fi rescris sub forma:

$-\Delta x\cdot y+\Delta y\cdot x+\Delta x\cdot q=0$ ${\ displaystyle - \ Delta x \ cdot y + \ Delta y \ cdot x + \ Delta x \ cdot q = 0}$ ${\ displaystyle - \ Delta x \ cdot y + \ Delta y \ cdot x + \ Delta x \ cdot q = 0}$

Toate punctele aparținând liniei trebuie să verifice ecuația. Dar această linie împarte și două jumătăți de plan, cel alcătuit din toate punctele pentru care formula anterioară returnează o valoare pozitivă și cel pentru care returnează o valoare negativă. Un exemplu de jumătate de plan poate fi găsit în figura 3.

Figura 3

Deci, din formula anterioară putem obține valoarea deciziei $d$ ${\ displaystyle d}$ $d$ , înlocuind anunțul $X$ ${\ displaystyle x}$ $X$ și $y$ ${\ displaystyle y}$ $y$ coordonatele din $M(x_{1}+1,y_{1}+1/2)$ ${\ displaystyle M (x_ {1} + 1, y_ {1} +1/2)}$ ${\ displaystyle M (x_ {1} + 1, y_ {1} +1/2)}$ (punctul mediu dintre A și B):

$d=-\Delta x\cdot y_{M}+\Delta y\cdot x_{M}+\Delta x\cdot q$ ${\ displaystyle d = - \ Delta x \ cdot y_ {M} + \ Delta y \ cdot x_ {M} + \ Delta x \ cdot q}$ ${\ displaystyle d = - \ Delta x \ cdot y_ {M} + \ Delta y \ cdot x_ {M} + \ Delta x \ cdot q}$

care va fi:

$d=0$ ${\ displaystyle d = 0}$ ${\ displaystyle d = 0}$ , dacă punctul se află pe linia dreaptă; în acest caz putem alege indiferent fie punctul A, fie punctul B;
$d<0$ ${\ displaystyle d <0}$ ${\ displaystyle d <0}$ , dacă punctul este deasupra liniei; în acest caz luăm punctul A;
$d>0$ ${\ displaystyle d> 0}$ ${\ displaystyle d> 0}$ , dacă punctul este sub linie; în acest caz luăm punctul B.

În algoritm ar trebui să știm de fiecare dată dacă $d$ ${\ displaystyle d}$ $d$ este pozitiv sau negativ.

Să presupunem că am ales punctul A, în acest caz punctul nostru de plecare $p$ ${\ displaystyle p}$ $p$ Și $p(x_{1}+1,y_{1})$ ${\ displaystyle p (x_ {1} + 1, y_ {1})}$ ${\ displaystyle p (x_ {1} + 1, y_ {1})}$ , iar noul nostru punct de mijloc M este $M(x_{1}+2,y_{1}+{1 \over 2})$ ${\ displaystyle M (x_ {1} + 2, y_ {1} + {1 \ peste 2})}$ ${\ displaystyle M (x_ {1} + 2, y_ {1} + {1 \ peste 2})}$ . În schimb, noua valoare a $d$ ${\ displaystyle d}$ $d$ Și:

$d_{new}=-\Delta x\cdot y_{M}+\Delta y\cdot x_{M}+\Delta x\cdot q=-\Delta x\cdot \left(y_{1}+{\frac {1}{2}}\right)+\Delta y\cdot (x_{1}+2)+\Delta x\cdot q$ ${\ displaystyle d_ {new} = - \ Delta x \ cdot y_ {M} + \ Delta y \ cdot x_ {M} + \ Delta x \ cdot q = - \ Delta x \ cdot \ left (y_ {1} + {\ frac {1} {2}} \ right) + \ Delta y \ cdot (x_ {1} +2) + \ Delta x \ cdot q}$ ${\ displaystyle d_ {new} = - \ Delta x \ cdot y_ {M} + \ Delta y \ cdot x_ {M} + \ Delta x \ cdot q = - \ Delta x \ cdot \ left (y_ {1} + {\ frac {1} {2}} \ right) + \ Delta y \ cdot (x_ {1} +2) + \ Delta x \ cdot q}$

Să încercăm să scădem din noua valoare a $d$ ${\ displaystyle d}$ $d$ cel Bătrân:

$d_{new}-d_{old}=-\Delta x\cdot \left(y_{1}+{\frac {1}{2}}\right)+\Delta y\cdot (x_{1}+2)+\Delta x\cdot q-\left(-\Delta x\cdot \left(y_{1}+{\frac {1}{2}}\right)+\Delta y\cdot (x_{1}+1)+\Delta x\cdot q\right)$ ${\ displaystyle d_ {new} -d_ {old} = - \ Delta x \ cdot \ left (y_ {1} + {\ frac {1} {2}} \ right) + \ Delta y \ cdot (x_ {1 } +2) + \ Delta x \ cdot q- \ left (- \ Delta x \ cdot \ left (y_ {1} + {\ frac {1} {2}} \ right) + \ Delta y \ cdot (x_ {1} +1) + \ Delta x \ cdot q \ right)}$ ${\ displaystyle d_ {new} -d_ {old} = - \ Delta x \ cdot \ left (y_ {1} + {\ frac {1} {2}} \ right) + \ Delta y \ cdot (x_ {1 } +2) + \ Delta x \ cdot q- \ left (- \ Delta x \ cdot \ left (y_ {1} + {\ frac {1} {2}} \ right) + \ Delta y \ cdot (x_ {1} +1) + \ Delta x \ cdot q \ right)}$

Simplificând obținem:

$d_{new}-d_{old}=\Delta y$ ${\ displaystyle d_ {new} -d_ {old} = \ Delta y}$ ${\ displaystyle d_ {new} -d_ {old} = \ Delta y}$

Deci, avem o modalitate de a obține noua valoare $d$ ${\ displaystyle d}$ $d$ într-un mod mai simplu față de cel vechi, fără a reface de fiecare dată toate calculele.

Acum trebuie să facem ipoteza pentru cazul în care a fost ales punctul B. Avem noile noastre puncte:

$p(x_{1}+1,y_{1}+1)$ ${\ displaystyle p (x_ {1} + 1, y_ {1} +1)}$ ${\ displaystyle p (x_ {1} + 1, y_ {1} +1)}$ ;
$M(x_{1}+2,y_{1}+1+{1 \over 2})=M(x_{1}+2,y_{1}+{3 \over 2})$ ${\ displaystyle M (x_ {1} + 2, y_ {1} +1+ {1 \ over 2}) = M (x_ {1} + 2, y_ {1} + {3 \ over 2})}$ ${\ displaystyle M (x_ {1} + 2, y_ {1} +1+ {1 \ over 2}) = M (x_ {1} + 2, y_ {1} + {3 \ over 2})}$ ;

și noua noastră valoare $d$ ${\ displaystyle d}$ $d$ :

$d_{new}=-\Delta x\cdot \left(y_{1}+{\frac {3}{2}}\right)+\Delta y\cdot (x_{1}+2)+\Delta x\cdot q$ ${\ displaystyle d_ {new} = - \ Delta x \ cdot \ left (y_ {1} + {\ frac {3} {2}} \ right) + \ Delta y \ cdot (x_ {1} +2) + \ Delta x \ cdot q}$ ${\ displaystyle d_ {new} = - \ Delta x \ cdot \ left (y_ {1} + {\ frac {3} {2}} \ right) + \ Delta y \ cdot (x_ {1} +2) + \ Delta x \ cdot q}$

Repetăm scăderea:

$d_{new}-d_{old}=-\Delta x\cdot \left(y_{1}+{\frac {3}{2}}\right)+\Delta y\cdot (x_{1}+2)+\Delta x\cdot q-\left(-\Delta x\cdot \left(y_{1}+{\frac {1}{2}}\right)+\Delta y\cdot (x_{1}+1)+\Delta x\cdot q\right)$ ${\ displaystyle d_ {new} -d_ {old} = - \ Delta x \ cdot \ left (y_ {1} + {\ frac {3} {2}} \ right) + \ Delta y \ cdot (x_ {1 } +2) + \ Delta x \ cdot q- \ left (- \ Delta x \ cdot \ left (y_ {1} + {\ frac {1} {2}} \ right) + \ Delta y \ cdot (x_ {1} +1) + \ Delta x \ cdot q \ right)}$ ${\ displaystyle d_ {new} -d_ {old} = - \ Delta x \ cdot \ left (y_ {1} + {\ frac {3} {2}} \ right) + \ Delta y \ cdot (x_ {1 } +2) + \ Delta x \ cdot q- \ left (- \ Delta x \ cdot \ left (y_ {1} + {\ frac {1} {2}} \ right) + \ Delta y \ cdot (x_ {1} +1) + \ Delta x \ cdot q \ right)}$

Simplificând obținem:

$d_{new}-d_{old}=-\Delta x+\Delta y$ ${\ displaystyle d_ {new} -d_ {old} = - \ Delta x + \ Delta y}$ ${\ displaystyle d_ {new} -d_ {old} = - \ Delta x + \ Delta y}$

În rezumat, i s-a dat o valoare $d_{i}$ ${\ displaystyle d_ {i}}$ $din}$ :

$d_{i+1}=\left\{{\begin{matrix}d_{i}-\Delta x+\Delta y,&{\mbox{se }}d_{i}>0\\d_{i}+\Delta y,&{\mbox{se }}d_{i}<0\end{matrix}}\right.$ ${\ displaystyle d_ {i + 1} = \ left \ {{\ begin {matrix} d_ {i} - \ Delta x + \ Delta y și {\ mbox {se}} d_ {i}> 0 \\ d_ {i} + \ Delta y și {\ mbox {se}} d_ {i} <0 \ end {matrix}} \ right.}$ ${\ displaystyle d_ {i + 1} = \ left \ {{\ begin {matrix} d_ {i} - \ Delta x + \ Delta y și {\ mbox {se}} d_ {i}> 0 \\ d_ {i} + \ Delta y și {\ mbox {se}} d_ {i} <0 \ end {matrix}} \ right.}$

Trebuie doar să știm valoarea $d_{0}$ ${\ displaystyle d_ {0}}$ ${\ displaystyle d_ {0}}$ ; amintindu-ne de formula de calculat $d$ ${\ displaystyle d}$ $d$ și luându-l ca punct $p$ ${\ displaystyle p}$ $p$ , $p_{0}(x_{0},y_{0})$ ${\ displaystyle p_ {0} (x_ {0}, y_ {0})}$ ${\ displaystyle p_ {0} (x_ {0}, y_ {0})}$ sau o extremă a liniei, avem:

$d=-\Delta x\cdot \left(y_{0}+{\frac {1}{2}}\right)+\Delta y\cdot (x_{0}+1)+\Delta x\cdot q=-\Delta x\cdot y_{0}+\Delta y\cdot x_{0}+\Delta x\cdot q+\left(-{\frac {\Delta x}{2}}+\Delta y\right)$ ${\ displaystyle d = - \ Delta x \ cdot \ left (y_ {0} + {\ frac {1} {2}} \ right) + \ Delta y \ cdot (x_ {0} +1) + \ Delta x \ cdot q = - \ Delta x \ cdot y_ {0} + \ Delta y \ cdot x_ {0} + \ Delta x \ cdot q + \ left (- {\ frac {\ Delta x} {2}} + \ Delta y \ dreapta)}$ ${\ displaystyle d = - \ Delta x \ cdot \ left (y_ {0} + {\ frac {1} {2}} \ right) + \ Delta y \ cdot (x_ {0} +1) + \ Delta x \ cdot q = - \ Delta x \ cdot y_ {0} + \ Delta y \ cdot x_ {0} + \ Delta x \ cdot q + \ left (- {\ frac {\ Delta x} {2}} + \ Delta y \ dreapta)}$

În pasaj am scos în evidență valorile $+1/2$ ${\ displaystyle +1/2}$ $+1/2$ Și $+1$ ${\ displaystyle +1}$ $+1$ . Prima parte a formulei corespunde ecuației liniei aplicate unui punct de pe linie, deci știm că va fi egală cu zero. În cele din urmă rămâne:

$d_{0}=-{\frac {\Delta x}{2}}+\Delta y$ ${\ displaystyle d_ {0} = - {\ frac {\ Delta x} {2}} + \ Delta y}$ ${\ displaystyle d_ {0} = - {\ frac {\ Delta x} {2}} + \ Delta y}$

Algoritm

Din toate aceste formule putem obține în cele din urmă algoritmul: Având două puncte $p_{1}$ ${\ displaystyle p_ {1}}$ $p_ {1}$ Și $p_{2}$ ${\ displaystyle p_ {2}}$ $p_ {2}$ , cu coordonatele (x ₁ , y ₁ ) și (x ₂ , y ₂ ):

 DX = x ₂ - x ₁
DY = y ₂ - y ₁

// valoarea noastră d ₀
d = - 1/2 * DX + DY

// atribuiți coordonatele de pornire
x = x ₁
y = y ₁
draw_point (x, y)

în timp ce x < x ₂ {
       dacă (d> = 0) {
        d = d -DX + DY;
        y = y + 1;
        x = x + 1;
       }
       altceva {
        d = d + DY;
        x = x + 1;
       }
       draw_point (x, y)
}

Observăm că algoritmul are numere în virgulă mobilă, care necesită resurse de calcul, o idee pentru a evita această precizie este de a dubla valorile $d$ ${\ displaystyle d}$ $d$ :

 DX = x ₂ - x ₁
DY = y ₂ - y ₁

// valoarea noastră d ₀
d = - DX + 2 * DY

// atribuiți coordonatele de pornire
x = x ₁
y = y ₁
draw_point (x, y)

în timp ce x < x ₂ {
       dacă (d> = 0) {
        d = d -2 * DX + 2 * DY;
        y = y + 1;
        x = x + 1;
       }
       altceva {
        d = d + 2 * DY;
        x = x + 1;
       }
       draw_point (x, y)
}

Apoi am obținut un algoritm care funcționează cu numere, numere întregi și simplu de implementat. Dacă am avea x ₁ > x ₂ atunci în loc să creștem $X$ ${\ displaystyle x}$ $X$ o micșorăm în timp ce valorile deciziei rămân aceleași, chiar dacă y ₁ > y ₂ valorile deciziei nu variază, deoarece linia presupune o pantă de valoare opusă celei cazului y ₁ <y ₂ și x ₁ <x ₂ , doar creșterea de $y$ ${\ displaystyle y}$ $y$ că, în loc să crească, scade și valoarea deciziei rămâne neschimbată, deoarece tratăm linia atât dacă x ₁ > x _{2, cât} și y ₁ > y ₂ ca și cum ar fi în primul caz studiat, în primul caz ambele DX și DY sunt mai mari de zero, atunci vom lua valoarea absolută, mai jos obținem algoritmul:

 DX = x ₂ - x ₁
DY = y ₂ - y ₁

// pentru a nu scrie întotdeauna valorile absolute Schimb DY și DX cu alte variabile
a = abs (DY)
b = -abs (DX)

// valoarea noastră d ₀
d = 2 * a + b
// atribuiți coordonatele de pornire
x = x ₁
y = y ₁
draw_point (x, y)

// seq sunt măririle lui x și y
s = 1
q = 1
dacă (x ₁ > x ₂ ) q = -1
dacă (y ₁ > y ₂ ) s = -1

în timp ce x < x ₂ {
       dacă (d> = 0) {
        d = 2 * (a + b) + d
        y = y + s;
        x = x + q;
       }
       altceva {
        d = 2 * a + d;
        x = x + q;
       }
       draw_point (x, y)
}

Cu aceasta am obținut liniile cu valoarea de $|m|<1$ ${\ displaystyle | m | <1}$ ${\ displaystyle | m | <1}$ . Cu valoare de $|m|>1$ ${\ displaystyle | m |> 1}$ ${\ displaystyle | m |> 1}$ trebuie să facem unele modificări deoarece | DY / DX |> 1 și acest lucru se întâmplă când DY> DX în acest caz aproximarea liniei cu algoritmul pe care l-am găsit este foarte proastă, deoarece doar DX este tratat ca o buclă, avem pentru a generaliza algoritmul în cazurile în care putem avea DY> DX. Dacă rotim linia cu 90 de grade putem vedea că este ca și cum ar fi trebuit să aplicăm același algoritm anterior cu coordonatele celor două puncte pentru a alege x în loc de $y$ ${\ displaystyle y}$ $y$ , atunci, în acest caz, tratăm DY ca DX și DY ca DX, deci trebuie doar să schimbăm DX și DY și să menținem valorile deciziei neschimbate, în buclă putem avea DX> DY sau DY> DX, dar, din moment ce îl schimbăm, va fi întotdeauna fie DX> DY, atunci în cazul în care d> = 0 vom avea că ambele coordonate cresc sau scad cu 1, deci acest caz rămâne același, cazul se schimbă în schimb $d<0$ ${\ displaystyle d <0}$ ${\ displaystyle d <0}$ în acest caz, de fapt, trebuie să decidem dacă creștem numai $X$ ${\ displaystyle x}$ $X$ sau numai $y$ ${\ displaystyle y}$ $y$ pe baza cazului pe care îl avem. În cazul normal crește $X$ ${\ displaystyle x}$ $X$ , în cazul DY> DX, acestea se schimbă și cresc $y$ ${\ displaystyle y}$ $y$ , din această logică putem deriva algoritmul pentru liniile generale care este următorul:

 swap = 0;
DX = x ₂ - x ₁ ;
DY = y ₂ - y ₁ ;

// deoarece schimb DY și DX, am întotdeauna DX> = DY, așa că pentru a ști ce coordonată trebuie să schimb, folosesc o variabilă
if (abs (DX) < abs (DY)) {
   swap (DX, DY);
   swap = 1;
}

// pentru a nu scrie întotdeauna valorile absolute Schimb DY și DX cu alte variabile
a = abs (DY);
b = -abs (DX);

// atribuiți coordonatele de pornire
x = x ₁ ;
y = y ₁ ;

// valoarea noastră d ₀
d = 2 * a + b;

// seq sunt măririle / micșorările lui x și y
q = 1;
s = 1;
dacă (x ₁ > x ₂ ) q = -1;
dacă (y ₁ > y ₂ ) s = -1;
draw_point (x, y);
draw_point (x ₂ , y ₂ );
pentru (k = 0; k < -b; k + = 1) {
   dacă (d> 0) {
       x = x + q; y = y + s;
       d = d + 2 * (a + b);
   }
   altceva {
       x = x + q;
       if (swap == 1) {y = y + s; x = x - q; }
       d = d + 2 * a;
   }
   draw_point (x, y);
}

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe algoritmul Bresenham Line

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică