9. Алгоритмы рисования линий.

Цифровой дифференциальный анализатор

Пусть дано уравнение линии Y(X). Для отрезка прямой уравнение имеет вид Y(X)=kx+b, где , - приращение координат отрезка по оси X, - приращение координат отрезка по оси Y.

Вычислим производную:

.

Для генерации отрезка из точки (x₁,y₁) в точку (x₂,y₂) в первом октанте (P_x  P_y  0) алгоритм несимметричного ЦДА имеет вид:

1. Вычислить приращения координат:

Px= x2 - x1; Py= y2 - y1; k=Py/Px;

2. Занести начальную точку отрезка

// PutPixel(]x1[,]y1[);

xn:=x1; yn:=y1;

1. Сгенерировать отрезок

while (x1<x2) do

begin

x1:=x1+1.0; y1:=y1+k; line(dx+round(xn),dy-round(yn),dx+round(x1),dy-round(y1));

xn:=x1; yn:=y1; end;

Здесь ]x1[, ]y1[ означает взятие целой части.

Алгоритм Брезенхема

Брезенхем предложил алгоритм, обеспечивающий минимизацию отклонения сгенерированного образа от истинного отрезка.

Для принятия решения, куда заносить пиксель, вводится величина отклонения Е точной позиции от середины между двумя возможными точками.

Если Е < 0, то Y-координата не меняется. В противном случае Y увеличивается на 1.

Для генерации отрезка из точки (x₁,y₁) в точку (x₂,y₂) в первом октанте (P_x  P_y  0) алгоритм Брезенхема имеет вид:

1. Вычислить приращения координат:

Px= x2 - x1;

Py= y2 - y1;

k=Py/Px;

x=]x1[;

y=]y1[;

2. Инициализация е с поправкой на полпикселя:

e=k-0.5;

3. Занести начальную точку отрезка

//PutPixel(x,y);

xn:=x; yn:=y;

4. Сгенерировать отрезок

while (x<x2) do

begin

while (e>=0)

begin

y:=y+1;

e:=e-1;

end;

x:=x+1; e:=e+k; line(dx+xn,dy-yn,dx+x,dy-y); end;

Здесь ]x1[, ]y1[ означает взятие целой части.

10. Рисование фракталов.

Понятия фрактал и фрактальная геометрия, появившиеся в конце 70-х, с середины 80-х прочно вошли в обиход математиков и программистов. Слово фрактал образовано от латинского fractus и в переводе означает состоящий из фрагментов. Оно было предложено Бенуа Мандельбротом в 1975 году для обозначения нерегулярных, но самоподобных структур, которыми он занимался. Рождение фрактальной геометрии принято связывать с выходом в 1977 году книги Мандельброта ″The Fractal Geometry of Nature″. В его работах использованы научные результаты других ученых, работавших в период 1875-1925 годов в той же области (Пуанкаре, Фату, Жюлиа, Кантор, Хаусдорф). Но только в наше время удалось объединить их работы в единую систему.

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

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

Определение фрактала, данное Мандельбротом, звучит так: "Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому".