Случай Dd > 0. Случай Dd = 0

Случай Dd > 0

Здесь в качестве следующего пиксела могут быть выбраны или диагональный - Pd или вертикальный Pv.

Для определения того, какую пиксел выбрать Pd или Pv составим разность:

|Dd| - |Dv| =

|(X+1)² + (Y-1)² - R²| - |X² + (Y-1)² - R²|

Если si £ 0, то расстояние до вертикальной точки больше и надо выбирать диагональный пиксел Pd, если же si > 0, то выбираем вертикальный пиксел Pv.

Рассмотрим вычисление si для разных вариантов.

Для вариантов 5 и 6:

Dd > 0 и Dv £ 0, так как диагональный пиксел вне, а вертикальный либо вне либо на окружности.

si = (X+1)² + (Y-1)² - R² + X² + (Y-1)² - R²;

Добавив и вычтя (X+1)² получим:

si = 2 ·[(X+1)² + (Y-1)² - R²] - 2·X - 1

В квадратных скобках стоит Dd, так что

si = 2 ·(Dd - X) - 1

Для варианта 7:

Ясно, что должен быть выбран вертикальный пиксел Pv. Проверка компонент si показывает, что Dd > 0 и Dv > 0, причем si > 0, так как диагональная точка больше удалена от окружности, т.е. по критерию si > 0 как и в предыдущих случаях следует выбрать вертикальный пиксел Pv, что соответствует выбору для вариантов 5 и 6.

Случай Dd = 0

Для компонент di имеем: Dg > 0 и Dd = 0, следовательно по критерию di > 0 выбираем диагональный пиксел.

С другой стороны, для компонент si имеем: Dd = 0 и Dv < 0, так что по критерию si £ 0 также выбираем диагональный пиксел.

Итак:

Dd < 0

di £ 0 - выбор горизонтального пиксела Pg

di > 0 - выбор диагонального пиксела Pd

Dd > 0

si £ 0 - выбор диагонального пиксела Pd

si > 0 - выбор вертикального пиксела Pv

Dd = 0

выбор диагонального пиксела Pd.

Выведем рекуррентные соотношения для вычисления Dd для (i+1)-го шага, после выполнения i-го.

1. Для горизонтального шага к X_i+1, Y_i

X_i+1 = X_i + 1
Y_i+1 = Y_i
Dd_i+1 = (X_i+1+1)² + (Y_i+1-1)² - R² =
X_i+1² + 2·X_i+1 + 1 + (Y_i+1-1)² - R² =
(X_i+1)² + (Y_i-1)² - R² + 2·X_i+1 + 1 =
Dd_i + 2·X_i+1 + 1

2. Для диагонального шага к X_i+1, Y_i-1

X_i+1 = X_i + 1
Y_i+1 = Y_i - 1
Dd_i+1 = Dd_i + 2 ·X_i+1 - 2 ·Y_i+1 + 2

3. Для вертикального шага к X_i, Y_i-1

X_i+1 = X_i
Y_i+1 = Y_i - 1
Dd_i+1 = Dd_i - 2 ·Y_i+1 + 1

В Приложении 5 приведена подпрограмма V_circle, реализующая описанный выше алгоритм и строящая дугу окружности в первой четверти. Начальная инициализация должна быть:

X= 0

Y= R

Dd = (X+1)² + (Y-1)² - R² = 1 + (R-1)² - R² = 2*(1 - R)

Пикселы в остальных четвертях можно получить отражением. Кроме того достаточно сформировать дугу только во втором октанте, а остальные пикселы сформировать из соображений симметрии, например, с помощью подпрограммы Pixel_circle, приведенной в Приложении и заносящей симметричные пикселы по часовой стрелке от исходного.

⇐ Предыдущая 12