Рассмотрим участок окружности из второго октанта jc€ [0,RHllye [RHlyR].

Особенностью данного участка является то обстоятельство, что угловой коэффициент касательной к окружности не превосходит 1 по модулю, а точнее, лежит между -1 и 0.

Применим к этому участку алгоритм средней точки (midpoint algorithm).

9 9 9

Функция F(jc, у)-х + у - R , определяющая окружность, обращается в нуль на самой окружности, отрицательна внутри окружности и положительна вне ее.

Пусть точка (jcj, у) уже поставлена. Для определения того, какое из двух значений у (у{ или) следует взять в качестве yi+i, введем переменную

dx = F(Xi +\,У1- Vi) = (*j + l)2 + (Vi - Уг)2 -R\

В случае, когда dj < 0, полагаем yj+i = у^Тогда

= F{xx + 2, yx - Уг) - + 2)2 + (vi ~ У2)2 ~ R\ Ac/j = dl+i - d\ ~ 2x\ + 3.

В случае, когда dt ^ 0, делаем шаг вниз, выбирая ^+1=^+1. Тогда di+i = F(jCj + 2,у-{ - 3/2) = (jcj + 2)2 + (y{ - 3/2)2 - R2, Ac/i = 2(jCi-^) + 5

Таким образом, мы определили итерационный механизм перехода от одного пиксела к другому. В качестве стартового пиксела берется. Тогда d0 = F(\,R-V2) = 5/4-R

и мы приходим к алгоритму О1

lmJ // File Cirdel .Cpp
static int xCenter;
static int yCenter;
static void circlePoints (int x, int y, int color) {

6. Растровые алгоритмь

putpixel ( xCenter + х, yCenter + у, color); putpixel ( xCenter + y, yCenter + x, color); putpixel ( xCenter + y, yCenter - x, color); putpixel ( xCenter + x, yCenter - y, color); putpixel ( xCenter - x, yCenter - y, color); putpixel ( xCenter - y, yCenter - x, color); putpixel ( xCenter - y, yCenter + x, color); putpixel ( xCenter - x, yCenter + y, color);

}
void circle 1 (int xc, int yc, int r, int color)
" {
int x = 0; int y = r;
float d = 1.25 - r;
xCenter = xc; yCenter = yc;
CirclePoints (x, y, color);

while (у > x)

- (
if ( d < 0 ) {
d += 2*x + 3; x++;
}
else
{

d += 2*(x - у ) + 5; x++;

y~;
}
CirclePoints ( x, y, color);
}
}

Заметим, что величина dj всегда имеет вид 1А + z,z&Z, и, значит, изменяется только на целое число. Поэтому дробную часть (всегда рав ную 1/4) можно отбросить, перейдя тем самым к полностью целочисленному алго ритму.


⇐ Предыдущая| |Следующая ⇒