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

    ИСПОЛЬЗОВАНИЕ РЕКУРСИИ В ГРАФИКЕ

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

    Задача. Составить рекурсивный алгоритм рисования окружностей следующего вида:

    Центральная окружность радиуса R, на этой окружности симметрично располагаются 4 окружности радиуса R/2 каждая. На каждой из этих 4-х  окружностях аналогичным образом  строятся еще 4 и т.д. Рисование прекращается, если радиус последних становится меньше некоторого числа k. Рисование окружностей  будем производить относительно центральной окружности с центром (x,y). Центр первой окружности - (x+R,y), второй - (x,y+R), третьей - (x-R,y), четвертой - (x,y-R).

    Решение:

    uses crt,graph;

    var

       gd,gm,mx,my:integer;

       ch         :char;

    procedure krug(x,y,r:integer);

    begin

       if r>k then

          begin 

                krug(x+r,y,r div 2);

                krug(x,y+r,r div 2);

                krug(x-r,y,r div 2); 

                krug(x,y-r,r div 2);

          end;

       circle(x,y,r);

    end;

    Procedure Init; {инициализация графического  режима}

    var err: integer;

    begin

          DetectGraph(gd,gm);

          InitGraph(gd,gm,' путь драйвера');

          if GraphResult<>grok then

             begin  

                   Writeln(GraphErrorMsg(err));

                   Readln; Halt(1);  

             end;

    end

    BEGIN

          Init;

          krug(getmaxX div 2, getmaxY div 2, getmaxY div 4);

    END.   

    КРИВЫЕ  ГИЛЬБЕРТА

    Этот  узор состоит из суперпозиции пяти кривых. Три наложенные друг на друга  кривые имеют форму Н₁, Н₂ и Н₃.

    Н_i+1 получается соединением четырех экземпляров Н_i вдвое меньшего размера, повернутых соответствующим образом и "стянутых" вместе тремя прямыми линиями. Н₁ можно считать состоящей из четырех вхождений пустой Н₀, соединенных этими же тремя линиями. Кривая Н_i называется кривой Гильберта i-го порядка в честь ее первооткрывателя Д.Гильберта.

    Каждая  кривая Н_i состоит из четырех вдвое меньших Н_i-1 , то процедура для рисования Н_i будет включать четыре обращения для рисования Н_i-1, соответствующим образом повернутых и уменьшенных вдвое. Обозначим эти четыре части через А, В, С и D.

    Это кривые Гильберта 1-го порядка.

    Соединительные  прямые будем обозначать стрелками, указывающими в соответствующем  направлении. Будем предполагать, что  направление задается целым параметром i как i·45 градусов.

    Тогда получаем: при i=0, при i=2, при i=4, при i=6.

    Для построения A, B, С, D получается следующая  схема рекурсий:

    A: D A A B

    B: C B B A

    C: B C C D

    D: A D D C

    Кривые  Гильберта 2-го порядка.

    Для рисования линии будем использовать процедуру : 
Line( i, s: integer), где i - направление, s - длина отрезка.

    procedure Line( i, s: integer);

    BEGIN

          x:=i*45/180*pi;

          setlinestyle(0,0,1);

          LineRel(Round(s*cos(x)),Round(s*sin(x)));

    END;

    Используя эту процедуру, с помощью рекурсивных  обращений напишем процедуру, соответствующую  схеме А:

    Procedure A(i, s: integer);

    BEGIN

          if i>0 then

             begin

                   D(i-1,s);

                   Line(4,s);

                   A(i-1,s);

                   Line(6,s);

                   A(i-1,s);

                   Line(0,s);

                   B(i-1,s);

             end;

    END;

    Аналогично  составляются процедуры для В, С, D. Процедура А инициируется главной  программой по одному разу для каждой из кривых Гильберта. Главная программа  определяет начальную точку кривой, т.е. исходные координаты (x₀,y₀) и начальное значение длины отрезка u (желательно, чтобы u=2ⁿ).

    Эта программа рисует кривые Гильберта 5-го порядка.

    Uses Crt, Graph;

    Var

      x          :Real;

      GrD, GrM   :integer;

      i,x0,y0,u  :integer;

    procedure Line( i, s: integer);

    BEGIN

          x:=i*45/180*pi;

          setlinestyle(0,0,1);

          LineRel(Round(s*cos(x)),Round(s*sin(x)));

    END;

    Procedure B(i, s: integer);forward;

    Procedure C(i, s: integer);forward;

    Procedure D(i, s: integer);forward;

    Procedure A(i, s: integer);

    BEGIN

          if i>0 then

             begin

                   D(i-1,s);  Line(4,s);

                   A(i-1,s);  Line(6,s);

                   A(i-1,s);  Line(0,s);

                   B(i-1,s);

             end;

    END;

    Procedure B;

    BEGIN

          if i>0 then

             begin

                   C(i-1,s);  Line(2,s);

                   B(i-1,s);  Line(0,s);

                   B(i-1,s);  Line(6,s);

                   A(i-1,s);

              end;

    END;

    Procedure C;

    BEGIN

          if i>0 then

             begin

                   B(i-1,s);  Line(0,s);

                   C(i-1,s);  Line(2,s);

                   C(i-1,s);  Line(4,s);

                   D(i-1,s);

             end;

    END;

    Procedure D;

    BEGIN

          if i>0 then

             begin

                   A(i-1,s);  Line(6,s);

                   D(i-1,s);  Line(4,s);

                   D(i-1,s);  Line(2,s);

                   C(i-1,s);

             end;

    END;

    BEGIN  {Кривые Гильберта Н1...Н5}

          Grd := Detect;

          InitGraph(GrD,GrM, ' путь драйвера ');

          if GraphResult=GrOk

             then

                  begin

                        x0:=450; y0:=350; u:=128; i:=1;

                        while i<=5 do

                              begin

                                    MoveTo(x0,y0);

                                    A(i,u); i:=i+1; u:=u div 2;

                                    x0:=x0+(u div 2); y0:=y0+(u div 2);

                                    Readln;

                              end;

                        CloseGraph;

                  end;

    END.   

    КРИВЫЕ  СЕРПИНСКОГО

    Аналогично, путем наложения друг на друга  нескольких кривых, получается рисунок  из кривых Серпинского. Первые две из них С₁ и С₂ показаны ниже:

    Главное отличие кривой Серпинского от кривой Гильберта в том, что первая кривая замкнута. Значит, основная рекурсивная  схема должна давать разомкнутую кривую, четыре части которой соединяются линиями, не принадлежащими самому рекурсивному образу. Четыре составляющих образа обозначим через A, B, C, D.

    Соединительные  прямые будем обозначать стрелками, указывающими в соответствующем  направлении. Будем предполагать, что  направление задается целым параметром i как i·45 градусов. Кроме направлений, описанных в предыдущем примере, понадобятся ещT:

    Основной  образ кривых Серпинского задается схемой: 
S: A B C D

    Рекурсивные составляющие по схемам:

    A: A B D A

    B: B C A B

    C: C D B C

    D: D A C D

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

    procedure A(i,s: integer);

    BEGIN

       if i>0 then

          begin

                A(i-1,s); Line(7,s);

                B(i-1,s); Line(0,2*s);

                D(i-1,s); Line(1,s);

                A(i-1,s);

          end;

    END;

    Аналогично  получаются процедуры для B, C, D. Главная  программа строится по образу S. Ее задача - установить начальные значения для  координат рисунка и задать единичную  длину линий.  

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

    Приведем  пример простой программы TRIANGLS, строящей на экране компьютера изображение вписанных  друг в друга треугольников (рис. 24.1) и использующей для этого рекурсивный вызов функции.

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

    Начнем  с некоторого целого числа n, заданного  пользователем; этот аргумент устанавливается  равным n - 1 для каждого из трех рекурсивных  обращений. То есть при достижении «самого  глубокого уровня рекурсии», значение n становится равным нулю, что приводит к немедленному возврату в вызывающую функцию, то есть в саму функцию  tria.

    Графика и случайные числа

    Иногда  нам не нужна полная симметрия, возникающая  при прямом применении рекурсии. В  таких случаях можно использовать (псевдо-) случайные числа для  устранения в некоторой степени  такой симметрии. Этим способом с  помощью программы TTREE была получена картинка на рис. 24.2.

    Здесь показано многократное изображение  большой буквы T. Точку в нижней части буквы T назовем ее начальной  точкой. Начнем с большой буквы T в ее нормальном положении, а концевые точки на верхней горизонтальной полке будут в свою очередь  начальными точками новых букв T, несколько меньших, чем первоначальная. От пользователя программы запрашивается  ввод двух коэффициентов уменьшения (fx и fy), глубины рекурсии и порогового значения в процентах. После вычерчивания каждой буквы T генерируется случайное число, меньше 100. Если это число меньше, чем заданное пороговое значение, то новая буква T вычерчивается в нормальном положении, в противном случае — в перевернутом. В программе используется хорошо известная формула 1 + r + r² + ... + r^n-1 = (1 - rⁿ)/(1 - r) для вычисления размера первой буквы T, такого, чтобы окончательный результат разместился в пределах границ экрана.

    Кривые  Гильберта

    Рекурсия  может быть использована для получения  линейного рисунка, известного под  названием кривая Гильберта. Кривая Гильберта основана на изображении буквы П, вычерченной в виде трех сторон квадрата, как показано на рис. 24.3a. Существуют кривые Гильберта порядков 1, 2, ..., обозначаемые как H₁, H₂,... На рис. 24.3b изображена кривая порядка H₂, в которой некоторые отрезки прямых линий вычерчены в виде толстых линий. Это так называемые связки (в действительности связки должны иметь одинаковую толщину с другими отрезками, здесь же они показаны утолщенными единственно с целью демонстрации способа получения H₂ из H₁).

    Видно, что H₂ можно рассматривать как большую букву П, четыре части которой заменены меньшими по размеру буквами П. Эти меньшие буквы П соединены тремя связками. Каждая сторона меньшей буквы П имеет ту же длину, что и связка, они в три раза меньше стороны квадрата, в который вписывается H₂. Применим ту же процедуру к каждой из четырех букв П, составляющих H₂, то есть каждую букву П в H₂ заменим меньшей H₂, одновременно уменьшим длину связок так, чтобы их длины стали равными длине элементарного отрезка прямой линии, которые содержатся в трех малых фигурах H₂. Таким образом мы получим фигуру H₃, показанную на рис. 24.3с.

    Теперь  все элементарные отрезки в семь раз меньше, чем длина сторон квадрата, в который вписывается фигура H₃. Отсюда получаем, что коэффициенты уменьшения для этих элементарных отрезков в фигурах H₁, H₂, H₃, ... образуют ряд чисел: 1, 3, 7, ..., то есть в общем случае коэффициент уменьшения для фигуры H_n может быть вычислен по формуле: 2ⁿ - 1.

    Заметим, что связки в фигуре H₂ вычерчиваются в тех же направлениях, как и три отрезка, образующие букву П в фигуре H₁. При желании эти последние отрезки прямых линий можно рассматривать как связки, соединяющие четыре точки, которые в свою очередь можно принять за кривую Гильберта нулевого порядка.

    В нашей программе HILBERT для построения кривых Гильберта используется рекурсивная  функция hilbert со следующими аргументами: координаты точек A, B, C (см. рис. 24.4); горизонтальные и вертикальные компоненты двух направленных связок, причем одна лежит на отрезке AB, а другая — на AC. Они задаются в виде векторов, то есть как пара чисел (dx, dy), где переменные dx и dy могут принимать положительные, нулевые или отрицательные значения, в зависимости от относительного положения точек A, B и C. Эти два вектора в программе обозначаются как dAB и dAC; n — глубина рекурсии, для n = 0 функция ничего не будет делать.

    Будем считать, что рис. 24.4 является вариацией изображения буквы П (повернутой на угол 30^o против часовой стрелки), позиция которой целиком определяется тремя заданными точками A, B и C. Будем считать, что точка A является начальной точкой, а точка B — конечной. Основной причиной задания точки C является необходимость указания, с какой стороны от напраленного отрезка AB должна лежать вычерчиваемая кривая. Оба заданных вектора связок dAB и dAC отмечены на рисунке в виде связок в трех местах, а именно как отрезки DF, GH и IK. Три заданные точки A, B, C и два заданных вектора dAB и dAC позволяют определить позиции точек D, E, F, G, H, I, J, K на рисунке. (Мы не будем требовать, чтобы угол CAB был прямым углом или чтобы длина отрезка AB совпадала с длиной отрезка AC, поэтому вместо квадрата каждая буква П может иметь форму произвольного параллелограмма). В общем случае пунктирные линии, показанные на рис. 24.4, фактически не вычерчиваются. Вместо этого мы будем выполнять рекурсивное обращение к нашей функции hilbert для каждой из четырех точечных букв П на рисунке. Для вычерчивания на экране трех отрезков связок DF, GH и IK будем обращаться к нашей функции draw.

    На рис. 24.5 представлен результат работы программы.

    Фракталы

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

    С помощью программы SQFRACT можно получить такую картинку. Первые четыре аргумента  функции side программы представляют собой координаты концевых точек A и B отрезка прямой линии. Но этот отрезок будет вычерчен только в том случае, если аргумент n функции side будет равен нулю. В противном случае на этом отрезке будут сформированы две новые точки P и S. Они будут определять концевые точки стороны уменьшенного квадрата (при равенстве PS = f * AB), как показано на (рис. 24.7). Из рисунка очевидно, что координаты точки Q можно вычислить следующим образом: 
x_Q = x_P + (y_S - y_P) 
y_Q = y_P + (x_S - x_P).

    (Напомним, что аналогичный способ формирования  новой точки уже обсуждался  более подробно при рассмотрении  кривой Гильберта). Координаты точки  R определяются очень просто, поскольку  она находится в таком же  отношении к точке Q, как точка  S относится к точке P. Теперь  можно вычертить отрезок AP, выполнить  рекурсивное обращение к функции  side для сторон PQ, QR, RS меньшего квадрата и закончить вычерчиванием отрезка SB.

    Вместо  непосредственного вычерчивания отрезков AP и SB для них можно рекурсивно обратиться к функции side. Хотя в данном конкретном случае это и не дает удовлетворительного результата, но полезна сама идея. Она приводит к целому классу интересных новых кривых, состоящих из отрезков прямых линий, которые, в отличие от рис. 24.6, имеют почти одинаковую длину. (Напомним, что с подобной ситуацией мы встречались в случае кривых Гильберта).

    Рассмотрим  общую программу FRCURVE для генерации  таких кривых. Во-первых, базовая фигура может быть задана либо в виде горизонтального отрезка прямой линии, либо в виде правильного многоугольника. Во-вторых, вместо вычисления позиций новых точек P, Q, R, S («модельных точек») относительно позиций концевых точек A и B, как на рис. 24.7, пользователь в качестве входных данных может задать любое количество таких точек, не обязательно четыре. Введем локальную систему координат, в которой точка A совпадает с точкой начала (0, 0), а точка B — с точкой (1, 0). Тогда позиции модельных точек могут быть выражены в этих локальных координатах. Рассмотрим для примера рис. 24.8, где определены три новые точки с координатами (x, y): (0.45, 0), (0.50, 0.45) и (0.55, 0).

    Напомним, что обе концевые точки A(0, 0) и B(1, 0) неявно добавляются к модельным  точкам, которые мы должны ввести, поэтому  вообще число модельных точек  всегда на две точки больше, чем  заданное число. Если же всю фигуру целиком применять к каждой из ее четырех частей, то получим рис. 24.9 и так далее.

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

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

    0.25   0 
0.25   0.25 
0.5   0.25 
0.5   0 
0.5   -0.25 
0.75   -0.25 
0.75   0