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

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

Задача 1. Составить рекурсивный алгоритм рисования окружностей, аналогичный представленному на рис. 8.1.

Рис. 8.1. Рисунок из окружностей

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

Решение:

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

На рис. 8.2 приведен пример кривых Гильберта.

Рис. 8.2. Кривые Гильберта

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

Рис. 8.3. Наложенные кривые

Н_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 - длина отрезка.

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

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

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

8.2.2. Кривые Серпинского

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

C1

C2

Рис. 8.4. Кривые Серпинского

Главное отличие кривой Серпинского от кривой Гильберта в том, что первая кривая замкнута. Значит, основная рекурсивная схема должна давать разомкнутую кривую, четыре части которой соединяются линиями, не принадлежащими самому рекурсивному образу. Четыре составляющих образа обозначим через 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

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

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: