« poprzedni punkt | następny punkt » |
Zastanówmy się teraz jak można narysować okrąg o środku w początku układu współrzędnych i o promieniu r. Oczywiście można skorzystać z równania okręgu
x2 + y2 = r2 i dla kolejnych wartości xi wyznaczać w każdej kolumnie wartości y i po zaokrągleniu znajdować odpowiednie piksele. Metoda taka jest jednak kosztowna obliczeniowo (występuje między innymi podnoszenie do kwadratu oraz pierwiastkowanie). Ponadto rozmieszczenie pikseli przybliżających okrąg nie jest równomierne wzdłuż okręgu (proszę się zastanowić dlaczego). Stąd w praktyce są stosowane inne metody. Niżej przedstawiono metodę z punktem środkowym (metoda mid point).
Przede wszystkim można zauważyć, że przy wyznaczaniu pikseli przybliżających okrąg można wykorzystać właściwość symetrii okręgu. Pozwala to na ograniczenie obliczania pikseli tylko do jednego oktantu (jednej ósmej) okręgu a pozostałe piksele znajdować zgodnie z zasadą pokazaną na rysunku VI.9.
![]() |
Rys. VI.9. Po wyznaczeniu punktu zaznaczonego na czerwono, punkty zaznaczone na zielono są wyznaczane przy wykorzystaniu właściwości symetrii okręgu
Wyjaśnijmy teraz na czym polega pomysł metody z punktem środkowym. Przede wszystkim przypomnijmy, że dla każdego punktu leżącego na okręgu spełnione jest równanie x2 + y2 - r2 = 0. Dla punktu leżącego na zewnątrz okręgu spełniona jest nierówność x2 + y2 - r2 > 0, a dla punktu leżącego wewnątrz okręgu spełniona jest nierówność x2 + y2 - r2 < 0. Z kolei, jeżeli ograniczymy się do pierwszego oktantu okręgu, to po wyznaczeniu piksela dla kolumny xi, w następnej kolumnie xi+1 możemy ograniczyć się tylko do wyboru między dwoma pikselami: pikselem leżącym w tym samym wierszu i pikselem leżącym w wierszu poniżej (por. rysunek VI.10). Wyboru między tymi dwoma pikselami można dokonać analizując położenie względem okręgu punktu znajdującego się w połowie odcinka łączącego dwa rozważane piksele, tak zwanego punktu środkowego. Zależnie od tego czy punkt środkowy leży wewnątrz okręgu czy na zewnątrz okręgu, należy wybrać odpowiednio górny albo dolny piksel. Okazało się, że w przypadku problemu rysowania okręgu, podobnie jak w przypadku rysowania odcinka metodą Bresenhama, można znaleźć kryterium wyboru piksela w kolejnej kolumnie, wymagające wykonania jedynie kilku prostych operacji.
![]() |
Rys. VI.10. Ilustracja metody z punktem środkowym
Ostatecznie algorytm rysowania okręgu o środku w początku układu współrzędnych i o promieniu r metodą z punktem środkowym wygląda następująco.
W przypadku gdy pk < 0, następny piksel ma współrzędne (xk+1, yk) i nowa wartość parametru decyzyjnego jest określana z zależności
pk+1 = pk +2xk+1 +1.
W przeciwnym przypadku, następny punkt ma współrzędne (xk+1, yk-1) i nowa wartość parametru decyzyjnego jest określana z zależności
pk+1 = pk + 2xk+1 +1 - 2yk+1.
Proponuję samodzielne wyznaczenie pikseli dla okręgu o środku w początku układu współrzędnych i o promieniu r = 10.
« poprzedni punkt | następny punkt » |