Алгоритмы вычерчивания окружностей

Цель работы: изучение алгоритма Брезенхема для вычерчивания окружностей.

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

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

Рисунок 4.1 – Окружность в первом квадранте

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

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

                        (4.1)

Рисунок 4.2 – Выбор пикселей в первом квадранте

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

Рисунок 4.3 – Пересечение окружности и сетки растра

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

                                 (4.2)

В алгоритме Брезенхема желательно использовать только знак ошибки, а не ее величину.

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

      (4.3)

При d < 0 расстояние от окружности до диагонального пикселя больше, чем до горизонтального. Напротив, если d > 0, расстояние до горизонтального пикселя больше. Таким образом:

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

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

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

Практическое задание

Составить алгоритм и программу для отображения объекта № 2 методом Брезенхема.

Содержание отчета: блок-схема данной программы; краткие ответы на вопросы, приведенные в таблице 4.1; распечатка листа Excel с результатами.

Таблица 4.1 – Вопросы для защиты