Algoritmul de desenare a cercurilor lui Bresenham
Nu este ușor să afișați un arc neted continuu pe ecranul computerului, deoarece ecranul computerului nostru este format din pixeli organizați sub formă de matrice. Deci, pentru a desena un cerc pe ecranul unui computer, ar trebui să alegem întotdeauna cei mai apropiați pixeli dintr-un pixel imprimat, astfel încât să poată forma un arc. Există doi algoritmi pentru a face acest lucru:
- Algoritmul de desenare a cercului Mid-Point
- Algoritmul de desen al cercului lui Bresenham
Am discutat deja despre Algoritmul de desenare a cercului Mid-Point în postarea noastră anterioară. În această postare vom discuta despre algoritmul de desenare al cercului lui Bresenham.
Ambii acești algoritmi folosesc caracteristica cheie a cercului că este foarte simetric. Deci pentru întregul cerc de 360 de grade îl vom împărți în 8 părți fiecare octant de 45 de grade. Pentru a face acest lucru, vom folosi algoritmul cerc al lui Bresenham pentru calcularea locațiilor pixelilor din primul octant de 45 de grade. Se presupune că cercul este centrat pe origine. Deci, pentru fiecare pixel (x y) pe care îl calculează, desenăm câte un pixel în fiecare dintre cei 8 octanți ai cercului, așa cum se arată mai jos:
Pentru un pixel (xy) toți pixelii posibili în 8 octanți
Acum vom vedea cum să calculăm următoarea locație a pixelului dintr-o locație a pixelului cunoscută anterior (x y). În algoritmul lui Bresenham în orice punct (x y) avem două opțiuni fie de a alege următorul pixel în est, adică (x+1 y), fie în sud-est, adică (x+1 y-1).
Și acest lucru poate fi decis utilizând parametrul de decizie d ca:
- Dacă d > 0, atunci (x+1 y-1) trebuie să fie ales ca următorul pixel, deoarece va fi mai aproape de arc.
- altfel (x+1 y) va fi ales ca următorul pixel.
Acum, pentru a desena cercul pentru o rază dată „r” și centru (xc yc) Vom începe de la (0 r) și ne vom deplasa în primul cadran până la x=y (adică 45 de grade). Ar trebui să începem de la condiția inițială enumerată:
d = 3 - (2 * r)
x = 0
y = rAcum pentru fiecare pixel vom face următoarele operații:
- Setați valorile inițiale pentru (xc yc) și (x y).
- Setați parametrul de decizie d la d = 3 – (2 * r).
- Apelați funcția drawCircle(int xc int yc int x int y).
- Repetați pașii următori până la x <= y:
- Dacă d < 0 set d = d + (4 * x) + 6.
- În rest, setați d = d + 4 * (x – y) + 10 și reduceți y cu 1.
- Creșteți valoarea lui x.
- Apelați funcția drawCircle(int xc int yc int x int y).
Funcția drawCircle():
CPPMai jos este implementarea C a abordării de mai sus.
CPP#include #include // Function to put pixels // at subsequence points void drawCircle ( int xc int yc int x int y ){ putpixel ( xc + x yc + y RED ); putpixel ( xc - x yc + y RED ); putpixel ( xc + x yc - y RED ); putpixel ( xc - x yc - y RED ); putpixel ( xc + y yc + x RED ); putpixel ( xc - y yc + x RED ); putpixel ( xc + y yc - x RED ); putpixel ( xc - y yc - x RED ); } // Function for circle-generation // using Bresenham's algorithm void circleBres ( int xc int yc int r ){ int x = 0 y = r ; int d = 3 - 2 * r ; drawCircle ( xc yc x y ); while ( y >= x ){ // check for decision parameter // and correspondingly // update d y if ( d > 0 ) { y -- ; d = d + 4 * ( x - y ) + 10 ; } else d = d + 4 * x + 6 ; // Increment x after updating decision parameter x ++ ; // Draw the circle using the new coordinates drawCircle ( xc yc x y ); delay ( 50 ); } } int main () { int xc = 50 yc = 50 r = 30 ; int gd = DETECT gm ; initgraph ( & gd & gm '' ); // initialize graph circleBres ( xc yc r ); // function call return 0 ; } Ieșire:
Avantaje
- Este un algoritm simplu.
- Poate fi implementat cu ușurință
- Se bazează în totalitate pe ecuația cercului, adică x 2 +y 2 =r 2
Dezavantaje
- Există o problemă de precizie la generarea punctelor.
- Acest algoritm nu este potrivit pentru imagini grafice complexe și înalte.
