Случай Dd < 0

Рис. 1: Варианты расположения очередного пиксела окружности

При генерации окружности по часовой стрелке после занесения точки (X_i, Y_i) следующая точка может быть (см. рис. 0.1а) либо Pg = (X_i+1, Y_i) - перемещение по горизонтали, либо Pd = (X_i+1, Y_i-1) - перемещение по диагонали, либо Pv = (X_i, Y_i-1) - перемещение по вертикали.

Для этих возможных точек вычислим и сравним абсолютные значения разностей квадратов расстояний от центра окружности до точки и окружности:

|Dg|

| (X+1)²

Y²

R² |

|Dd|

| (X+1)²

(Y-1)²

R² |

|Dv|

| X²

(Y-1)²

R² |

Выбирается и заносится та точка, для которой это значение минимально.

Выбор способа расчета определяется по значению Dd. Если Dd < 0, то диагональная точка внутри окружности. Это варианты 1-3 (см. рис. 0.1б).

Если Dd > 0, то диагональная точка вне окружности. Это варианты 5-7.

И, наконец, если Dd = 0, то диагональная точка лежит точно на окружности. Это вариант 4.

Рассмотрим случаи различных значений Dd в только что приведенной последовательности.

Случай Dd < 0

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

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

|Dg| - |Dd| =

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

При di £ 0 будем выбирать точку Pg, в противном случае выберем Pd.

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

Для вариантов 2 и 3:

Dg ³ 0 и Dd < 0, так как горизонтальный пиксел либо вне, либо на окружности, а диагональный внутри.

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

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

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

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

di = 2 ·(Dd + Y) - 1

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

Ясно, что должен быть выбран горизонтальный пиксел Pg. Проверка компонент di показывает, что Dg < 0 и Dd < 0, причем di < 0, так как диагональная точка больше удалена от окружности, т.е. по критерию di < 0 как и в предыдущих случаях следует выбрать горизонтальный пиксел Pg, что верно.

12 Следующая ⇒