ТЕМА 4. ГЕНЕРАЦИЯ ПРОСТЫХ ФИГУР
4.1. Общие замечания
Как было отмечено в разделе 1.1, материалы настоящего лекционного курса рассчитаны на последующую программную реализацию на разных языках программирования. Поэтому они изложены в самом общем виде. Так, в дальнейшем при рассмотрении алгоритмов компьютерной графики (в рамках настоящей темы и тем 5, 6 и 7) приводятся, наряду с теоретическими основами построения, только формальные описания алгоритмов, в том числе для большинства алгоритмов – на простом и доступном псевдокоде (а не на конкретном языке программирования). Перечень используемых элементов псевдокода (кроме тех, обозначения которых общеприняты в программировании или очевидны) с указанием их назначения содержится в приложении к настоящему учебному пособию. Комментарии к алгоритмам набраны с начертанием «обычный курсив».
В компьютерной графике необходимо иметь возможность генерировать отрезки, многоугольники и многогранники (представляющиеся как совокупности определенным образом ориентированных отрезков), окружности, эллипсы, параболы, гиперболы и т. д. Алгоритмы генерации таких фигур основаны на схожих принципах. Так, разложение фигур в растр (см. раздел 1.1) базируется в большинстве случаев на пошаговом методе. Он предполагает построение фигуры или ее части путем поочередного перехода от текущего пикселя к одному из соседних пикселей, который, в свою очередь, становится текущим. При этом на каждом шаге вопрос о выборе конкретного перехода среди альтернативных вариантов решается с использованием, по сути дела, аналогичных с геометрической точки зрения критериев. Требования, предъявляемые к получаемым аппроксимациям фигур, тоже более-менее однотипны: их формы желательно максимально приближать к формам идеальных фигур, отрезки прямых и кривых должны начинаться и заканчиваться в заданных точках, иметь по возможности одинаковую толщину на всей протяженности. Важным, кроме того, является требование по быстродействию работы алгоритмов. Для его повышения следует стараться сводить вычисления к минимуму, применять целочисленную арифметику (а не вещественную), избегать операций деления, при анализе альтернативных вариантов перехода использовать знаки (а не численные значения) соответствующих критериев и т. п. Как это часто бывает, не все перечисленные требования могут быть удовлетворены в полной мере одновременно, и при решении о выборе алгоритма часто приходится идти на те или иные компромиссы.
Далее в рамках настоящей темы рассмотрен ряд алгоритмов генерации относительно простых фигур: отрезка, окружности, эллипса. Во всех этих алгоритмах (так же, как, впрочем, и в последующих) полагается, что исходные точки задаются целочисленными значениями координат в сетке растра. Напомним здесь, кроме того, о том, что обращение к конкретному пикселю осуществляется через целочисленные координаты его адресуемой точки, расположенной в левом нижнем углу пикселя (см. раздел 1.1).
4.2. Алгоритм генерации отрезков по методу ЦДА
Один из наиболее простых вариантов разложения отрезка в растр основан на методе цифрового дифференциального анализатора (ЦДА). Любой отрезок описывается дифференциальным уравнением вида
,
где 
, 
и 
, 
– горизонтальная и вертикальная координаты соответственно начала и конца отрезка.
Аналогичное уравнение относительно конечных приращений 
и 
(которые используются далее при определении принадлежащих отрезку точек с некоторой дискретностью) будет выглядеть так:
.
При нахождении в некоторой текущей точке отрезка с координатами 
и 
решение для следующей точки будет таким:
§ если задано –
, 
;
§ если задано –
, 
.
Суть метода ЦДА, использующего пошаговый метод, заключается в следующем. Если для всего отрезка модуль полного приращения по x, т. е. 
, не меньше, чем модуль полного приращения по y, т. е. 
, модуль дискретного приращения принимается равным единице, и на каждом шаге координата x в координатной сетке растра безусловно изменяется на единицу; после расчета значения координаты y следующей точки оно округляется до ближайшего целого числа, поэтому единичное изменение y в сетке растра либо происходит, либо нет. Если же меньше, чем , все происходит наоборот: единичным полагают модуль дискретного приращения , в сетке растра координата y на каждом шаге изменяется на единицу, а координата x в зависимости от результата расчета и округления ее значения либо изменяется на единицу, либо нет.
Приведем реализующий данный подход алгоритм генерации отрезка на псевдокоде (см. приложение).
Определение большего из полных приращений отрезка по x и по y
if Abs (x2 – x1) ³ Abs ( y2 – y1) then
Длина = Abs (x2 – x1)
else
Длина = Abs ( y2 – y1)
end if
Расчет дискретных приращений D x и D y
D x = (x2 – x1) / Длина
D y = ( y2 – y1) / Длина
Инициализация переменных; прибавление к начальным значениям x1 и y1 по 1/2 приращений D x и D y с учетом их знаков соответственно обеспечивает в дальнейшем округление текущих значений x и y, а не взятие от них целой части
x = x1 + 0.5*Sign (D x)
y = y1 + 0.5*Sign (D y)
Расчет координат адресуемых точек пикселей в растре
i = 1
while (i £ Длина)
Plot (Integer (x), Integer ( y))
x = x + D x
y = y + D y
i = i + 1
end while
finish
Приведем пример последовательности действий такого алгоритма при разложении в растр отрезка, идущего из точки (0, 0) в точку (-5, 3). Начальные установки при расчете: 
, 
, 
, 
.
Результаты последующего расчета координат адресуемых точек пикселей, аппроксимирующих отрезок, приведены в табл.4.1, а соответствующее расчету растровое представление отрезка – на рис.4.1.
Представленный алгоритм не отличается высокой точностью. Так, симметричные относительно начала координат отрезки могут отображаться несимметричными растровыми аппроксимациями. Кроме того, в алгоритме используется вещественная арифметика, что несколько замедляет проведение расчетов.
4.3. Алгоритм Брезенхема для генерации отрезков
Более приемлемым для генерации отрезков считается алгоритм Брезенхема. В соответствии с ним отрезок вычерчивается пошагово от начала – точки P1 с координатами (,) – до конца – точки P2 с координатами ( ,). Важную роль при этом имеет ориентация отрезка. Ее определяет положение точки P2 относительно начала координат, которое условно совмещается с точкой P1 (рис.4.2). При попадании точки P2 в какой-либо октант координатной плоскости говорят о том, что весь отрезок расположен в этом октанте (так, например, считается, что отрезок 
на рис.4.2 расположен в седьмом октанте). На каждом шаге в зависимости от величины тангенса угла наклона отрезка (назовем его угловым коэффициентов и обозначим как m) единичное приращение одной из координат задается безусловно. Необходимость единичного изменения другой координаты
|
|
, изображенного на рис.4.2, на каждом шаге y безусловно будет получать приращение –1, а x – либо изменяться на +1, либо оставаться неизменным).
Ознакомимся более подробно с принципами работы вещественного алгоритма Брезенхема для генерации отрезка в первом октанте (впоследствии он будет преобразован в целочисленный и обобщен на случай произвольной ориентации отрезка). Значение углового коэффициента отрезка, расположенного в первом октанте, лежит в диапазоне 
, и на каждом шаге x безусловно получает приращение +1, а вопрос о приращении y на +1 решается с учетом знака ошибки e. Каким образом она формируется и используется для выбора решения, можно рассмотреть на следующем примере.
Допустим, необходимо построить отрезок в первом октанте с угловым коэффициентом 
. Точка начала отрезка с координатами (x1 , y1) (впрочем, как и точка его конца) совпадает с каким-либо узлом растра. Активизируем пиксель с такими же координатами адресуемой точки и инициализируем начальное значение ошибки 
(рис.4.3). Горизонтальная координата следующей адресуемой точки очевидна: 
. Новое значение ошибки рассчитывается путем добавления к ней значения углового коэффициента: 
. Отрицательное значение ошибки свидетельствует о том, что пересечение реального отрезка с прямой расположено ближе к прямой 
, чем к прямой 
(это наглядно иллюстрирует рис.4.3), поэтому точка растра (
,) лучше аппроксимирует ход отрезка, чем точка (,
). Активизировав пиксель с координатами адресуемой точки (,), делаем следующий шаг: 
, 
; т. к. ошибка положительна, задаем единичное приращение по вертикали . Активизируем пиксель с адресуемой точкой (
,). Вместе с тем, как только ошибка стала положительной, ее значение необходимо скорректировать путем вычитания единицы: 
. Дальнейшие действия алгоритма аналогичны: 
, 
, y не увеличивается, активизируется пиксель (
,) и т. д. Отметим здесь только еще один нюанс: если на каком-либо шаге ошибка принимает нулевое значение, нет предпочтительного варианта задания вертикальной координаты (т. к. отрезок пересекает соответствующую вертикаль строго посередине между двумя узлами растра); для определенности алгоритм Брезенхема в этом случае дает приращение y на единицу и корректирует значение ошибки. Поэтому при расчете следующей точки в рассмотренном только что примере результаты будут такими: 
, 
, 
, активизация пикселя с координатами адресуемой точки (
,
), корректировка значения ошибки 
(см. рис.4.3).
Алгоритм на псевдокоде (см. приложение) выглядит так.
Инициализация переменных
x = x1
y = y1
D x = x2 – x1
D y = y2 – y1
Инициализация ошибки с поправкой на 
e = D y /D x – 1/2
Основной цикл
for i = 1 to D x
Plot (x, y)
while (e ³ 0)
y = y + 1
e = e – 1
end while
x = x + 1
e = e + D y /D x
next i
finish
Приведем пример построения отрезка, расположенного в первом октанте и имеющего координаты начала и конца (0, 0) и (5, 3) соответственно. Начальные установки при расчете: , , 
, .
Результаты работы основного цикла по расчету пикселей, аппроксимирующих отрезок, приведены в табл.4.2, а соответствующее расчету растровое представление отрезка – на рис.4.4.
Быстродействие приведенного алгоритма можно повысить, если исключить из вычислений деление и вещественную арифметику (оставив, естественно, целочисленную). Это достигается в целочисленном алгоритме Брезенхема для генерации отрезка в первом октанте простым приемом: при вычислении ошибки используется положительный множитель 
(важен ведь только ее знак); при этом ошибка всегда принимает целочисленные значения. Приведем данный алгоритм на псевдокоде.
Инициализация переменных
x = x1
y = y1
D x = x2 – x1
D y = y2 – y1
Инициализация ошибки
e = 2*D y – D x
Основной цикл
for i = 1 to D x
Plot (x, y)
while (e ³ 0)
y = y + 1
e = e – 2*D x
end while
x = x + 1
e = e + 2*D y
next i
finish
Собрав воедино изложенные выше соображения, приведем формальное описание обобщенного целочисленного алгоритма Брезенхема (который, собственно, и используется в компьютерной графике под названием алгоритма Брезенхема), позволяющего генерировать произвольным образом ориентированные отрезки. Используем для этого псевдокод.
Инициализация переменных
x = x1
y = y1
D x = Abs (x2 – x1)
D y = Abs ( y2 – y1)
s1 = Sign (x2 – x1)
s2 = Sign ( y2 – y1)
Обмен значений D x и D y в зависимости от величины углового коэффициента отрезка
if D y > D x then
Врем = D x
D x = D y
D y = Врем
Обмен = 1
else
Обмен = 0
end if
Инициализация ошибки
e = 2*D y – D x
Основной цикл
for i = 1 to D x
Plot (x, y)
while (e ³ 0)
if (Обмен = 1) then
x = x + s1
else
y = y + s2
end if
e = e – 2*D x
end while
if (Обмен = 1) then
y = y + s2
else
x = x + s1
end if
e = e + 2*D y
next i
finish
Для иллюстрации работы обобщенного алгоритма Брезенхема рассмотрим разложение в растр отрезка, расположенного в шестом октанте (и, соответственно, в третьем квадранте). Пусть координаты начала и конца отрезка будут (0, 0) и (–5, –8) соответственно. Начальные установки при расчете очевидны.
Обмен значений D x и D y
Инициализация ошибки
Результаты последующей работы основного цикла по разложению отрезка в растр приведены в табл.4.3, а полученная растровая аппроксимация отрезка – на рис.4.5.
4.4. Алгоритм Брезенхема для генерации окружности
Существуют несколько версий алгоритма Брезенхема для генерации окружности. Они имеют ряд общих признаков. Так, во всех этих версиях изначально пошагово генерируется одна восьмая часть окружности, расположенная во втором октанте координатной плоскости, при условии, что центр окружности совмещен с точкой начала координат (рис.4.6); причем ее построение начинается в точке (
,
) и осуществляется в направлении по часовой стрелке. При этом y является монотонно убывающей функцией x. Остальные части окружности достраиваются последовательными симметричными отражениями: сгенерированной восьмой части во втором октанте – относительно прямой 
в первый октант, а полученной после этого четверти окружности в первом квадранте – относительно координатных осей x и y, а также точки начала координат в четвертый, второй и третий квадранты соответственно. Во всех случаях арифметика целочислена, при анализе альтернативных вариантов перехода (от пикселя к пикселю) используются не численные значения, а только знаки определенных величин (критериев), что упрощает и ускоряет вычисления. Отличаются версии, по сути дела, только несколько разными с математической, в том числе геометрической точки зрения подходами. Рассмотрим кратко первую, самую раннюю, версию алгоритма (сейчас она практически вышла из употребления) и одну из тех, которые появились позже и применяются в настоящее время.
Теоретические положения, на которых базируется первая версия алгоритма Брезенхема, пригодны для построения четверти (а не одной восьмой части) окружности в первом квадранте. При нахождении в этом квадранте в некоторой текущей точке растра с координатами (
,
) есть только три варианта выбора очередного пикселя (рис.4.7): по горизонтали вправо (направление H ), по диагонали вниз и вправо (направление D) и по вертикали вниз (направление V ). Вместе с тем, в каждой такай ситуации возможны пять типов пересечений реальной окружности и сетки растра (рис.4.7).
В качестве первого критерия для выбора очередного шага используется разность между квадратами расстояний от центра окружности до диагональной (по отношению к текущей) точки, т. е. точки с координатами (
,
), и до реальной окружности:
.
При 
диагональная точка находится внутри окружности, т. е. это случаи пересечения 1 или 2. Ясно, что в данной ситуации следует выбрать либо точку (,), т. е. шаг H, либо точку (,), т. е. шаг D. Вторым критерием перехода при таких условиях служит величина
;
она представляет собой разность двух модулей: под первым из них стоит разность между квадратами расстояний от центра окружности до горизонтальной (по отношению к текущей) точки и до реальной окружности; под вторым – разность между квадратами расстояний от центра окружности до диагональной (по отношению к текущей) точки и до реальной окружности.
При 
расстояние от окружности до горизонтальной точки не больше расстояния до диагональной точки, и следует выбирать горизонтальную точку, т. е. шаг H. При 
выбирается диагональная точка, т. е. шаг D, т. к. расстояние от окружности до нее меньше.
Вместе с тем, при варианте пересечения 1 (см. рис.4.7)
, 
,
т. к. горизонтальная точка лежит вне или на окружности, а диагональная – внутри нее, поэтому d можно вычислить по формуле
;
или (после преобразования с учётом выражения для 
)
.
При варианте пересечения 2 (см. рис.4.7) расстояние от окружности до горизонтальной точки безусловно меньше расстояния от нее же до диагональной точки, и выбирать следует горизонтальную. При этом обе точки лежат внутри окружности, поэтому
, ,
и для расчета d можно использовать ту же формулу, что и при варианте 1, т. к. она дает заведомо отрицательное значение.
Если 
, то диагональная точка находится вне окружности, т. е. это случаи пересечения 3 или 4 (рис.4.7). Выбирать следует либо точку (,), т. е. шаг D, либо точку (,), т. е. шаг V.
Можно показать (аналогично тому, как это было сделано для предыдущего случая), что критерием для выбора при этом является величина
;
при 
выбирается диагональная точка, т. к. расстояние от окружности до нее не больше, чем до вертикальной (по отношению к текущей); при 
выбирается вертикальная точка, т. к. расстояние от окружности до нее меньше, чем до диагональной.
Очевидно, что при 
диагональная точка (,) расположена непосредственно на окружности (вариант пересечения 5 на рис.4.7), и выбирается именно она.
Подведем итог. Согласно рассматриваемой версии алгоритма Брезенхема:
§ если :
при выбираем направление H, т. е. пиксель (,);
при выбираем направление D, т. е. пиксель (,);
§ если :
при выбираем направление D, т. е. пиксель (, );
при d¢ > 0 выбираем направление V, т. е. пиксель (,);
§ если выбираем направление D, т. е. пиксель (,).
При переходе к очередному текущему пикселю можно использовать следующие выражения (для 
– без вывода):
§ при шаге в горизонтальном направлении H:
; 
; 
;
§ при шаге в диагональном направлении D:
; 
; 
;
§ при шаге в вертикальном направлении V:
; ; 
.
Если сгенерирована четверть окружности в первом квадранте, для построения полной окружности эту четверть следует симметрично отразить относительно осей x и y и точки начала координат, т. е. активизировать не только выбранные пиксели (,), но и симметричные им пиксели (,
), (
,) и (,).
Ниже представлен составленный с учетом изложенных соображений алгоритм для прорисовки окружности с исходной генерацией ее четверти на псевдокоде (см. приложение). Кроме описанных выше величин в нем присутствуют переменные x0 , y0 – целочисленные координаты центра окружности в сетке растра.
Инициализация переменных
x = 0
y = R
D = 2*(1 – R)
Предел = 0
Пошаговый расчет и генерация пикселей
1 Plot (x0 + x , y0 + y), (x0 + x , y0 – y), (x0 – x , y0 + y),
(x0 – x, y0 – y)
if y £ Предел then 4
if D < 0 then 2
if D > 0 then 3
if D = 0 then 20
2 d = 2*D + 2* y – 1
if d £ 0 then 10
if d > 0 then 20
3 d¢ = 2*D – 2* x – 1
if d¢ £ 0 then 20
if d¢ > 0 then 30
Шаг H
10 x = x + 1
D = D + 2* x + 1
go to 1
Шаг D
20 x = x + 1
y = y – 1
D = D + 2* x – 2* y + 2
go to 1
Шаг V
30 y = y – 1
D = D – 2* y + 1
go to 1
4 finish
Данный алгоритм может быть легко преобразован в алгоритм построения окружности с исходной генерацией одной восьмой ее части во втором октанте. Для этого достаточно присвоить переменной Предел другое значение: Предел = Integer (
). При этом, однако, надо позаботиться еще и о том, чтобы происходили все необходимые симметричные отражения рассчитанных пикселей (см. ниже, во второй версии алгоритма Брезенхема).
Рассмотрим теперь более позднюю и достаточно простую версию алгоритма Брезенхема (в [4] ее называют алгоритмом средней точки). В ней учитывается то обстоятельство, что при построении одной восьмой части окружности во втором октанте на каждом шаге возможны только два варианта перехода: по горизонтали, т. е. шаг H, и по диагонали, т. е. шаг D (рис.4.8). Выбор между ними осуществляется с использованием единственного критерия – разности между квадратами расстояний от центра окружности до точки с координатами (,
) (так называемой средней точки, расположенной как раз посередине между альтернативными точками перехода, см. рис.4.8) и до реальной окружности:
.
Если , средняя точка находится внутри окружности, и выбирается шаг H; если 
, эта точка расположена вне окружности или непосредственно на ней, и выбирается шаг D.
При переходе к очередному текущему пикселю можно использовать следующие выражения (для – без вывода):
§ при шаге в горизонтальном направлении H:
; ; 
;
§ при шаге в диагональном направлении D:
; ; 
.
Приведем данную версию алгоритма Брезенхема для прорисовки окружности с исходной генерацией одной восьмой ее части на псевдокоде (см. приложение). Как и в первой версии, переменным x0 и y0 здесь присваиваются целочисленные значения координат центра окружности.
Инициализация переменных
x = 0
y = R
D = 5/4 – R
Пошаговый расчет и генерация пикселей
while ( y > x)
Plot (x0 + x , y0 + y), (x0 + y , y0 + x), (x0 + x , y0 – y), (x0 + y , y0 – x),
(x0 – x , y0 + y), (x0 – y , y0 + x), (x0 – x , y0 – y), (x0 – y , y0 – x)
if D < 0 then
D = D + 2*x + 3
else
D = D + 2* x – 2*y + 5
y = y – 1
end if
x = x + 1
end while
finish
Анализ представленного алгоритма приводит к следующему выводу: все значения, которые принимает D, содержат дробную часть, равную 1/4, и ее отбрасывание не приводит к нарушению действий алгоритма по расчету точек. Это обстоятельство позволяет инициализировать начальное значение данного критерия без учета дробной части, т. е. 
(а не 
). При этом все последующие значения D будут также целочисленными.
Приведем пример работы алгоритма, в который внесено данное изменение, при построении окружности с центром в точке (2, 0) и радиусом, равным пяти. Начальные установки: 
, 
, 
.
Результаты последующей работы алгоритма по разложению окружности в растр приведены в табл.4.4, а полученная растровая аппроксимация окружности – на рис.4.9.
Таблица 4.4. Разложение в растр окружности
по второй версии алгоритма Брезенхема
Plot | D | y | x |
(2, 5 ); (7, 0); (2, –5 ); (7, 0); (2, 5 ); (–3, 0); (2, –5 ); (–3, 0) | –1 |
| 1 |
(3, 5 ); (7, 1); (3, –5 ); (7, –1); (1, 5 ); (–3, 1); (1, –5 ); (–3, –1) | 4 |
| 2 |
(4, 5 ); (7, 2); (4, –5 ); (7, –2); (0, 5 ); (–3, 2); (0, –5 ); (–3, –2) | 3 | 4 | 3 |
(5, 4 ); (6, 3); (5, –4 ); (6, –3); (–1, 4 ); (–2, 3); (–1, –4 ); (–2, –3) | 6 | 3 | 4 |
4.5. Алгоритм генерации эллипса
Существуют несколько версий алгоритма генерации эллипса. Все они являются, по сути дела, обобщениями соответствующих версий алгоритма Брезенхема для генерации окружности. Основные принципы построения эллипса схожи во всех версиях. Центр эллипса условно совмещается с точкой начала координат (как и при построении окружности), а оси эллипса – с координатными осями. При этом уравнение эллипса имеет вид
;
или
.
Генерируется одна четвертая часть эллипса в первом квадранте; затем эта четверть симметрично отражается во второй, третий и четвертый квадранты (рис.4.10). Пошаговое построение четверти эллипса начинается в точке (,
) и осуществляется в направлении по часовой стрелке. Данный процесс реализуется в два этапа: на первом прорисовывается участок, на котором модуль углового коэффициента принимает значения в диапазоне от нуля до единицы (на рис.4.10 – участок 1); на втором – участок, на котором угловой коэффициент по модулю больше единицы (на рис.4.10 – участок 2). При решении вопроса о том, на каком шаге следует перейти от построения первого участка к построению второго участка, можно использовать следующие соображения. Теоретически для первого участка справедливо неравенство 
, для второго – неравенство 
; в точке же, разделяющей эти участки, выполняется условие 
. Подстановка этого условия в уравнение эллипса и решение последнего в общем виде относительно x дает выражение для расчета горизонтальной координаты в точке, разделяющей участки:
.
Разберем более подробно одну из версий алгоритма генерации эллипса, самую, пожалуй, простую, аналогичную рассмотренному в предыдущем разделе алгоритму средней точки.
При нахождении в некоторой текущей точке с координатами (,) на первом участке есть только два варианта перехода к очередной точке (как и при построении одной восьмой части окружности во втором октанте): по горизонтали, т. е. шаг H, и по диагонали, т. е. шаг D (рис.4.11а). Критерий перехода формируется путем подстановки в левую часть уравнения эллипса (второго из двух, приведенных выше) координат точки (,) (т. е. средней точки, расположенной посередине между альтернативными точками перехода):
;
с геометрической точки зрения получаемая величина пропорциональна разности квадратов вертикальных координат средней точки и точки, принадлежащей четверти эллипса, при 
(коэффициентом пропорциональности служит 
).
Если , эллипс проходит выше средней точки, и выбирается шаг H; если , эллипс проходит ниже этой точки или непосредственно через нее, и выбирается шаг D.
При переходе к очередному текущему пикселю можно использовать следующие выражения (для – без вывода):
§ при шаге в горизонтальном направлении H:
; ; 
;
§ при шаге в диагональном направлении D:
; ; 
.
При нахождении текущей точке (,) на втором участке вариантов перехода к очередной точке тоже два: по диагонали, т. е. шаг D, или по вертикали, т. е. шаг V (рис.4.11б). Критерий перехода формируется по аналогии с предыдущим, но в данном случае используется средняя точка (
,):
;
получаемая величина пропорциональна разности квадратов горизонтальных координат средней точки и точки, принадлежащей четверти эллипса, при 
(коэффициент пропорциональности здесь равен ).
Если , эллипс проходит правее средней точки, и выбирается шаг D; если , эллипс проходит левее этой точки или непосредственно через нее, и выбирается шаг V.
Переход к очередному текущему пикселю осуществляется с использованием следующих выражений (для – без вывода):
§ при шаге в диагональном направлении D:
; ; 
;
§ при шаге в вертикальном направлении V:
; ; 
.
Вопрос о выборе критерия, на основании которого осуществляется переход от построения первого участка к построению второго участка, решается неоднозначно. Будем считать, что первый участок следует выстраивать до тех пор, пока горизонтальная координата точки, сдвинутой вправо на 1/2 относительно текущей, меньше чем 
(см. выше), т. е. пока выполняется условие 
или (что то же самое) 
.
Приведем алгоритм, базирующийся на изложенных соображениях, на псевдокоде (см. приложение). Переменные x0 и y0 в нем – это целочисленные координаты центра эллипса.
Инициализация переменных
x = 0
y = b
Расчет первого значения D для первого участка
Пошаговый расчет первого участка и инициализация пикселей
Plot (x0 + x , y0 + y), (x0 + x , y0 – y), (x0 – x , y0 + y), (x0 – x , y0 – y)
while (
)
if D < 0 then
else
y = y – 1
end if
x = x + 1
Plot (x0 + x , y0 + y), (x0 + x , y0 – y), (x0 – x , y0 + y), (x0 – x , y0 – y)
end while
Расчет первого значения D для второго участка
Пошаговый расчет второго участка и инициализация пикселей
while (
)
if D < 0 then
x = x + 1
else
end if
y = y – 1
Plot (x0 + x , y0 + y), (x0 + x , y0 – y), (x0 – x , y0 + y), (x0 – x , y0 – y)
end while
finish
Проследим действия данного алгоритма по генерации эллипса при следующих начальных установках: 
, 
, 
, 
.
Расчет первого значения D для первого участка
Plot (0, 6 ), (0 , –2), (0, 6 ), (0 , –2)
Результаты последующей работы алгоритма по разложению в растр первого участка эллипса приведены в табл.4.5.
Таблица 4.5. Разложение в растр первого участка эллипса
D | x | y | Plot |
–71 | 1 |
| (1, 6 ); (1, –2); (–1, 6 ); (–1, –2) |
9 | 2 |
| (2, 6 ); (2, –2); (–2, 6 ); (–2, –2) |
–95 | 3 | 3 | (3, 5 ); (3, –1); (–3, 5 ); (–3, –1) |
49 | 4 |
| (4, 5 ); (4, –1); (–4, 5 ); (–4, –1) |
81 | 5 | 2 | (5, 4 ); (5, 0); (–5, 4 ); (–5, 0) |
Расчет первого значения D для второго участка
Результаты работы алгоритма по разложению в растр второго участка эллипса приведены в табл.4.6.
Таблица 4.6. Разложение в растр второго участка эллипса
D | x | y | Plot |
100 | 6 | 1 | (6, 3); (6, 1); (–6, 3); (–6, 1) |
136 |
| 0 | (6, 2 ); (6, 2); (–6, 2 ); (–6, 2) |
Растровая аппроксимация эллипса представлена на рис.4.12.
