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

D этой теме рассматривается применение рекурсии в графике. Приводятся примеры построения кривых Гильберта и Серпинского.

 

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

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




Центральная окружность радиуса 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.

 


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


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

Нi+1 получается соединением четырех экземпляров Нi вдвое меньшего размера, повернутых соответствующим образом и "стянутых" вместе тремя прямыми линиями. Н1 можно считать состоящей из четырех вхождений пустой Н0, соединенных этими же тремя линиями. Кривая Н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. Процедура А инициируется главной программой по одному разу для каждой из кривых Гильберта. Главная программа определяет начальную точку кривой, т.е. исходные координаты (x0,y0) и начальное значение длины отрезка u (желательно, чтобы u=2n).

Эта программа рисует кривые Гильберта 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.

 


КРИВЫЕ СЕРПИНСКОГО
Аналогично, путем наложения друг на друга нескольких кривых, получается рисунок из кривых Серпинского. Первые две из них С1 и С2 показаны ниже:




C1

C2

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

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

Основной образ кривых Серпинского задается схемой:
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. Ее задача - установить начальные значения для координат рисунка и задать единичную длину линий.

 

  •  
    •  
      •  

      • 1. Составить рекурсивный алгоритм рисования кривых Серпинского 4-го порядка.
        2. Составить рекурсивный алгоритм рисования окружностей следующего вида:3. Составить рекурсивный алгоритм рисования "дерева" следующего вида:
    • Упражнения:

 


1-го порядка

2-го порядка

Другие записи

10.06.2016. РАЗМЕЩЕНИЯ. ПЕРЕСТАНОВКИ. СОЧЕТАНИЯ
В этой теме рассматриваются элементы комбинаторики и алгоритмы решения комбинаторных задач. Имеется n различных предметов. Сколько из них можно составить k-расстановок? При этом две расстановки считаются…
10.06.2016. ОБХОД ДЕРЕВА. ПЕРЕБОР С ВОЗВРАТАМИ
    1. Приведенная программа тратит довольно много времени на выполнение проверки есть_сверху (проверка, находится ли верхний ферзь под боем, требует числа действий порядка n). Изменить реализацию…
10.06.2016. СОРТИРОВКИ
 В данной теме мы рассмотрим некоторые методы сортировки массивов порядка n2. Проведет анализ производительности алгоритмов. Покажем, как путем улучшений алгоритма можно добиться некоторого выигрыша…
10.06.2016. УЛУЧШЕННЫЕ МЕТОДЫ СОРТИРОВКИ
  В этой теме продолжаем изучать методы сортировок массивов, которые получены усовершенствованием простых методов.       1. Дан массив целых чисел a[1..n]. Отсортировать его методом…
10.06.2016. РЕКУРСИЯ
В этой теме рассматривается понятие "рекурсия" и ее применение к решению задач. Приводятся решения задач из предыдущих тем с использованием рекурсии.   Рекурсивным называется объект, частично состоящий…