Алгоритм вывода окружности

Для вывода контура круга можно использовать соотношение между координатами X и Y для точек окружности X²+Y²=R² и построить алгоритм прямого вычисления координат. Однако в этом случае необходимо вычислять квадратный корень (как элемент бесконечной последовательности приближений).

Приведем запись инкрементного алгоритма Брезенхэма:

r2:=radius*radius;

dst:=4*r2;

dxt:=radius/1.414213562373;

t:=0;

s:=-4*r2*radius;

e:=(-s/2)-3*r2;

ca:=-6*r2;

cd:=-10*r2;

x:=0; y:=radius;

Закрасить пиксел (xc,yc+radius);

Закрасить пиксел (xc,yc-radius);

Закрасить пиксел (xc+radius,yc);

Закрасить пиксел (xc-radius,yc);

Для indx от 1 до dxt с шагом 1:

x:=x+1;

Если e>=0 то e:=e+t+ca иначе y:=y-1, e:=e+t-s+cd, s:=s+dst; t:=t-dst;

Закрасить пиксел (xc+x,yc+y);

Закрасить пиксел (xc+y,yc+x);

Закрасить пиксел (xc+y,yc-x);

Закрасить пиксел (xc+x,yc-y);

Закрасить пиксел (xc-x,yc-y);

Закрасить пиксел (xc-y,yc-x);

Закрасить пиксел (xc-y,yc+x);

Закрасить пиксел (xc-x,yc+y).

В этом алгоритме используется симметрия круга - в основном цикле вычисляются координаты точек окружности только для одного октанта и сразу рисуются восемь симметрично расположенных пикселов.

Алгоритм вывода эллипса

Инкрементный алгоритм для эллипса подобен алгоритму для круга, но несколько сложнее его:

a:=|enx-xc|; b:=|eny-yc|;

a2:=a*a; b2:=b*b;

dds:=4*a2; ddt:=4*b2; dxt:=a2/sqrt(a2+b2);

t:=0;

s:=-4*a2*b;

e:=(-s/2)-2*b2-a2;

ca:=-6*b2;

cd:=ca-4*a2;

x:=xc; y:=yc+b;

Закрасить пиксел (x, y);

Закрасить пиксел (x, 2*yc-y);

Закрасить пиксел (2*xc-x, 2*yc-y);

Закрасить пиксел (2*xc-x, y);

Для indx от 1 до dxt с шагом 1:

x:=x+1;

Если e>=0 то e:=e+t+ca иначе y:=y-1, e:=e+t-s+cd,

s:=s+dds; t:=t-ddt;

Закрасить пиксел (x, y);

Закрасить пиксел (x, 2*yc-y);

Закрасить пиксел (2*xc-x, 2*yc-y);

Закрасить пиксел (2*xc-x, y);

dxt:=|y-yc|;

e:=e-(t/2+s/2+b2+a2);

ca:=-6*a2;

cd:=ca-4*b2;

Для indx от 1 до dxt с шагом 1:

y:=y-1;

Если e<=0 то e:=e-s+ca иначе x:=x+1, e:=e-s+t+cd,

t:=t-ddt; s:=s+dds;

Закрасить пиксел (x, y);

Закрасить пиксел (x, 2*yc-y);

Закрасить пиксел (2*xc-x, 2*yc-y);

Закрасить пиксел (2*xc-x, y).

В этом алгоритме использована симметрия эллипса по квадрантам. Алгоритм состоит из двух циклов. Сначала для x от 0 до dxt, где а потом цикл до точки x=a, y=0.

Лекция 12

Алгоритмы закрашивания