Формула для рисования окружности
Алгоритмы взяты из прекрасной книги
П.В.Вельтмандер «Машинная графика»
Во многих областях приложений, таких как, например, системы автоматизированного проектирования машиностроительного направления, естественными графическими примитивами, кроме отрезков прямых и строк текстов, являются и конические сечения, т.е. окружности, эллипсы, параболы и гиперболы. Наиболее употребительным примитивом, естественно, является окружность. Один из наиболее простых и эффективных алгоритмов генерации окружности разработан Брезенхемом.
1 Алгоритм Брезенхема
Для простоты и без ограничения общности рассмотрим генерацию 1/8 окружности, центр которой лежит в начале координат. Остальные части окружности могут быть получены последовательными отражениями (использованием симметрии точек на окружности относительно центра и осей координат).
Окружность с центром в начале координат описывается уравнением:
|
Алгоритм Брезенхема пошагово генерирует очередные точки окружности, выбирая на каждом шаге для занесения пиксела точку растра Pi(Xi, Yi), ближайшую к истинной окружности, так чтобы ошибка:
|
была минимальной. Причем, как и в алгоритме Брезенхема для генерации отрезков, выбор ближайшей точки выполняется с помощью анализа значений управляющих переменных, для вычисления которых не требуется вещественной арифметики. Для выбора очередной точки достаточно проанализировать знаки.
Рассмотрим генерацию 1/8 окружности по часовой стрелке, начиная от точки X=0, Y=R.
Проанализируем возможные варианты занесения i+1-й точки, после занесения i-й.
При генерации окружности по часовой стрелке после занесения точки (Xi, Yi) следующая точка может быть (см. рис. 0.1а) либо Pg = (Xi+1, Yi) — перемещение по горизонтали, либо Pd = (Xi+1, Yi-1) — перемещение по диагонали, либо Pv = (Xi, Yi-1) — перемещение по вертикали.
Для этих возможных точек вычислим и сравним абсолютные значения разностей квадратов расстояний от центра окружности до точки и окружности:
| ||||||||||||||||||||||||||||||||||||||||
Выбирается и заносится та точка, для которой это значение минимально.
Выбор способа расчета определяется по значению Dd. Если Dd 0, то диагональная точка вне окружности. Это варианты 5-7. И, наконец, если Dd = 0, то диагональная точка лежит точно на окружности. Это вариант 4. Рассмотрим случаи различных значений Dd в только что приведенной последовательности.
Случай Dd
Здесь в качестве следующего пиксела могут быть выбраны или горизонтальный — Pg или диагональный — Pd.
Для определения того, какой пиксел выбрать Pg или Pd составим разность:
| |||||||||
И будем выбирать точку Pg при di Ј 0, в противном случае выберем Pd.
Рассмотрим вычисление di для разных вариантов.
Для вариантов 2 и 3:
Dg і 0 и Dd
|
Добавив и вычтя (Y-1) 2 получим:
|
В квадратных скобках стоит Dd, так что
|
Для варианта 1:
Ясно, что должен быть выбран горизонтальный пиксел Pg. Проверка компонент di показывает, что Dg Случай Dd > 0
Здесь в качестве следующего пиксела могут быть выбраны или диагональный — Pd или вертикальный Pv.
Для определения того, какую пиксел выбрать Pd или Pv составим разность:
| |||||||||
Если si Ј 0, то расстояние до вертикальной точки больше и надо выбирать диагональный пиксел Pd, если же si > 0, то выбираем вертикальный пиксел Pv.
Рассмотрим вычисление si для разных вариантов.
Для вариантов 5 и 6:
Dd > 0 и Dv Ј 0, так как диагональный пиксел вне, а вертикальный либо вне либо на окружности.
|
Добавив и вычтя (X+1) 2 получим:
|
В квадратных скобках стоит Dd, так что
|
Для варианта 7:
Ясно, что должен быть выбран вертикальный пиксел Pv. Проверка компонент si показывает, что Dd > 0 и Dv > 0, причем si > 0, так как диагональная точка больше удалена от окружности, т.е. по критерию si > 0 как и в предыдущих случаях следует выбрать вертикальный пиксел Pv, что соответствует выбору для вариантов 5 и 6.
Случай Dd = 0
Для компонент di имеем: Dg > 0 и Dd = 0, следовательно по критерию di > 0 выбираем диагональный пиксел.
С другой стороны, для компонент si имеем: Dd = 0 и Dv Ј 0 также выбираем диагональный пиксел.
Dd Ј 0 — выбор горизонтального пиксела Pg
di > 0 — выбор диагонального пиксела Pd
si Ј 0 — выбор диагонального пиксела Pd
si > 0 — выбор вертикального пиксела Pv
выбор диагонального пиксела Pd.
Выведем рекуррентные соотношения для вычисления Dd для (i+1)-го шага, после выполнения i-го.
1. Для горизонтального шага к Xi+1, Yi
2. Для диагонального шага к Xi+1, Yi-1
3. Для вертикального шага к Xi, Yi-1
В Приложении 5 приведена подпрограмма V_circle, реализующая описанный выше алгоритм и строящая дугу окружности в первой четверти. Начальная инициализация должна быть:
Dd = (X+1) 2 + (Y-1) 2 — R 2 = 1 + (R-1) 2 — R 2 = 2*(1 — R)
Пикселы в остальных четвертях можно получить отражением. Кроме того достаточно сформировать дугу только во втором октанте, а остальные пикселы сформировать из соображений симметрии, например, с помощью подпрограммы Pixel_circle, приведенной в Приложении и заносящей симметричные пикселы по часовой стрелке от исходного.
В Приложении приведены подпрограмма V_BRcirc, реализующая описанный выше алгоритм и строящая дугу окружности во втором октанте с последующим симметричным занесением пикселов. Эта процедура может строить и 1/4 окружности. Подробнее см. текст Приложения. Там же приведена более короткая подпрограмма, строящая 1/8 окружности методом Мичнера [], (том 1, стр. 152). Остальная часть окружности строится симметрично.
0.15 Приложение 4. Процедуры генерации окружности
В данном приложении помещены процедуры генерации окружностей по алгоритму Брезенхема и Мичнера, а также программа T_Circle для тестирования данных процедур.
Источник
Алгоритм Брезенхема построения окружности.
Значительная часть школьного курса геометрии посвящена задачам на построение. Вопросы, связанные с алгоритмами построения геометрических фигур, интересовали еще математиков древности. Более поздние исследования показали их тесную связь с фундаментальными вопросами математики (достаточно вспомнить классические задачи о трисекции угла и квадратуре круга). Появление ЭВМ поставило перед математиками принципиально новые вопросы, которые не могли возникнуть в докомпьютерную эпоху. К их числу относятся задачи построения элементарных графических объектов — линий и окружностей.
Любая геометрическая фигура может быть определена как некоторое множество точек плоскости. В геометрии это множество, как правило, бесконечно; даже отрезок содержит бесконечно много точек.
В компьютерной графике дело обстоит иначе. Элементарная составляющая всех фигур — точка — обретает реальные физические размеры, а вопросы вида «сколько точек содержит данная фигура?» никого не удивляют. Мы попадаем в конечный мир, где все можно сравнить, измерить, подсчитать. Даже само слово «точка» употребляется редко. Его заменяет термин пиксель (pixel — от picture element — элемент картинки). Если взглянуть на экран дисплея сквозь увеличительное стекло, то можно увидеть, что фрагмент изображения, который невооруженному глазу кажется сплошным, на самом деле состоит из дискретного множества пикселей. Впрочем, на дисплеях с невысокой разрешающей способностью это можно наблюдать и без увеличительного стекла.
Пиксель нельзя разделить, так как он является минимальным элементом изображения — не бывает «двух с половиной пикселей». Таким образом, в компьютерной графике мы фактически располагаем целочисленной координатной сеткой, в узлах которой ставятся точки. Во всех алгоритмах, обслуживающих компьютерную графику, должно быть учтено это обстоятельство 2 .
Имеется и другой аспект проблемы. Допустим, вы хотите съесть яблоко. Имеет ли для вас значение, съедите вы все яблоко целиком или разделите его на 2 половинки и съедите каждую из них отдельно? Скорее всего, если яблоко достаточно вкусное, вы охотно согласитесь на оба варианта. А вот с точки зрения программиста, поделив прекрасное целое яблоко пополам, вы совершаете огромную ошибку. Ведь вместо замечательного целого числа вам приходится иметь дело с двумя дробными, а это значительно хуже. По той же самой причине из двух равенств 1+1=2 и 1,5+0,5=2 программист всегда выберет первое — ведь в нем нет этих непрятных дробных чисел. Такой выбор связан с соображениями повышения эффективности работы программ. В нашем случае, когда речь идет об алгоритмах построения элементарных графических объектов, которые предполагают многократное применение, эффективность является обязательным требованием. Большинство микропроцессоров имеет лишь средства целочисленной арифметики и не располагает встроенными возможностями для операций над вещественными числами. Безусловно, такие операции реализуются, но при этом бывает, что одна операция требует выполнения компьютером до десятка и более команд, что существенным образом влияет на время выполнения алгоритмов.
Статья посвящена рассмотрению одного из шедевров искусства программирования — алгоритму построения окружности, предложенному Брезенхемом (Brezenham). Требуется разработать метод построения окружности на целочисленной координатной сетке по координатам центра и радиусу. Мы должны также максимально сократить время выполнения алгоритма, что заставляет оперировать по возможности целыми числами. Каким графическим инструментарием мы располагаем? Практически никаким. Безусловно, мы должны уметь ставить точку (pixel) в нужном месте экрана. К примеру, языки программирования фирмы Borland содержат процедуру putpixel, с помощью которой можно оставить на экране точку, имеющую нужные координаты и цвет. Цвет для нас значения не имеет, для определенности пусть он будет белым.
1. От чего придется отказаться.
Представим себе, что мы не ограничены в средствах. Что мы не только можем оперировать с дробными числами, но и использовать трансцендентные тригонометрические функции (такое, кстати, вполне возможно на машинах, оснащенных математическим сопроцессором, который берет на себя подобные вычисления). Задача все та же — построить окружность. Что мы станем делать? Вероятно, мы вспомним формулы, параметрически определяющие окружность. Эти формулы достаточно просты и могут быть получены непосредственно из определения тригонометрических функций. Согласно им окружность радиуса R с центром в точке (x0, y0) может быть определена как множество точек M(x, y), координаты которых удовлетворяют системе уравнений
| м | x = x0 + R cos a y = y0 + R sin a , | где a О [0;2 p ). |
| н | ||
| о |
Составить программу, реализующую построение окружности по приведенным формулам, совсем не сложно. Мы приведем такую программу на Паскале. При этом воспользуемся процедурами moveto и lineto, первая из которых устанавливает графический курсор на место с указанными координатами, а вторая — проводит линию от текущего положения курсора до точки, координаты которой являются ее параметрами. Использование этих процедур, безусловно, является еще одним отступлением от сформулированных нами правил, но ведь мы уже и так отошли от них, воспользовавшись тригонометрическими функциями.
Если вы располагаете временем и достаточно любопытны, то можете попробовать определить время, которое потребуется для изображения, к примеру, тысячи произвольных окружностей с помощью нашей процедуры, и сохранить его с временем, которое понадобится на то же самое с использованием стандартной процедуры circle. Не сомневаемся, что полученные результаты убедят вас в правильности названия этого параграфа. Кроме всего прочего, необходимо сделать следующее замечание: на самом деле мы строим не окружность, а правильный 360-угольник. Весьма вероятно, что в недалеком будущем аппаратные средства позволят добиться такой разрешающей способности дисплеев, что отличие многоугольника от окружности станет заметным на глаз. Что мы станем делать тогда? Уменьшим шаг приращения угла? Это неплохой выход, но такая ситуация обещает повториться. Итак, приведенный алгоритм нас не устраивает. Надо поискать что-нибудь свободное от упомянутых недостатков.
2. Это похоже на фокус.
Математики любят удивлять. Загадайте. умножьте. разделите. сложите. теперь забудьте то, что вы задумали, и назовите первое число, которое вам придет в голову. Вы задумали. Это, конечно, развлечение. Но и настоящая, серьезная математика способна преподносить не менее удивительные сюрпризы. Алгоритм Брезенхема является одним из таких сюрпризов. Ниже приведена реализация этого алгоритма на Паскале. Изучите ее. Убедитесь, что программа действительно работает. Удивитесь, ибо ничего другого вам не остается. В следующем параграфе вас ждет увлекательный разбор алгоритма.
3. Что у него внутри?
Перед тем как приступить к рассмотрению алгоритма, договоримся о расположении осей координат. Мы привыкли к обычной декартовой системе координат с положительным направлением осей вправо и вверх. Как правило, в графических системах используется другая система координат — с положительным направлением оси ординат вниз и началом координат в левом верхнем углу экрана. Мы станем пользоваться привычной нам системой координат. Преобразование координат в экранные может быть легко осуществлено, но в этом, как вы убедитесь ниже, нет никакой необходимости.
Обратимся к тексту процедуры bres_circle. Она использует процедуру sim, которая, как можно видеть, расставляет восемь точек вокруг точки (xc,yc) (центра нашей окружности). Эта процедура реализует следующее: окружность обладает центром симметрии и бесконечным количеством осей симметрии. Поэтому нет необходимости строить всю окружность, достаточно построить некоторую ее часть и последовательным применением преобразований симметрии получить из нее полную окружность. Мы станем строить 1/8 часть окружности, заключенную в Р AOB (рис. 1).
Каждая точка этого фрагмента должна быть еще семь раз отображена с помощью преобразований симметрии для получения полной окружности.
Кроме того, именно процедура sim отвечает за расположение центра окружности. Главная процедура вполне может считать, что она строит окружность с центром в начале координат.
Приступим к разбору ключевой идеи алгоритма. Пусть мы находимся в некоторой промежуточной фазе построения. Мы только что поставили точку (xi, yi) и теперь должны сделать выбор между точками 1(xi+1, yi-1) и 2(xi+1, y) (рис. 2). (Напомним, что мы строим часть окружности, заключенную в Р AOB, следовательно, подняться выше мы не можем и спуститься вниз более чем на одну точку не можем тоже.)
Реальная окружность может быть расположена относительно точек 1 и 2 одним из пяти способов 1-5. Если мы выбераем точку 1, то тем самым говорим, что (xi+1) 2 +(yi-1) 2 » R 2 . Если же выбераем точку 2, то допускаем, что (xi+1) 2 +(yi) 2 » R 2 . Рассмотрим две погрешности D i 1 и D i 2:
и контрольную величину D i = D i 1+ D i 2. При выборе точки, следующей за (xi, yi), станем руководствоваться следующим критерием:
если D i > 0, выберем точку 1;
если D i Ј 0, выберем точку 2.
Обоснуем разумность такого выбора. Рассмотрим знаки погрешностей D i 1 и D i 2 и их влияние на знак контрольной величины D i для всех пяти возможных положений окружности.
Для положения 1.
Для положения 2.
Для положения 3 возможны варианты (учитывая, что D i 1 D i 2 > 0).
Для положения 4.
Для положения 5.
Далее получим выражение для контрольной величины D i
Выражение для D i+1 существенным образом зависит от выбора следующей точки. Необходимо рассмотреть два случая: yi+1 = yi и yi+1 = yi-1.
Теперь, когда получено рекуррентное выражение для D i+1 через D i , остается получить D 1 (контрольную величину в начальной точке.) Она не может быть получена рекуррентно, ибо не определено предшествующее значение, зато легко может быть найдена непосредственно
Таким образом, алгоритм построения окружности, реализованный в bres_circle, основан на последовательном выборе точек; в зависимости от знака контрольной величины D i выбирается следующая точка и нужным образом изменяется сама контрольная величина. Процесс начинается в точке (0, r), а первая точка, которую ставит процедура sim, имеет координаты (xc, yc+r). При x = y процесс заканчивается.
Источник
