Algorytm rysowania okręgu Bresenhama
Nie jest łatwo wyświetlić ciągły, gładki łuk na ekranie komputera, ponieważ ekran naszego komputera składa się z pikseli zorganizowanych w formie matrycy. Aby więc narysować okrąg na ekranie komputera, należy zawsze wybrać z wydrukowanego piksela najbliższe piksele, tak aby utworzyły łuk. Można to zrobić na dwa algorytmy:
- Algorytm rysowania okręgu w punkcie środkowym
- Algorytm rysowania okręgu Bresenhama
Omówiliśmy już Algorytm rysowania okręgu w punkcie środkowym w naszym poprzednim poście. W tym poście omówimy algorytm rysowania okręgu Bresenhama.
Obydwa algorytmy wykorzystują kluczową cechę koła, czyli jego wysoką symetryczność. Zatem całe koło o 360 stopniach podzielimy na 8 części, każdy oktan o 45 stopniach. W tym celu użyjemy algorytmu koła Bresenhama do obliczenia położenia pikseli w pierwszym oktancie 45 stopni. Zakłada, że środek koła znajduje się w początku układu współrzędnych. Zatem dla każdego obliczonego piksela (x y) rysujemy piksel w każdym z 8 oktanów koła, jak pokazano poniżej:
Dla piksela (xy) wszystkie możliwe piksele w 8 oktanach
Teraz zobaczymy, jak obliczyć położenie kolejnego piksela na podstawie wcześniej znanego położenia piksela (x y). W algorytmie Bresenhama w dowolnym punkcie (x y) mamy dwie możliwości wyboru kolejnego piksela na wschodzie, tj. (x+1 y) lub na południowym wschodzie, tj. (x+1 y-1).
Można to ustalić, używając parametru decyzyjnego d jako:
- Jeżeli d > 0 to (x+1 y-1) należy wybrać jako kolejny piksel, gdyż będzie on bliżej łuku.
- else (x+1 y) ma zostać wybrany jako następny piksel.
Teraz, aby narysować okrąg dla danego promienia „r” i środka (xc yc). Zaczniemy od (0 r) i będziemy poruszać się w pierwszej ćwiartce aż do x=y (tj. 45 stopni). Powinniśmy zacząć od wymienionego warunku początkowego:
d = 3 - (2 * r)
x = 0
y = rTeraz dla każdego piksela wykonamy następujące operacje:
- Ustaw wartości początkowe (xc yc) i (x y).
- Ustaw parametr decyzyjny d na d = 3 – (2 * r).
- Wywołaj funkcję remisCircle(int xc int yc int x int y).
- Powtarzaj poniższe kroki aż do x <= y:
- Jeśli d < 0 set d = d + (4 * x) + 6.
- Inaczej ustaw d = d + 4 * (x – y) + 10 i zmniejsz y o 1.
- Zwiększ wartość x.
- Wywołaj funkcję remisCircle(int xc int yc int x int y).
funkcja remisCircle():
CPPPoniżej znajduje się implementacja powyższego podejścia w języku C.
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 ; } Wyjście:
Zalety
- Jest to prosty algorytm.
- Można to łatwo wdrożyć
- Opiera się całkowicie na równaniu okręgu, tj. x 2 +y 2 = r 2
Wady
- Występuje problem z dokładnością podczas generowania punktów.
- Algorytm ten nie nadaje się do obrazów złożonych i o dużej zawartości graficznej.
