Если изображение создается с помощью этих уравнений при фиксированном шаге по углу, окружность строится из точек, расположенных по кругу через одинаковые интервалы. Чтобы уменьшить объем вычислений, можно сделать угловое расстояние между точками на окружности большим и соединять эти точки прямолинейными отрезками, аппроксимируя ими окружность. Для того чтобы на растровом дисплее получить более гладкую линию, размер углового шага можно задать равным При этом пиксели будут располагаться приблизительно на одинаковом расстоянии друг от друга. Отметим также, что, хотя полярные координаты дают равные промежутки между точками, вычисление тригонометрических функций все еще требует много времени.
При любом из вышеописанных способов построения окружностей объем вычислений можно уменьшить, учтя симметрию окружности. Форма окружности одинакова во всех квадрантах. Следовательно, если определить положение кривой в первом квадранте, можно построить часть окружности во втором квадранте плоскости ху, используя симметрию этих двух сегментов относительно оси у.
Алгоритм построения прямой линии Брезенхема для растровых систем можно адаптировать для построения окружностей, установив на каждом шаге выборки параметры принятия решения для определения ближайшего к окружности пикселя. Уравнение окружности (3.26), однако, нелинейно, поэтому для того, чтобы найти расстояния от окружности до пикселей, придется вычислять квадратные корни. В алгоритме построения окружности Брезеноема этих операций можно избежать, сравнивая квадраты расстояний до пикселей.
В то же время, возможно и непосредственное сравнение самих расстояний без возведения в квадрат. Основная идея этого подхода заключается в том, чтобы проверить точку на половине пути между двумя пикселями и определить, лежит ли эта средняя точка внутри или снаружи границы окружности. Этот метод намного легче применять к другим коническим поверхностям; а для окружности с целочисленным радиусом метод средней точки дает те же самые положения пикселей, что и алгоритм построения окружности Брезенхема. Для прямолинейного отрезка метод средней точ ки эквивалентен алгоритму построения прямой линии Брезенхема. К тому же, ошибка, возникающая при выстраивании пикселей вдоль любого конического сечения с помощью метода средней точки, не превышает половину расстояния между пикселями.
В следующем коде иллюстрируются процедуры, которыми можно воспользоваться при реализации алгоритма средней точки для окружности. Значения радиуса окружности и координат ее центра сообщаются процедуре circleMidpoint. После этого вычисляются координаты пикселей на окружности в первом октанте, которые сообщаются процедуре circlePlotPoints. Эта процедура задает в буфере кадра цвет окружности для всех симметричных точек на окружности с помощью многократного вызова процедуры set Pixel, которая реализована с помощью функций изображения точек OpenGL.
♦include <GL/glut.h> class screenPt { private:
GLint x, y;
public:
/* Инициализация по умолчанию с координатами (0, 0). */ screenPt ( ) {