Алгоритм для рисования круга

В данном приложении помещены процедуры генерации окружностей по алгоритму Брезенхема и Мичнера, а также программа T_Circle для тестирования данных процедур.

Источник

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

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

Для простоты и без ограничения общности рассмотрим генерацию 1/8 окружности, центр которой лежит в начале координат. Остальные части окружности могут быть получены последовательными отражениями (использованием симметрии точек на окружности относительно центра и осей координат).

Окружность с центром в начале координат описывается уравнением:

X 2 + Y 2 = R 2

Алгоритм Брезенхема пошагово генерирует очередные точки окружности, выбирая на каждом шаге для занесения пиксела точку растра P_i(X_i, Y_i), ближайшую к истинной окружности, так чтобы ошибка:

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

Рассмотрим генерацию 1/8 окружности по часовой стрелке, начиная от точки X=0, Y=R.

Проанализируем возможные варианты занесения i+1-й точки, после занесения i-й.

При генерации окружности по часовой стрелке после занесения точки (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) 2 +Y 2 -R 2 |
|Dd|=| (X+1) 2 +(Y-1) 2 -R 2 |
|Dv|=| X 2 +(Y-1) 2 -R 2 |

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

Выбор способа расчета определяется по значению Dd. Если Dd 0, то диагональная точка вне окружности. Это варианты 5-7. И, наконец, если Dd = 0, то диагональная точка лежит точно на окружности. Это вариант 4. Рассмотрим случаи различных значений Dd в только что приведенной последовательности.

Случай Dd 2 + Y 2 — R 2 | — |(X+1) 2 + (Y-1) 2 — R 2 |
И будем выбирать точку Pg при di = 0 и Dd 2 + Y 2 — R 2 + (X+1) 2 + (Y-1) 2 — R 2 ;
Добавив и вычтя (Y-1) 2 получим:

di = 2 ·[(X+1) 2 + (Y-1) 2 — R 2 ] + 2·Y — 1
В квадратных скобках стоит Dd, так что

Ясно, что должен быть выбран горизонтальный пиксел Pg. Проверка компонент di показывает, что Dg 0

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

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

si = |Dd| — |Dv| = |(X+1) 2 + (Y-1) 2 — R 2 | — |X 2 + (Y-1) 2 — R 2 |
Если si 0, то выбираем вертикальный пиксел Pv.

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

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

Dd > 0 и Dv 2 + (Y-1) 2 — R 2 + X 2 + (Y-1) 2 — R 2 ;
Добавив и вычтя (X+1) 2 получим:

si = 2 ·[(X+1) 2 + (Y-1) 2 — R 2 ] — 2·X — 1
В квадратных скобках стоит Dd, так что

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

С другой стороны, для компонент si имеем: Dd = 0 и Dv 0 — выбор диагонального пиксела Pd

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

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

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

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

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

Источник