ALL

АЛГОРИТМЫ ПОСТРОЕНИЯ ОКРУЖНОСТЕЙ

2.Еще один способ устранения неодинаковых промежутков – найти точки на границе круга с помощью полярных координат r и θ (рис. 3.16)

•x=xc +rcosθ;

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

•Чтобы уменьшить объем вычислений, можно сделать угловое расстояние между точками на окружности большим и соединять эти точки прямолинейными отрезками, аппроксимируя ими окружность.

•Для того чтобы на растровом дисплее получить более гладкую линию, размер углового шага можно задать равным 1/r. При этом пиксели будут располагаться приблизительно на одинаковом расстоянии друг от друга.

•Отметим также, что, хотя полярные координаты дают равные промежутки между точками,

вычисление тригонометрических функций все еще требует много времени.

3.При любом из вышеописанных способов построения окружностей объем вычислении можно уменьшить, учтя симметрию окружности.

•Форма окружности одинакова во всех квадрантах. Следовательно, если определить положение кривой в первом квадранте, можно построить часть окружности во втором квадранте плоскости xy, используя симметрию этих двух сегментов относительно оси у. Кроме того, части окружности в третьем и четвертом квадрантах полу чаются из частей первого и второго с помощью симметрии относительно оси х.

АЛГОРИТМЫ ПОСТРОЕНИЯ ОКРУЖНОСТЕЙ

•Рис. симметрия окружности. По координатам точки окружности (x, y) в одном октанте получаются точки окружности, обозначенные в остальных октантах.

•Этим путем можно пройти еще дальше и воспользоваться симметрией октантов.

•Части окружности в соседние октантах одного квадранта симметричны относительно биссектрисы квадранта, делящей его на октанты.

•Воспользовавшись преимуществами симметрии окружности, можно изобразить все пиксели

на окружности, рассчитав всего лишь координаты точек в секторе от х = 0 до х =y. Тангенс угла наклона кривой в этом октанте m 1,0.

•В точке х = 0 величина m = 0, а в точке х = у величина m = –1,0.

•Определение координат пикселей окружности с использованием преимуществ симметрии и уравнения (26), либо уравнения (28) все еще требует существенного объема вычислений.

•В декартовом уравнении (26) входят операции умножения и извлечение квадратного корня, тогда как параметрические уравнения содержат операции умножения и расчета тригонометрических функций.

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

АЛГОРИТМЫ ПОСТРОЕНИЯ ОКРУЖНОСТЕЙ

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

•Уравнение окружности (20), однако, нелинейно, поэтому для того, чтобы найти расстояния от окружности до пикселей, придется вычислять квадратные корни.

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

•В то же время, возможно и непосредственное сравнение расстояний без возведении в квадрат.

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

•Этот метод намного легче применять к другим коническим поверхностям, а для окружности с целочисленным радиусом метод средней точки дает те же самые положения пикселей, что и алгоритм построений окружности Брезенхема.

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

АЛГОРИТМ ПОСТРОЕНИЯ ОКРУЖНОСТИ МЕТОДОМ СРЕДНЕЙ ТОЧКИ

•Линия разбивается на единичные интервалы и на каждом шаге определяются координаты пикселей, которые находятся ближе всего к заданной окружности.

1.При известном радиусе r и координатах центра окружности на экране (x0, y0) вначале можно организовать алгоритм таким образом, чтобы рассчитать координаты пикселей вокруг окружности с центром в начале координат (0, 0).

2.После того каждое рассчитанное положение (х, у) перемещается в соответствующую ему

точку на экране для чего – xc прибавляется к х. уc – к у. На дуге окружности от х = 0 до х = у в первом квадрате тангенс угла наклона кривой меняется 0 до 1.

•Таким образом, в этом октанте можно брать 1 шаг в положительном направлении координаты х и на основе параметра принятия решения определять, какой из пикселей в каждом столбце находится ближе по вертикали к заданной окружности.

•После этого из соображений симметрии находятся координаты пикселей в остальных семи октантах.

•Чтобы воспользоваться методом средней точки, зададим функцию окружности как

–Любая точка (x, y), которая лежит на окружности радиуса r , удовлетворяет уравнению fcirc(x,y) = 0.

–Если точка находится внутри круга, то функция окружности будет иметь отрицательное значение.

–Если точка лежит за пределами круга, значение функции окружности будет положительным.

АЛГОРИТМ ПОСТРОЕНИЯ ОКРУЖНОСТИ МЕТОДОМ СРЕДНЕЙ ТОЧКИ

• Подытоживая, можно сказать, что относительное положение любой точки с координатами (x, y) определяется проверкой знака функции окружности:

•Проверка (30) выполняется на каждое этапе выборки для средних положений между пикселями вблизи заданной окружности.

•Таким образом, функция окружности – это параметр принятия решении в алгоритме средней точки, и для этой функции можно установить операции приращения, как это было сделано для алгоритма построения прямой линии.

•На рис. показана средняя точка между двумя возможными пикселями в точке выборки xk + 1.

Рис. Средняя точка между вероятными пикселями окружности в точки выборки xk + 1

АЛГОРИТМ ПОСТРОЕНИЯ ОКРУЖНОСТИ МЕТОДОМ СРЕДНЕЙ ТОЧКИ

•Предположим, что мы поставили точку в пикселе с координатами (xk, yk).

•нужно определить, какой из двух пикселей ближе к заданной окружности – с координатами (xk

+1, yk ) или (xk +1, yk –1).

•Параметром принятия решения будет функция окружности (fcirc(x,y) = x2 + y2 + r2), которая рассчитывается для средней точки между этими двумя пикселями;

–Если pk < 0, средняя точка лежит внутри окружности, и к заданной окружности будет ближе пиксель, который находится в строке развертки yk.

–В противном случае средняя точка находится за пределами окружности или лежит на ней, и выбирается пиксель в строке развертки yk – 1.

•Последующие параметры принятия решения находятся с помощью операции приращения.

•Рекурсивное выражение для следующего параметра принятия решения получается вычислением функции окружности в точке выборки xk + 1= x + 2.

• где yk+1 – это либо yk, либо yk –1, в зависимости от знака pk.

АЛГОРИТМ ПОСТРОЕНИЯ ОКРУЖНОСТИ МЕТОДОМ СРЕДНЕЙ ТОЧКИ

•Приращение, с помощью которою находится pk+1 равно либо 2xk+1 + 1 (если pk отрицательное), либо 2xk+1 + 1 – 2yk+1.

•Члены 2xk+1 и 2yk+1 также можно оценить через приращение значения как

•2xk+1 = 2 xk +2;

•2 yk+1= 2 yk – 2.

•В начальном положении (0, r) эти два члена имеют значения 0 и 2r соответственно. Каждое

последующее значение члена 2xk+1 находится прибавлением 2 к предыдущему значению, а каждое последующее значение члена 2yk+1 находится вычитанием 2 из предыдущего значения.

•Чтобы найти начальный параметр принятия решения, вычисляется функция окружности в начальном положении (x0, y0) = (0, r).

•p0 = fcirc(1, r – 1/2) = 1+ (r – 1/2) – r2

•или

•Если радиус r – целое число, то, поскольку все приращения – целые числа, p0 можно просто округлить до

•p0 = 1 – r (если r – целое число).

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

АЛГОРИТМ ПОСТРОЕНИЯ ОКРУЖНОСТИ МЕТОДОМ СРЕДНЕЙ ТОЧКИ

•1. Ввести радиус r и координаты центра окружности (xc, yc),

•затем задать координаты первой точки на окружности, центр которой находится в начале координат:

•(x0, y0) = (0, r).

•2. Найти исходное значение параметра принятия решения:

•p0 = 5/4 – r

•3. Для каждого значения xk, начиная с k = 0, выполнить следующую проверку:

–Если pk<0, то следующая точка на окружности с центром в точке (0, 0) будет (xk+1 ,yk) и

–pk+1 = pk + 2xk + 1

–Иначе следующей точкой на окружности будет (xk + 1,yk – 1) и

–pk+1 = pk + 2xk + 1 – 2yk+1 1

•где 2xk+1 = 2 xk +2 и 2 yk+1=2 yk – 2.

•4. Найти симметричные точки в остальных семи октантах,

•5. Переместить все рассчитанные пиксели с координатами (х, у) на окружность с центром в точке с координатами (xc,yc) и отметить точки с координатами

• x = x + xc, y = y + yc.

•6. Повторять этапы с 3 по 5 до тех пор, пока не получится x y.

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

•Для вывода контура круга можно использовать соотношение между координатами Х и Y для точек круга X2 + У2 = R2 и построить алгоритм прямого вычисления координат. Однако тогда необходимо вычислять квадратный корень, а это в цифровом компьютере выполняется медленно. Дадим пример записи инкрементного алгоритма Брезенхема на языке С++:

В этом алгоритме использована симметрия круга — в основном цикле вычисляются координаты точек круга только для одного октанта и сразу рисуются восемь симметрично расположенных пикселей.