Обобщённый целочисленный алгоритм Брезенхема квадрантов

предполагается, что концы отрезка (x₁,y₁) и (x₂,y₂) не совпадают и все переменные - целые.

Функция Sign возвращает - 1, 0, 1 для отрицательного нулевого и положительного аргумента соответственно.

инициализация переменных

x = x₁

y = y₁

Dx = abs (x₂ - x₁ )

Dy = abs (y₂ - y₁ )

s₁ = Sign (x₂ - x₁ )

s₂ = Sign (y₂ - y₁ )

обмен значение D x и D y в зависимости от углового коэффициента наклона отрезка

if Dy > Dx then

Врем = Dx

Dx = Dy

Dy = Врем

Обмен = 1

Else

Обмен = 0

End if

инициализация   с поправкой на половину пиксела

 = 2 * Dy - Dx

основной цикл

for i = 1 to Dx

Plot (x,y)

While (  ³ 0)

If Обмен = 1 then

x = x + s₁

Else

y = y + s₂

End if

 =  - 2 * Dx

End while

if Обмен = 1 then

y = y + s₂

Else

x = x + s₁

End if

 =  + 2 * Dy

next i

Finish

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

 Алгоритм Брезенхема для генерации окружностей

В растр нужно разлагать не только линейные, но и другие, более сложные функции. Разложению конических сечений, т. е. окружностей, эллипсов, парабол, гипербол посвящено значительное число работ.Наибольшее внимание, разумеется, уделено окружности. Один из наиболее эффективныхи простых для понимания алгоритмов генерации окружности принадлежит

 

2.3 Генерация полной окружности из дуги в первом октанте

 

Брезенхему. Для начала заметим, что необходимо сгенерировать только одну восьмую часть окружности. Остальные её части могут быть получены последовательными отражениями, как это показано на рис. 2.3. Если сгенерирован первый октант (от 0° до 45° против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой у = x, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой x = 0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой у = 0 для завершения построения. На рис.2.3. приведены двумерные матрицы соответствующих преобразований.

Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат. Заметим, что если работа алгоритма начинается в точке x = 0, у = R, то при генерации окружности по часовой стрелке в первом квадранте у является монотонно убывающей функцией аргумента x (рис. 2.4). Аналогично, если исходной точкой является y = 0, x = R, то при генерации окружности против часовой стрелки x будет монотонно убывающей функцией аргумента у. В нашем случае выбирается генерация по часовой стрелке с началом в точке x = 0, у = R. Предполагается, что центр окружности и начальная точка находятся точно в точках растра.

Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим образом приближающий окружность: горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. На рис.2.5 эти направления обозначены соответственно m_H, m_D, m_V.

 

2.4 Окружность в первом квадранте. 2.5 Выбор пикселов в первом квадранте

 

Алгоритм выбирает пиксел, для которого минимален квадрат расстояния между одним из этих пикселов и окружностью, т. е. минимум из

m_H = | (x_i + 1)² + (y_i )² – R² |

m_H = | (x_i + 1)² + (y_i - 1)² – R² |

m_H = | (x_i)² + (y_i - 1)² – R² |

Вычисления можно упростить, если заметить, что в окрестности точки (x_i, y_i ) возможны только пять типов пересечений окружности и сетки растра, приведенных на рис.2.6.

Разность между квадратами расстояний от центра окружности до диагонального пиксела (x_i + 1, y_i- 1) и от центра до точки на окружности R² равна

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

2.6 Пересечение окружности и сетки растра

 

При D < 0 диагональная точка (x_i + 1, y_i- 1) находится внутри реальной окружности, т. е. это случаи 1 или 2 на рис.2.6. Ясно, что в этой ситуации следует выбрать либо пиксел (x_i + 1, y_i )т. е. m_H, либо пиксел (x_i + 1, y_i- 1), т. е. m_D. Для этого сначала рассмотрим случай 1 и проверим разность квадратов расстояний от окружности до пикселов в горизонтальном и диагональном направлениях:

При d < 0 расстояние от окружности до диагонального пиксела

(m_D)больше, чем до горизонтального (m_H). Напротив, если d > 0, расстояние до горизонтального пиксела (m_H)больше. Таким образом,

при d < 0 выбираем m_H (x_i + 1, у_i )

при d > 0 выбираем m_D (x_i + 1, у_i – 1)

 

При d = 0, когда расстояния от окружности до обоих пикселов одинаковы, выбираем горизонтальный шаг.

Количество вычислений, необходимых для оценки величины d, можно сократить, если заметить, что в случае 1

так как диагональный пиксел (x_i + 1, у_i – 1) всегда лежит внутри окружности, а горизонтальный (x_i + 1, у_i ) - вне ее. Таким образом, d можно вычислить по формуле

Дополнение до полного квадрата члена (y_i )² с помощью добавления и вычитания - 2у_i + 1 дает

В квадратных скобках стоит по определению D_i, и его подстановка

 

d = 2(D_i + y_i) – 1

 

существенно упрощает выражение.

Рассмотрим случай 2 на рис.2.6 и заметим, что здесь должен быть выбран горизонтальный пиксел (x_i + 1, у_i ), так как у является монотонно убывающей функцией. Проверка компонент d показывает, что

поскольку в случае 2 горизонтальный (x_i + 1, у_i ) и диагональный (x_i + 1, у_i – 1) пикселы лежат внутри окружности. Следовательно, d < 0, и при использовании того же самого критерия, что и в случае 1, выбирается пиксел (x_i + 1, у_i ).

Если D_i > 0, то диагональная точка (x_i + 1, у_i – 1) находится вне окружности, т. е. это случаи З и 4 на рис.2.6. В данной ситуации ясно, что должен быть выбран либо пиксел (x_i + 1, у_i – 1), т. е. m_D, либо (x_i, у_i – 1), т. е. m_V. Аналогично разбору предыдущего случая критерий выбора можно получить, рассматривая сначала случай З и проверяя разность между квадратами расстояний от окружности до диагонального m_D и вертикального m_V пикселов, т. е.

При d^\ < 0 расстояние от окружности до вертикального пиксела (x_i, у_i – 1) больше и следует выбрать диагональный шаг m_D, к пикселу (x_i + 1, у_i – 1). Напротив, в случае d^\ > 0 расстояние от окружности до диагонального пиксела больше и следует выбрать вертикальное движение к пикселу (x_i, у_i – 1). Таким образом,

 

при d £ 0 выбираем m_D в (x_i + 1, у_i – 1)

при d < 0 выбираем m_V в (x_i, у_i – 1)

 

Здесь в случае d = 0, т. е. когда расстояния равны, выбран диагональный шаг.

Проверка компонент d^\ показывает, что

поскольку для случая З диагональный пиксел (x_i + 1, у_i – 1) находится вне окружности, тогда как вертикальный пиксел (x_i, у_i – 1) лежит внутри ее. Это позволяет записать d^\ в виде

Дополнение до полного квадрата члена (x_i )² с помощью добавления и вычитания 2x_i + 1 дает

Использование определения D_i приводит выражение к виду

Теперь, рассматривая случай 4, снова заметим, что следует выбрать вертикальный пиксел (x_i, у_i – 1), так как y является монотонно убывающей функцией при возрастании x. проверка компонент d^\ для случая 4 показывает, что

поскольку оба пиксела находятся вне окружности. Следовательно, d^\ > 0 и при использовании критерия, разработанного для случая 3, происходит верный выбор m_V.

Осталось проверить только случай 5 на рис.2.7, который встречается, когда диагональный пиксел (x_i + 1, у_i – 1) лежит на окружности, т. е. D_i = 0. Проверка компонент d показывает, что

Следовательно, d > 0 и выбирается диагональный пиксел (x_i + 1, у_i – 1). Аналогичным образом оцениваем компоненты d^\:

и d < 0, что является условием выбора правильного диагонального шага к (х_i + 1, у_i – 1). Таким образом, случай D_i = 0 подчиняется тому же критерию, что и случай D_i < 0 или D_i > 0.

Подведем итог полученных результатов:

D_i < 0

 d £ 0 выбираем пиксел (х_i + 1, у_i ) ® m_H

 d > 0 выбираем пиксел (х_i + 1, у_i – 1) ® m_D

D_i > 0

 d^\ £ 0 выбираем пиксел (х_i + 1, у_i – 1) ® m_D

 d^\ > 0 выбираем пиксел (х_i, у_i – 1) ® m_V

D_i = 0 выбираем пиксел (х_i + 1, у_i – 1) ® m_D

Легко разработать простые рекуррентные соотношения дня реализации пошагового алгоритма. Сначала рассмотрим горизонтальный шаг m_H к пикселу (х_i + 1, у_i ). Обозначим это новое положение пиксела как (i + 1). Тогда координаты нового пиксела и значение D_i равны

Аналогично координаты нового пиксела и значения D_i для шага m_D к пикселу (х_i + 1, у_i – 1) таковы:

То же самое для шага m_V к (х_i, у_i – 1)

Реализация алгоритма Брезенхема для окружности приводиться ниже.