Для варианта 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, приведенной в Приложении 5 и заносящей симметричные пикселы по часовой стрелке от исходного.

В Приложении 6 приведены подпрограмма V_BRcirc, реализующая описанный выше алгоритм и строящая дугу окружности во втором октанте с последующим симметричным занесением пикселов. Эта процедура может строить и 1/4 окружности. Подробнее см. текст Приложения 6. Там же приведена более короткая подпрограмма, строящая 1/8 окружности методом Мичнера [], (том 1, стр. 152). Остальная часть окружности строится симметрично.

0.4 Заполнение многоугольника

В большинстве приложений используется одно из существенных достоинств растровых устройств - возможность заполнения областей экрана.

Существует две разновидности заполнения:

· первая, связанная как с интерактивной работой, так и с программным синтезом изображения, служит для заполнения внутренней части многоугольника, заданного координатами его вершин.

· вторая, связанная в первую очередь с интерактивной работой, служит для заливки области, которая либо очерчена границей с кодом пиксела, отличающимся от кодов любых пикселов внутри области, либо закрашена пикселами с заданным кодом;

В данном разделе рассмотрим алгоритм заполнения многоугольника. В следующем разделе будут рассмотрены алгоритмы заливки области.

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

Определить принадлежность пиксела многоугольнику можно, например, подсчетом суммарного угла с вершиной на пикселе при обходе контура многоугольника. Если пиксел внутри, то угол будет равен 360^°, если вне - 0^° (рис. ).

Рис. 0.4.1: Определение принадлежности пиксела многоугольнику

Вычисление принадлежности должно производиться для всех пикселов экрана и так как большинство пикселов скорее всего вне многоугольников, то данный способ слишком расточителен. Объем лишних вычислений в некоторых случаях можно сократить использованием прямоугольной оболочки - минимального прямоугольника, объемлющего интересующий объект, но все равно вычислений будет много. Другой метод определения принадлежности точки внутренней части многоугольника будет рассмотрен ниже при изучении отсечения отрезков по алгоритму Кируса-Бека.