Использование рекурсии в компьютерной графике

    Содержание

    Введение 3

    Глава I. Теоретическая часть 5

    1.1. Компьютерная графика 5

    1.2. Рекурсия 6

    1.3. Использование рекурсии в компьютерной графике 7

    Глава II. Решение частных задач 16

    Задача 1. 16

    Задача 2. 16

    Задача 3. 17

    Задача 4. 18

    Разработка приложения 22

    Заключение 23

    Литература 24

    Приложение 25 

    Введение

Компьютерная  графика - это область информатики, занимающаяся проблемами получения различных изображений (рисунков, чертежей, мультипликации) на компьютере. Работа с компьютерной графикой - одно из самых популярных направлений использования персонального компьютера, причем занимаются этой работой не только профессиональные художники и дизайнеры. На любом предприятии время от времени возникает необходимость в подаче рекламных объявлений в газеты и журналы, в выпуске рекламной листовки или буклета. Иногда предприятия заказывают такую работу специальным дизайнерским бюро или рекламным агенствам, но часто обходятся собственными силами и доступными программными средствами. 
Без компьютерной графики не обходится ни одна современная программа. Работа над графикой занимает до 90% рабочего времени программистких коллективов, выпускающих программы массового применения. 
Основные трудозатраты в работе редакций и издательств тоже составляют художественные и оформительские работы с графическими прораммами. 
Необходимость широкого использования графических программных средств стала особенно ощутимой в связи с развитием Интернета и, в первую очередь, благодаря службе World Wide Web, связавшей в единую "паутину" миллионы "домашних страниц". У страницы, оформленной без компьютерной графики мало шансов привлечь к себе массовое внимание.

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

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

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

      Практически все геометрические фракталы задаются в форме бесконечной рекурсии.

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

      Цель  курсовой работы – изучить применение рекурсии в компьютерной графике. 
 
 
 
 
 
 
 
 
 

    Глава I. Теоретическая часть

    Рекурсивные алгоритмы

    Ситуация, когда алгоритм вызывает себя в качестве вспомогательного, называется рекурсией (это слово происходит от латинского recursio — возвращение). Рекурсивными бывают подпрограммы-процедуры и подпрограммы-функции. В рекурсивных подпрограммах в теле процедуры или функции имеется вызов этих же подпрограмм. Процесс обращения к себе самому может длиться бесконечно. Для обеспечения остановки устанавливают барьер в виде некоторого условия.

    № 1. Знакомство с рекурсивными алгоритмами

    Пример 1. Написать программу построения изображения, представленного на следующем рисунке:

    

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

    описать процедуру изображения одной  окружности с четырьмя окружностями поменьше;

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

    Опишем  алгоритм рисования окружности радиуса  r с центром в точке (х,у) с четырьмя окружностями вокруг. При этом необходимо знать расстояния (r1) от точки (х,у) до центров окружностей окружения (радиусы орбиты), которые, очевидно равны. Пусть , где - радиус окружности окружения, . 

    Procedure Picturel (х,у, r, rl :Integer);

    Begin

    { изобразить  окружность с центром (х,у) и радиусом r}

    For i:=1 To 4 Do

    Begin {вычислить координаты центра (xl,yl) i-й окружности};

    Picturel(xl,yl,<новое значение r>, rl);

    End;

    End.

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

    Как вычислить значения xl, у1? Они зависят от х и у следующим образом: xl = х + dx, yl = у + dy. Необходимо выразить значения приращений координат dx, dy. Воспользуемся определениями тригонометрических функций sin и cos:

    dx = rl - cos(a)

    dy = rl - sin(a), где a= p/2, p , 3p/2, 2p. 

    Если  осуществить вызов этой же процедуры  из основной программы с начальными параметрами, то рекурсивные вызовы никогда не закончатся и программа будет работать бесконечно. Для того, чтобы этого не случилось, можно ввести в качестве аргумента процедуры некоторую величину п, которая при каждом новом вызове процедуры будет уменьшаться на 1, а в тело процедуры что его операторы должны выполняться только при п > 0, то есть это условие должно играть роль своеобразной «заглушки», ограничивающей число вызовов.

    Ниже  приведена программа, полностью  решающая поставленную задачу.

    В основной программе запрашиваются  радиус r самой большой окружности и число уровней п, а также задаются значения коэффициентов k1 и k2. Центр самой окружности располагается в центре экрана.

    Program Example_1;

    Uses Graph;

    Var х, у, n, r, rl,cd,gm:Integer;

    kl,k2:Real;

    Procedure Picture1(x,y,r,rl,n:Integer);

    Var xl,yl:Integer;

    i:Integer;

    Begin

    If n>0 Then {"заглушка"} Begin

    circle (x, y, r); {рисование окружности,}

    rl:=trunc(r*k2);  {вычисление радиуса орбиты}

    For i:=l To 4 Do

    Begin

    xl:=trunc(x+rl*cos (pi/2*i));

    yl:=trunc(y+rl*sin (pi/2*i)); {координаты центра i-й окружности}

    picture1 (xl,yl,trunc(r*kl),rl,n-l);

    {вызов  процедуры с новыми параметрами} 

    End;

    End;

    End;

    Begin {Задание начальных значений}

    Writeln(‘Введите число уровней n.’);

    Readln(n); x:=600 Div 2; y:=400 Div 2;

    Writeln(‘Введите радиус первой окружности r’);

    Readln(r);

    K1:=0.3; k2:=2;

    Cd:=detect; gm:=1;   { инициализация графики }

    Initgraph(cd,gm,’c:\tp7_0\bin’);

    Picture1(x,y,r1,n);

    Readln;   { задержка на экране }

    Closegraph;

    End. 

    Примечания:

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

    Изменяя в процессе демонстрации работы программы  значения k1, k2, п, можно получать множество привлекательных рисунков. 

    66. Снежинка. Разработать программу, которая обеспечивает рисование снежинки, число звеньев и число ветвей которой задаются пользователем.

    На  рисунке ниже изображена снежинка, состоящая из трех звеньев и восьми ветвей.

    Сделаем расчет длины каждого звена по известному значению п — звеньев и величине экрана. Будем считать, что снежинка строится в квадрате 400 * 400 , центр снежинки совпадает с центром квадрата, а длина отрезка каждого очередного звена в четыре раза меньше предыдущего. Если через l обозначить длину первого звена, то справедливо следующее равенство: 

      

    то  есть

    / = 200 х 3 х •

    4" -1 '

    Пусть снежинка состоит из одного звена  и р ветвей, тогда соответствующая программа проста. Основная ее часть имеет вид

         For  i:=1   То р Dо

    X1:=trunc(х+1*соs(2*рi*(i-1)/р) :=Ъгипс(у+1*з1п (2*р1* (1-1)/р) {координаты конца очередного 11пе (х, у, х1, у!) ;     {рисование звена} Еш1;

    Здесь х, у -- координаты точки центра снежинки. Наша снежинка рисуется как бы много раз, при этом длины звеньев изменяются, поэтому их надо просчитать один раз и запомнить в массиве X из  n элементов. Длина каждого звена уменьшается в четыре раза по отношению к предыдущему. Длина первого звена определяется из того, что в квадрате из 400 * 400 точек необходимо построить снежинку из п звеньев. Если мы дошли до этапа рисования самого маленького звена (самой маленькой снежинки), то наша программа должна работать как приведенный набросок.

    Итак, логика решения задачи.

    Начинаем  рисовать из центра, точки А, нарисовали первый отрезок АВ (а), если это не последнее звено, то будем рисовать отрезок следующего звена ВС, звено не последнее, поэтому продолжим. Предположим, что нарисовали СЕ, это первая ветвь самой маленькой снежинки, наша программа должна работать как набросок, то есть рисовать все ветви этой снежинки. После этого мы должны

    вернуться в точку В. Так как это не последняя ветвь этой снежинки, то мы снова нарисовать следующую ветвь — отрезок ВО (б), а затем снова полностью маленькую снежинку. Что необходимо для реализации этой логики? Пусть переменной 1с будет равно текущему номеру звена снежинки, в начальный момент оно равно п. Тогда при переходе от точек С, О к точке В мы должны «вспомнить» координаты точки В и номер ветви снежинки, рисуемой из точки В. При переходе от точки В к точке А мы должны «вспомнить» координаты точки А и номер ветви снежинки, рисуемой из точки А. Эта логика легко реализуется с по-рекурсии.