Алгоритм брезенхема для отрезка прямой линии. Квантовая физика и алгоритм брезенхема

На что вы сейчас смотрите? Если вы не из параллельной вселенной, где все сидят за векторными мониторами, то перед вами растровое изображение. Поглядите на эту полоску: /. Если придвинуться поближе к монитору, то можно увидеть пиксельные ступеньки, которые пытаются притвориться векторной линией. Для этой цели существует целая куча всевозможных алгоритмов растеризации, но я бы хотел рассказать об алгоритме Брезенхема и алгоритме У, которые находят приближение векторного отрезка в растровых координатах.

С проблемой растеризации мне довелось столкнуться во время работы над процедурным генератором планов зданий. Мне нужно было представить стены помещения в виде ячеек двумерного массива. Похожие задачи могут встретиться в физических расчётах, алгоритмах поиска пути или расчёте освещения, если используется разбиение пространства. Кто бы мог подумать, что знакомство с алгоритмами растеризации однажды может пригодиться?

Принцип работы алгоритма Брезенхема очень простой. Берётся отрезок и его начальная координата x . К иксу в цикле прибавляем по единичке в сторону конца отрезка. На каждом шаге вычисляется ошибка - расстояние между реальной координатой y в этом месте и ближайшей ячейкой сетки. Если ошибка не превышает половину высоты ячейки, то она заполняется. Вот и весь алгоритм.

Это была суть алгоритма, на деле всё выглядит следующим образом. Сначала вычисляется угловой коэффициент (y1 - у0)/(x1 - x0) . Значение ошибки в начальной точке отрезка (0,0) принимается равным нулю и первая ячейка заполняется. На следующем шаге к ошибке прибавляется угловой коэффициент и анализируется её значение, если ошибка меньше 0.5 , то заполняется ячейка (x0+1, у0) , если больше, то заполняется ячейка (x0+1, у0+1) и из значения ошибки вычитается единица. На картинке ниже жёлтым цветом показана линия до растеризации, зелёным и красным - расстояние до ближайших ячеек. Угловой коэффициент равняется одной шестой, на первом шаге ошибка становится равной угловому коэффициенту, что меньше 0.5 , а значит ордината остаётся прежней. К середине линии ошибка пересекает рубеж, из неё вычитается единица, а новый пиксель поднимается выше. И так до конца отрезка.

Ещё один нюанс. Если проекция отрезка на ось x меньше проекции на ось y или начало и конец отрезка переставлены местами, то алгоритм не будет работать. Чтобы этого не случилось, нужно проверять направление вектора и его наклон, а потом по необходимости менять местами координаты отрезка, поворачивать оси, и, в конечном итоге, сводить всё к какому-то одному или хотя бы двум случаям. Главное не забывать во время рисования возвращать оси на место.

Для оптимизации расчётов, применяют трюк с умножением всех дробных переменных на dx = (x1 - x0) . Тогда на каждом шаге ошибка будет изменяться на dy = (y1 - y0) вместо углового коэффициента и на dx вместо единицы. Также можно немного поменять логику, «передвинуть» ошибку так, чтобы граница была в нуле, и можно было проверять знак ошибки, это может быть быстрее.

Примерно так может выглядеть код для рисования растровой линии по алгоритму Брезенхема. Псевдокод из Википедии переделанный под C#.

void BresenhamLine(int x0, int y0, int x1, int y1) { var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); // Проверяем рост отрезка по оси икс и по оси игрек // Отражаем линию по диагонали, если угол наклона слишком большой if (steep) { Swap(ref x0, ref y0); // Перетасовка координат вынесена в отдельную функцию для красоты Swap(ref x1, ref y1); } // Если линия растёт не слева направо, то меняем начало и конец отрезка местами if (x0 > x1) { Swap(ref x0, ref x1); Swap(ref y0, ref y1); } int dx = x1 - x0; int dy = Math.Abs(y1 - y0); int error = dx / 2; // Здесь используется оптимизация с умножением на dx, чтобы избавиться от лишних дробей int ystep = (y0 < y1) ? 1: -1; // Выбираем направление роста координаты y int y = y0; for (int x = x0; x <= x1; x++) { DrawPoint(steep ? y: x, steep ? x: y); // Не забываем вернуть координаты на место error -= dy; if (error < 0) { y += ystep; error += dx; } } }

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

Пример кода рисования окружности на C#.

void BresenhamCircle(int x0, int y0, int radius) { int x = radius; int y = 0; int radiusError = 1 - x; while (x >= y) { DrawPoint(x + x0, y + y0); DrawPoint(y + x0, x + y0); DrawPoint(-x + x0, y + y0); DrawPoint(-y + x0, x + y0); DrawPoint(-x + x0, -y + y0); DrawPoint(-y + x0, -x + y0); DrawPoint(x + x0, -y + y0); DrawPoint(y + x0, -x + y0); y++; if (radiusError < 0) { radiusError += 2 * y + 1; } else { x--; radiusError += 2 * (y - x + 1); } } }

Теперь про алгоритм У Сяолиня для рисования сглаженных линий. Он отличается тем, что на каждом шаге ведётся расчёт для двух ближайших к прямой пикселей, и они закрашиваются с разной интенсивностью, в зависимости от удаленности. Точное пересечение середины пикселя даёт 100% интенсивности, если пиксель находится на расстоянии в 0.9 пикселя, то интенсивность будет 10%. Иными словами, сто процентов интенсивности делится между пикселями, которые ограничивают векторную линию с двух сторон.

На картинке выше красным и зелёным цветом показаны расстояния до двух соседних пикселей.

Для расчёта ошибки можно использовать переменную с плавающей запятой и брать значение ошибки из дробной части.

Примерный код сглаженной линии У Сяолиня на C#.

private void WuLine(int x0, int y0, int x1, int y1) { var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); if (steep) { Swap(ref x0, ref y0); Swap(ref x1, ref y1); } if (x0 > x1) { Swap(ref x0, ref x1); Swap(ref y0, ref y1); } DrawPoint(steep, x0, y0, 1); // Эта функция автоматом меняет координаты местами в зависимости от переменной steep DrawPoint(steep, x1, y1, 1); // Последний аргумент - интенсивность в долях единицы float dx = x1 - x0; float dy = y1 - y0; float gradient = dy / dx; float y = y0 + gradient; for (var x = x0 + 1; x <= x1 - 1; x++) { DrawPoint(steep, x, (int)y, 1 - (y - (int)y)); DrawPoint(steep, x, (int)y + 1, y - (int)y); y += gradient; } }

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

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

Отрезок проводится между двумя точками - (x0,y0) и (x1,y1), где в этих парах указаны колонка и строка, соответственно, номера которых растут вправо и вниз. Сначала мы будем предполагать, что наша линия идёт вниз и вправо, причём горизонтальное расстояние x1 − x0 превосходит вертикальное y1 − y0, т.е. наклон линии от горизонтали - менее 45°. Наша цель состоит в том, чтобы для каждой колонки x между x0 и x1, определить, какая строка y ближе всего к линии, и нарисовать точку (x,y).

Общая формула линии между двумя точками:

Поскольку мы знаем колонку x, то строка y получается округлением к целому следующего значения:

Однако, вычислять точное значение этого выражения нет необходимости. Достаточно заметить, что y растёт от y0 и за каждый шаг мы добавляем к x единицу и добавляем к y значение наклона

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

Что из этих двух выбрать - можно решить, отслеживая значение ошибки, которое означает - вертикальное расстояние между текущим значением y и точным значением y для текущего x. Всякий раз, когда мы увеличиваем x, мы увеличиваем значение ошибки на величину наклона s, приведённую выше. Если ошибка превысила 0.5, линия стала ближе к следующему y, поэтому мы увеличиваем y на единицу, одновременно уменьшая значение ошибки на 1. В реализации алгоритма, приведённой ниже, plot(x,y) рисует точку, а abs возвращает абсолютную величину числа:

function line(x0, x1, y0, y1)

int deltax:= abs(x1 - x0)

int deltay:= abs(y1 - y0)

real error:= 0

real deltaerr:= deltay / deltax

int y:= y0

for x from x0 to x1

error:= error + deltaerr

if error >= 0.5

error:= error - 1.0

Пусть начало отрезка имеет координаты (X 1 ,Y 1), а конец(X 1 ,X 2) . Обозначим

Dx=(X 2 -X 1),dy=(Y 2 -Y 1) . Не нарушая общности, будем считать, что начало отрезка совпадает с началом координат, и прямая имеет вид

Где. Считаем что начальная точка находится слева. Пусть на (i-1) -м шаге текущей точкой отрезка является P i -1 =(r,q) . Выбор следующей точки S i или T i зависит от знака разности (s-t). Если (s-t)<0 , то P i =T i =(r+1,q) и тогда

X i +1 =i+1;Y i +1 =Y i , если же (s-t)≥0,то P i =T i =(r+1,q+1) и тогда X i +1 =i+1 ; Y i +1 =Y i +1 ;

dx=(s-t)=2(rdy-qdx)+2dy –dx

Поскольку знак dx=(s-t) совпадает со знаком разности) , то будем проверять знак выражения d i =dx(s-t). . Так как r=X i -1 и q=Y i -1 ,то

d i +1 = d i +2dy -2dx(y i -y i -1) .

Пусть на предыдущем шаге d i <0 , тогда(y i -y i -1)=0 и d i +1 = d i +2dy . Если же на предыдущем шаге d i ≥0 , тогда(y i -y i -1)=1 и d i +1 = d i +2dx(y i -y i -1)

Осталось узнать как вычислить d i . Так как при i=1

Procedure Bresenham(x1,y1,x2,y2,Color: integer);

dx,dy,incr1,incr2,d,x,y,xend: integer;

dx:= ABS(x2-x1);

dy:= Abs(y2-y1);

d:=2*dy-dx; {начальное значение для d}

incr1:=2*dy; {приращение для d<0}

incr2:=2*(dy-dx); {приращение для d>=0}

if x1>x2 then {начинаем с точки с меньшим знач. x}

PutPixel(x,y,Color); {первая точка отрезка}

While x

d:=d+incr1 {выбираем нижнюю точку}

d:=d+incr2; {выбираем верхнюю точку, y-возрастает}

PutPixel(x,y,Color);

26. Общий алгоритм Брезенхема.

Алгоритм выбирает оптимальные растровые координаты для представления отрезка. Большее из приращений, либо Δx, либо Δy, выбирается в качестве единицы растра. В процессе работы одна из координат - либо x, либо y (в зависимости от углового коэффициента) - изменяется на единицу. Изменение другой координаты (на 0 или 1) зависит от расстояния между действительным положением отрезка и ближайшими координатами сетки. Такое расстояние есть ошибкой.

Алгоритм построен так, что требуется лишь знать знак этой ошибки. Следовательно, точка растра (1, 1) лучше аппроксимирует ход отрезка, чем точка (1, 0). Если угловой коэффициент меньше ½, то верно обратное. Для углового коэффициента, равного ½, нет какого-либо предпочтительного выбора. В данном случае алгоритм выбирает точку (1, 1). Так как желательно проверять только знак ошибки, то она первоначально устанавливается равной -½. Таким образом, если угловой коэффициент отрезка больше или равен ½, то величина ошибки в следующей точке растра может быть вычислена как е = -½ + Δy/Δx.

Чтобы реализация алгоритма Брезенхема была полной, необходимо обрабатывать отрезки во всех октантах. Это легко сделать, учитывая в алгоритме номер квадранта, в котором лежит отрезок и его угловой коэффициент. Когда абсолютная величина углового коэффициента больше 1, y постоянно изменяется на единицу, а критерий ошибки Брезенхема используется для принятия решения об изменении величины x. Выбор постоянно изменяющейся (на +1 или -1) координаты зависит от квадранта

var x,y,sy,sx,dx,dy,e,z,i: Integer;
change: boolean;
begin
x:=x1; y:=y1;
dx:=abs(x2-x1); dy:=abs(y2-y1) ;
sx:=sign(x2-x1); sy:=sign(y2-y1);
e:= 2*dy-dx;
if dy
else begin
z:=dx;
dx:=dy; dy:=z;
change:=true
end;
for i:=1 to dx+dy do begin
if dy< dx then begin
if change then y:=y+sy
else x:=x+sx;
e:=e+2*dy;
end else
if change then x:=x+sx
else y:=y+sy;
e:=e-2*dx
end;
Form1.Canvas.Pixels:=clblack; // вывод точки, для примера
end;

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

У растр потрібно розкладати як лінійні, а й інші, більш складні функції. Розкладаннюконічних перерізів, тобто кіл, еліпсів, парабол, гіпербол, було присвячено значнукількість робіт. Найбільшу увагу, зрозуміло, приділено кола. Один з найбільшефективних і простих для розуміння алгоритмів генерації окружності належитьБрезенхему. Для початку зауважимо, що необхідно згенерувати тільки одну восьмучастину кола. Решта її частини можуть бути отримані послідовними відбитками. Якщо згенерований перший октант (від 0 до 45 ° протигодинникової стрілки), то другий Октант можна отримати дзеркальним відображеннямвідносно прямої у = х, що дає в сукупності перший квадрант. Перший квадрант відбивається відносно прямої х = 0 для отримання відповідної частини кола у другому квадранті. Верхня півколо відбивається відносно прямої у = 0 для завершення побудови.

Для виведення алгоритму розглянемо першу чверть кола з центром в початкукоординат. Зауважимо, що якщо робота алгоритму починається в точці х = 0, у = R, то при генерації окружності за годинниковою стрілкою в першому квадраті у ємонотонно спадною функцією аргументів. Аналогічно, якщо вихідною точкою є у = 0, х == R, то при генерації окружності проти годинникової стрілки х будемонотонно спадною функцією аргументу у. У нашому випадку вибирається генерація за годинниковою стрілкою з початком в точці х = 0, у = R. Передбачається, що центр кола та початкова точка перебувають точно в точках растру.

Для будь-якої заданої точки на колі при генерації за годинниковою стрілкою існує тільки три можливості вибрати наступний піксел, найкращим чином наближує окружність: горизонтально вправо, по діагоналі вниз і вправо, вертикально вниз. Алгоритм вибирає піксель, для якого мінімальний квадрат відстані між одним з цих пікселів і окружністю.

28.Понятие фрактала. История фрактальной графики

В повседневной жизни часто можно наблюдать изображение (узоры), которые, казалось бы, нельзя описать математически. Пример: окна зимой замерзают, можно в итоге наблюдать картину. Подобные множества называют фрактальными. Фракталы не похожи на известные фигуры из геометрии, и строятся они по определенным алгоритмам, которые можно реализовать на компьютере. Упрощенно, фрактал - это изображение, полученное в результате некоторого преобразования, многократно примененного к исходной фигуре.
Первые идеи фрактальной геометрии возникли в 19 веке. Кантор с помощью простой рекурсивной процедуры превратил линию в набор несвязанных точек, которые в последствии получили название «Пыль Кантора». Он брал линию и удалял центральную треть и после этого повторял то же самое с оставшимися отрезками. Пеано нарисовал особый вид линии. Для ее рисования Пеано использовал следующий алгоритм:
Он брал прямую линию и заменял её отрезками в три раза меньшей длины, чем у исходной линии. Далее он повторял это же действие с каждым из отрезков. Её уникальность в том, что она заполняет всю плоскость, т.е. для каждой точки, находящейся на плоскости можно найти точку, принадлежащую линии Пеано.
Основателем фрактальной геометрии считается Бенуа Мандельброт . Мандельброт ввел понятие «фрактал».

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

29. Понятие размерности и её расчет

В своей повседневной жизни мы постоянно встречаемся с размерностями. Мы прикидываем длину дороги, узнаем площадь квартиры и т.д. Это понятие вполне интуитивно ясно и, казалось бы, не требует разъяснения. Линия имеет размерность 1. Это означает, что, выбрав точку отсчета, мы можем любую точку на этой линии определить с помощью 1 числа - положительного или отрицательного. Причем это касается всех линий - окружность, квадрат, парабола и т.д.

Размерность 2 означает, что любую точку мы можем однозначно определить двумя числами. Не надо думать, что двумерный - значит плоский. Поверхность сферы тоже двумерна (ее можно определить с помощью двух значений - углов наподобие ширины и долготы).

Если смотреть с математической точки зрения, то размерность определяется следующим образом: для одномерных объектов - увеличение в два раза их линейного размера приводит к увеличению размеров (в данном случае длинны) в два раза (2^1).

Для двумерных объектов увеличение в два раза линейных размеров приводит к увеличению размера (например, площадь прямоугольника) в четыре раза (2^2).

Для 3-х мерных объектов увеличение линейных размеров в два раза приводи к увеличению объема в восемь раз (2^3) и так далее.

Геометрические фракталы

Именно с этим фракталов началась история развития фракталов в целом. Этот тип фракталов получается путем простых геометрических построений. Обычно при построении геометрических фракталов руководствуются следующим алгоритмом:

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

Примеры геометрических фракталов: кривая Пеано, снежинка Коха, лист папоротника, треугольник Серпинского,

Рис. Снежинка Коха

Рис. Лист

Рис. Треугольник Серпинского

Алгебраические фракталы

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

Алгебраические фракталы получили своё название за то, что их строят на основе алгебраических функцій.К алгебраическим фракталам относяться: множество Мандельброта, множество Жюлиа, басейны Ньютона, биоморфы.

-множество Мандельброта: Впервые множество Мандельброта было описано в 1905 году Пьером Фату. Фату изучал рекурсивные процессы вида

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

Фату нашел, что орбита при этом преобразовании показывает достаточно сложное и интересное поведение. Существует бесконечное множество таких преобразований - своё для каждого значения . (названо мандельброта так как он первым провел необходимое количество вычислений использовав компьютер).

-множество Жюлиа : мно́жество Жюлиа́ рационального отображения - множество точек, динамика в окрестности которых в определённом смысле неустойчива по отношению к малым возмущениям начального положения. В случае, если f - полином, рассматривают также заполненное множество Жюлиа - множество точек, не стремящихся к бесконечности. Обычное множество Жюлиа при этом является его границей.

-бассейны Ньютона: Области с фрактальными границами появляются при приближенном нахождении корней нелинейного уравнения алгоритмом Ньютона накомплексной плоскости (для функции действительной переменной метод Ньютона часто называют методом касательных , который, в данном случае, обобщается для комплексной плоскости).

Применим метод Ньютона для нахождения нуля функции комплексного переменного, используя процедуру:

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

-биоморфы: сокращенная форма множества Жюлиа, вычисляеться по формуле z=z 3 +c. Название получила из-за схожести с одноклеточными организмами.

Стохастические фракталы

Типичным представителем данного вида фракталов является так называемая плазма.

Для её построения берут прямоугольник и для каждого его угла определяют цвет. Далее находят центральную точку прямоугольника и раскрашивают её в цвет, равный среднеарифметическому цветов по углам прямоугольника + некоторое случайное число. Чем больше это случайно число - тем более рваным будет рисунок.

Природные объекты часто имеют фрактальную форму. Для их моделирования могут применяться стохастические (случайные) фракталы. Примеры стохастических фракталов:

траектория броуновского движения на плоскости и в пространстве;

граница траектории броуновского движения на плоскости. В 2001 году Лоулер, Шрамм и Вернер доказали предположение Мандельброта о том, что её размерность равна 4/3.

эволюции Шрамма-Лёвнера - конформно-инвариантные фрактальные кривые, возникающие в критических двумерных моделях статистической механики, например, в модели Изинга и перколяции.

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

Фрактальная монотипия, или стохатипия - направления в изобразительном искусстве, заключающиеся в получении изображения случайного фрактала.

Похожая информация.

Сложно сегодня найти человека, который бы не сталкивался с машинной графикой в тех или иных проявлениях. Если человек начинает интересоваться алгоритмами, лежащими в её основе, то одними из первых будут алгоритмы Брезенхема. Беда лишь в том, что мне до сих пор не попадалось простого и вразумительного описания этих алгоритмов, а уж тем более — реализации. В этой статье я попытаюсь по возможности просто рассказать о семействе алгоритмов Брезенхема, а также приведу готовый к использованию код на JavaScript, который практически не отличается от кода на C/C++ . Код можно брать и использовать, предварительно написав автору благодарственное письмо.

Хотелось бы выразить свои глубокие и искренние чувства к разработчикам стандартов www и тем, кто их реализует. Вариант JavaScript-кода, работающий во всех доступных броузерах, т.е. IE 6.0, NN 7.0 и Opera 6.0x, не отличается красотой и изысканностью. Впрочем, «к науке, которую я в настоящий момент представляю, это отношения не имеет».

Итак, назначение алгоритмов Брезенхема — нарисовать линию на растровом устройстве, как правило, на мониторе. Как можно видеть на рисунке 1, не все пиксели, входящие в изображение линии, лежат на этой линии, то есть задача алгоритма — найти наиболее близкие пиксели. Главное достоинство алгоритма Брезенхема в том, что в нём не используется в цикле дорогостоящая операция умножения. Алгоритм подходит для прямых или кривых второго порядка*. Существуют модификации алгоритма для четырёхсвязной (т.е. соседними считаются точки, отличающиеся на 1 по одной координате) и восьмисвязной (т.е. соседними считаются точки, обе координаты которых отличаются не больше, чем на 1) линий. Здесь приведён второй вариант — более сложный, но и дающий лучший результат.

Основная идея алгоритма в том, что линия, которую надо нарисовать, делит плоскость на две части. Уравнение кривой записывается в виде Z = f (x,y) . Во всех точках кривой Z = 0 , в точках, лежащих над кривой Z > 0 , а в точках под кривой Z < 0 . Нам известны координаты начала отрезка, то есть точки, заведомо лежащей на искомой кривой. Ставим туда первый пиксель и принимаем Z = 0 . От текущего пикселя можно сделать два шага — либо по вертикали (по горизонтали), либо по диагонали на один пиксель. Конкретные направления шагов выбираются в зависимости от типа линии, которую надо нарисовать. Делая шаг, мы мы вычисляем, как изменятся значение Z:

ΔZ = Z" x Δx + Z" y Δy

При одном из возможных шагов Z растёт, при другом — уменьшается. Каждый шаг выбирается с тем расчётом, чтобы значение Z для нового пикселя было как можно ближе к 0. Таким образом, мы будем двигаться вдоль линии, создавая её изображение.

Рисование отрезка

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

Оставшиеся отрезки делятся на две группы: горизонтальные и вертикальные. Если представить уравнение прямой в виде y = kx , то горизонтальными считаются отрезки, у которых |k| ≤ 1 , а вертикальными — у которых |k| > 1 . Отнеся отрезок к одной из групп, мы можем поменять местами координаты концов так, чтобы горизонтальные отрезки всегда рисовались слева направо, а вертикальные — сверху вниз.

Для горизонтальных отрезков каждый новый пиксель будет правее предыдущего на 1, при этом он может также быть выше (ниже), т.е. возможны два шага — вправо и вправо-по диагонали. Для вертикальных отрезков возможные шаги — вниз и вниз-по диагонали.

Если координаты концов отрезка (x 1 ,y 1) и (x 2 ,y 2) соответственно, то при каждом шаге по оси x Z изменяется на 1, а по оси y — на (x 2 -x 1)/(y 2 -y 1) . Чтобы не связываться с делением и остаться в пределах целочисленной арифметики, переменную Z будем изменять соответственно на y2-y1 и x2-x1 . Вот, собственно, и вся математика, остальное можно понять из кода.

Рисование окружности

Алгоритм рисования дуги останется за рамками статьи, а вот алгоритм для рисования окружности получился значительно проще, чем для прямой. Связано это со многими причинами.

Во-первых, мы рисуем только одну восьмую часть окружности — от π/2 до π/4 , причём в обратном направлении, то есть по часовой стрелке. Вся остальная окружность получается путём отражения этой части относительно центра окружности, горизонтальной и вертикальной осей, а также прямых y = x + b и y = -x + b , проходящих через центр окружности.

Во-вторых из-за симметрии отклонения линии от окружности не так заметны, как отклонения от прямой, поэтому Z можно сравнивать с нулём, не вычисляя максимально допустимого отклонения.

Допустимые шаги — вправо и вправо-по диагонали, а изменение Z зависит от значений x и y , но зависимость линейная, поэтому операция умножения не требуется.

Вот, собственно, и всё. Ниже вы найдёте скрипт, демонстрирующий работу описанных алгоритмов, а для того, чтобы понять, как он работает, просто посмотрите исходный текст страницы.

Удачи!

Если хотите увидеть демонстрацию работы алгоритмов в окне броузера, включите JavaScript!

x1:		y1:
x2:		y2:

x0:		y0:
R:

Значительная часть школьного курса геометрии посвящена задачам на построение. Вопросы, связанные с алгоритмами построения геометрических фигур, интересовали еще математиков древности. Более поздние исследования показали их тесную связь с фундаментальными вопросами математики (достаточно вспомнить классические задачи о трисекции угла и квадратуре круга). Появление ЭВМ поставило перед математиками принципиально новые вопросы, которые не могли возникнуть в докомпьютерную эпоху. К их числу относятся задачи построения элементарных графических объектов - линий и окружностей.

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

В компьютерной графике дело обстоит иначе. Элементарная составляющая всех фигур - точка - обретает реальные физические размеры, а вопросы вида "сколько точек содержит данная фигура?" никого не удивляют. Мы попадаем в конечный мир, где все можно сравнить, измерить, подсчитать. Даже само слово "точка" употребляется редко. Его заменяет термин пиксель (pixel - от picture element - элемент картинки). Если взглянуть на экран дисплея сквозь увеличительное стекло, то можно увидеть, что фрагмент изображения, который невооруженному глазу кажется сплошным, на самом деле состоит из дискретного множества пикселей. Впрочем, на дисплеях с невысокой разрешающей способностью это можно наблюдать и без увеличительного стекла.

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

Имеется и другой аспект проблемы. Допустим, вы хотите съесть яблоко. Имеет ли для вас значение, съедите вы все яблоко целиком или разделите его на 2 половинки и съедите каждую из них отдельно? Скорее всего, если яблоко достаточно вкусное, вы охотно согласитесь на оба варианта. А вот с точки зрения программиста, поделив прекрасное целое яблоко пополам, вы совершаете огромную ошибку. Ведь вместо замечательного целого числа вам приходится иметь дело с двумя дробными, а это значительно хуже. По той же самой причине из двух равенств 1+1=2 и 1,5+0,5=2 программист всегда выберет первое - ведь в нем нет этих непрятных дробных чисел. Такой выбор связан с соображениями повышения эффективности работы программ. В нашем случае, когда речь идет об алгоритмах построения элементарных графических объектов, которые предполагают многократное применение, эффективность является обязательным требованием. Большинство микропроцессоров имеет лишь средства целочисленной арифметики и не располагает встроенными возможностями для операций над вещественными числами. Безусловно, такие операции реализуются, но при этом бывает, что одна операция требует выполнения компьютером до десятка и более команд, что существенным образом влияет на время выполнения алгоритмов.

Статья посвящена рассмотрению одного из шедевров искусства программирования - алгоритму построения окружности, предложенному Брезенхемом (Brezenham). Требуется разработать метод построения окружности на целочисленной координатной сетке по координатам центра и радиусу. Мы должны также максимально сократить время выполнения алгоритма, что заставляет оперировать по возможности целыми числами. Каким графическим инструментарием мы располагаем? Практически никаким. Безусловно, мы должны уметь ставить точку (pixel) в нужном месте экрана. К примеру, языки программирования фирмы Borland содержат процедуру putpixel, с помощью которой можно оставить на экране точку, имеющую нужные координаты и цвет. Цвет для нас значения не имеет, для определенности пусть он будет белым.

1. От чего придется отказаться...

Представим себе, что мы не ограничены в средствах. Что мы не только можем оперировать с дробными числами, но и использовать трансцендентные тригонометрические функции (такое, кстати, вполне возможно на машинах, оснащенных математическим сопроцессором, который берет на себя подобные вычисления). Задача все та же - построить окружность. Что мы станем делать? Вероятно, мы вспомним формулы, параметрически определяющие окружность. Эти формулы достаточно просты и могут быть получены непосредственно из определения тригонометрических функций. Согласно им окружность радиуса R с центром в точке (x 0 , y 0) может быть определена как множество точек M (x , y ), координаты которых удовлетворяют системе уравнений

x = x 0 + R cos a

y = y 0 + R sin a ,

где a О = 2x 2 i +1 +2y 2 i +1 +4x i +1 -2y i +1 +3-2R 2 = 2(x i +1) 2 +2y i 2 +4(x i +1)-2y i +3-2R 2 = D i +4x i +6.

D i +1 [при y i +1 = y i -1] = 2x 2 i +1 +2y 2 i +1 +4x i +1 -2y i +1 +3-2R 2 = 2(x i +1) 2 +2(y i -1) 2 +4(x i +1)-2(y i -1)+3-2R 2 = D i +4(x i -y i )+10.

Теперь, когда получено рекуррентное выражение для D i +1 через D i , остается получить D 1 (контрольную величину в начальной точке.) Она не может быть получена рекуррентно, ибо не определено предшествующее значение, зато легко может быть найдена непосредственно

x 1 = 0, y 1 = R Ю D 1 1 = (0+1) 2 +(R -1) 2 -R 2 = 2-2R ,

D 1 2 = (0+1) 2 +R 2 -R 2 = 1

D 1 = D 1 1 +D 1 2 = 3-2R .

Таким образом, алгоритм построения окружности, реализованный в bres_circle, основан на последовательном выборе точек; в зависимости от знака контрольной величины D i выбирается следующая точка и нужным образом изменяется сама контрольная величина. Процесс начинается в точке (0, r ), а первая точка, которую ставит процедура sim, имеет координаты (xc , yc +r ). При x = y процесс заканчивается.

Пример кода рисования окружности на C#.

На картинке выше красным и зелёным цветом показаны расстояния до двух соседних пикселей.

Примерный код сглаженной линии У Сяолиня на C#.