Лабораторная работа №4 / LAB_4

Санкт-Петербургский государственный электротехнический университет

Кафедра МОЭВМ

Отчет по лабораторной работе №4.

Фрактал и фрактальная геометрия

Выполнил:

Студент гр.3351

Сергеев М.В.

Проверил:

Герасимова Т.В.

Санкт-Петербург

2007г.

1. Задание

Кривая Гильберта. Основана на изображении буквы П, вычерченной в виде трех сторон квадрата. Существуют кривые Гильберта порядков 1,2, 3,.., обозначаемые как Н1, Н2, Н3

Н1 Н2 Н3

2. Выполнение работы

Кривая Гильберта первого порядка, обозначаемая H1, похожа на изображение буквы П, вычерченной в виде трех сторон квадрата, как показано на рис. 3а. На рис. 3б изображена кривая Гильберта второго порядка H2. Видно, что кривая H2 состоит из кривых H1, ориентированных в разные стороны (вправо, вверх и влево). Кривые H1, составляющие кривую H2, соединены тремя отрезками прямых, называемых связками (на рис. 3б они вычерчены утолщенными линиями). В действительности эти отрезки должны иметь одинаковую толщину с другими линиями, утолщенными они показаны единственно с целью демонстрации способа получения H2 из Н1.

Рис. 3. Кривые Гильберта первого, второго и третьего порядков

Аналогично фигуру H3 (рис. 3в) можно рассматривать как состоящую из четырех кривых H2 (ориентированных в разные стороны) и трех связок.

Заметим, что отрезки, образующие линию H1, можно рассматривать как связки, соединяющие 4 точки — кривые Гильберта нулевых порядков.

Таким образом, кривую Гильберта i-го порядка Hi можно получить из четырех кривых Hi–1, ориентированных в разные стороны, и трех связок. Если процедуры рисования кривых Hi, ориентированных вверх, вниз, влево и вправо, обозначить соответственно GU(i), GD(i), GL(i) и GR(i), то можно составить следующие рекурсивные схемы построения этих кривых:

GU(i): GR(i—1) GU(i—1) GU(i—1) GL(i—1)

GR(i): GU(i—1) GR(i—1) GR(i—1) GD(i—1)

GD(i): GL(i—1) GD(i—1)¬ GD(i—1) GR(i—1)

GL(i): GD(i—1) GL(i—1) GL(i—1) GU(i—1)

Обозначим через h длину элементарного отрезка прямых в кривых H_i. Тогда, например, процедура GU в программе на школьном алгоритмическом языке [3, 4] может быть оформлена следующим образом:

алг GU(арг цел i)   нач    если i>0    то     GR(i-1)     LineUp    GU(i-1)     LineRight     GU(i-1)     LineDown     GL(i-1)   все кон

Здесь LineUp, LineRight, LineLeft, LineDown — процедуры рисования связок, направленных соответственно вверх, вправо, влево и вниз (напомним, что ось Y на экране направлена сверху вниз).

алг LineUp   нач     | вектор(0, -d) кон

алг LineRight   нач   | вектор(d, 0)   кон

алг LineLeft нач    вектор(-h, 0) кон

алг LineDown   нач    | вектор(0, d) кон

Аналогично можно оформить процедуры рисования кривых Гильберта, ориентированных вниз, влево и вправо:

алг GD(арг цел i)   нач     если i>0      то        GL(i-1)       LineDown       GD(i-1)       LineLeft      GD(i-1)       LineUp       GR(i-1)    все кон

алг GL(арг цел i)   нач    если i>0     то       GD(i-1)      LineLeft      GL(i-1)      LineDown     GL(i-1)      LineRight     GU(i-1)   все кон

алг GR(арг цел i)   нач     если i>0      то        GU(i-1)       LineRight      GR(i-1)       LineUp       GR(i-1)       LineLeft       GD(i-1)      все   кон

Обратим внимание на то, что в приведенных процедурах рисования кривых Гильберта используется так называемая косвенная рекурсия — ситуация, когда процедура вызывает себе как вспомогательную не только непосредственно, а также и через другую процедуру [1].

Квадрат, в который вписывается кривая Гильберта, будем называть опорным, длину его стороны (в пикселях) обозначим через S. Обсудим теперь вопрос определения значения величины h в зависимости от порядка кривой n. Из рис. 3 видно, что при n=2 длина элементарного отрезка линии в три раза меньше стороны опорного квадрата, при n=3 — в семь раз. Отсюда получаем, что коэффициенты уменьшения для этих элементарных отрезков в фигурах H₁, H₂ , H₃, ... образуют ряд чисел 1, 3, 7, ..., то есть в общем случае коэффициент уменьшения для фигуры H_n может быть вычислен по формуле 2n—1.

3