Algorisme de dibuix de cercles de Bresenham
No és fàcil mostrar un arc suau continu a la pantalla de l'ordinador, ja que la nostra pantalla d'ordinador està feta de píxels organitzats en forma de matriu. Per tant, per dibuixar un cercle a la pantalla d'un ordinador sempre hauríem de triar els píxels més propers d'un píxel imprès perquè puguin formar un arc. Hi ha dos algorismes per fer-ho:
- Algorisme de dibuix de cercles de punt mitjà
- Algorisme de dibuix de cercles de Bresenham
Ja hem comentat el Algorisme de dibuix de cercles de punt mitjà en el nostre post anterior. En aquest post parlarem sobre l'algorisme de dibuix de cercles de Bresenham.
Ambdós algorismes utilitzen la característica clau del cercle que és altament simètric. Així, per a un cercle sencer de 360 graus, el dividirem en 8 parts cada octant de 45 graus. Per fer-ho, utilitzarem l'algoritme del cercle de Bresenham per al càlcul de les ubicacions dels píxels en el primer octant de 45 graus. Se suposa que el cercle està centrat en l'origen. Així, per cada píxel (x y) que calcula dibuixem un píxel en cadascun dels 8 octants del cercle, tal com es mostra a continuació:
Per a un píxel (xy) tots els píxels possibles en 8 octants
Ara veurem com calcular la següent ubicació de píxel a partir d'una ubicació de píxel prèviament coneguda (x y). A l'algorisme de Bresenham en qualsevol punt (x y) tenim dues opcions: triar el següent píxel a l'est, és a dir (x+1 y) o al sud-est, és a dir, (x+1 y-1).
I això es pot decidir utilitzant el paràmetre de decisió d com:
- Si d > 0, llavors (x+1 y-1) s'ha de triar com a píxel següent, ja que estarà més a prop de l'arc.
- sinó (x+1 y) s'ha de triar com a píxel següent.
Ara per dibuixar el cercle per a un radi 'r' i centre determinats (xc yc) començarem des de (0 r) i ens mourem en el primer quadrant fins a x=y (és a dir, 45 graus). Hauríem de partir de la condició inicial enumerada:
d = 3 - (2 * r)
x = 0
y = rAra per a cada píxel farem les següents operacions:
- Estableix els valors inicials de (xc yc) i (x y).
- Establiu el paràmetre de decisió d a d = 3 – (2 * r).
- Truqueu a la funció drawCircle(int xc int yc int x int y).
- Repetiu els passos següents fins que x <= y:
- Si d < 0 set d = d + (4 * x) + 6.
- En cas contrari, estableix d = d + 4 * (x – y) + 10 i disminueix y en 1.
- Incrementar el valor de x.
- Truqueu a la funció drawCircle(int xc int yc int x int y).
funció drawCircle():
CPPA continuació es mostra la implementació C de l'enfocament anterior.
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 ; } Sortida:
Avantatges
- És un algorisme senzill.
- Es pot implementar fàcilment
- Es basa totalment en l'equació del cercle, és a dir, x 2 +y 2 = r 2
Inconvenients
- Hi ha un problema de precisió durant la generació de punts.
- Aquest algorisme no és adequat per a imatges gràfiques complexes i altes.
