Kranover R M - Fraktaly i khaos v din sist
.pdf2.% L-системы
Рис. 2.15. Сорняк после 4-х итераций |
|
|
используется стек |
|
|
" х\ |
ух |
ах |
Х2 |
У2 |
«2 |
Хп |
Уп |
"п |
причем новые данные записываются в конец стека. Когда ветвь закрывается, переменным (х, у, а) присваиваются значения,считанные из конца стека. Затем эти значения из стека удаляются.
Таким образом, ветвление задается двумя символами:
[ |
Открыть ветвь. Сохранить (ж,у, а) в конце стека. |
] |
Закрыть ветвь. Присвоить переменным (х, у, а) значения, |
|
считанные из конца стека, после чего удалить их из стека. |
На рис. 2.15 и 2.16 изображены фракталы, построенные с помощью операции ветвления.
Ниже приведен алгоритм, который позволяет получать графическое представление слова при помощи тертл-графики.
32 • Глава 2 / Классические фракталы
Алгоритм 2.2.2. (ТЕРТЛ-ГРАФИКА)
Назначение: реализует тертл-графику для кодового слова, состоящего из букв F, Ь, [, ], + и —.
Вход:
word (результат работы L-системы) в (приращение по углу)
а (начальное направление)
Выход:
Графическое представление word.
Инициализация:
графический режим (подробнее см. ниже)
W = word
п = \ength(word)
stack = { } (пустое множество)
Шаги:
for j = 1 to п
if W{j) |
= +, о = a + в, end if |
if W(j) |
— -, a = a — 9, end if |
if W(j) |
= F, x = x0 + cos(o;), у = yo + sin(a), |
провести линию из точки (хо,уо) в точку (х, у), х0 = х, Уо = У
end if
if W(j) = 6, XQ= XQ + cos(a), j/o = Уо+ sin(a), end if
/ = length(stack), stack (I + 1,1) = XQ stack (I + 1,2)= yo stack (I + 1,3) = a
end if
if W(j) = ],
I = length(stack), XQ= stack (/, 1) 2/o = stack (1,2)
a — stack (/,3)
2.2 L-системы • 33
Рис. 2.16. Куст после 4-х итераций
удалить 1-ую запись из stack end if
end for
Можно написать специальную программу для определения размеров графического окна. Для этого достаточно выполнить в точности те же шаги, что и в алгоритме 2.2.2, но вместо вывода на экран надо отслеживать наименьшее и наибольшее значения х и у. Вначале положим эти значения равными нулю:
хтгп —хтах = О,
ymin = углах = 0.
Каждый раз, когда появляется новая точка (ж,у), размеры окна обновляюся:
хтгп = iain(x,xmin),
хтах = та.х(х, хтах),
34 • Глава2 / Классические фракталы
Рис. 2.17. Снежинка после 3-х итераций (Джонг By Ким)
ymin — min(?/, ymin), утах = max.(y,ymax).
Значения xmin, xmax, ymin и утах, полученные по окончании работы алгоритма, используются для инициализации окна вывода тертл-графики.
Порождающие правила для L-систем. Порождающие правила для L-систем перечислены в алфавитном порядке.
Дракон Хартера-Хайтвея (рис. 2.14): axiom = FX
newf = F
newx = X+YF+ newy = —FX—Y
2.2 L-системы " 35
Рис. 2.18. Цветок после 3-х итераций (Брандон Нельсон)
Ковер Серпинского (рис. 2.4): axiom = F X F — F F — F F newf = FF
newx = — FXF++FXF++FXF —
Кривая Гильберта, заполняющая плоскость (рис. 2.24): axiom = X
newf = F
newx = -YF+XFX+FY- newy = +XF-YFY-FX+
Кривая Госпера, заполняющая плоскость (рис. 2.26): axiom = XF
newf = F
newx = X+YF++YF-FX—FXFX-YF+
36 • Глава 2 / Классические фракталы
newy = -FX+YFYF++YF+FX—FX-Y 0 = тг/3
Кривая Пеано, заполняющая плоскость (рис. 2.22, 2.23): axiom = F
newf = F - F + F + F + F - F - F - F + F
Q = 7г/4
9 = IT/2
Кривая Серпинского, заполняющая плоскость (рис. 2.25): axiom = F+XF+F+XF
newf = F
newx = XF-F+F-XF+F+XF-F+F-X a = тг/4
0 = тг/2
Куст (рис. 2.16): axiom = F
newf = - F+F+[+F - F - ] - [ - F+F+F] 6> = 7г/8
Мозаика (рис. 2.11): axiom = F - F - F - F
newf = F-b+FF-F-FF-Fb-FF+b-FF+F+FF+Fb+FFF newb = bbbbbb
Остров (рис. 2.10): axiom = F+F+F+F
newf = F + F - F - F F F + F + F - F 6> = 7г/2
Снежинка (рис. 2.17):
axiom = [F]+[F]+[F]+[F]+[F]+[F] newf = F[++F][-FF]FF[+F][-F]FF (9= 7г/3
Снежинка Коха (рис.2.2): axiom = F++F++F newf = F - F + + F - F
0 = 7r/2
Сорняк (рис. 2.15): axiom = F
2.2 L-системы |
37 |
Рис. 2.19. Порождающее правило к упр. 2
newf = F[+F]F[-F]F 0 = тг/7
Цветок (рис. 2.18):
axiom = F[+F+F][-F-F][++F][—F]F newf = FF[++F][+F][F][-F][—F]
a = ?r/2 в = 7г/1б
Цепочка (рис. 2.12): axiom = F+F+F+F
newf = F+b - F - FFF+F+b - F newb = bbb
0 = тг/2
Упражнения 2.2.
1.а) Чему равно слово на выходе следующей L-системы после двух итераций:
axiom = F (слово инициализации) newf =FF-[F]+[F]
а = тг/2 (начальное направление)
б) Изобразить найденное в предыдущем пункте слово графически.
38 • Глава 2 / Классические фракталы
2. Написать псевдокод для L-систем (с использованием «newf»
ит. п.), реализующих правила нарис. 2.19.Положить axiom = F.
3.Построить L-системы дляфракталов изупр. 1,п.2.1. Отобразить результат работы L-системы в графике.
4.Придумать и реализовать на компьютере три новые L-системы, результатом работы которых были бываши собственные варианты следующих фигур:
а) снежинка или остров (с границей безразрывов); б) мозаика или острова (с разрывной границей); в) куст или сорняк.
5.(Компьютерный эксперимент.) Исследовать с точки зренияфрактальных свойств один из множества представленных в [39] объектов. Возможные темы:
а) растения с перекрестным опылением (соцветия); б) мозаика; в) восточный орнамент;
г) фрактальная музыка.
2.3.Пыль Кантора
Классическое множество Кантора,или пыль Кантора,названо по имени Георга Кантора, который описал его в 1883 году. Существование пыли Кантора отмечалось до этого Генри Смитом (Henry Smith) в 1875 году илиещеранее. Этомножество хорошо известно студентам изкурса математического анализа как пример множества нулевой меры Лебега [41], чья мощность равна мощности континуума [0,1]. Фрактальные свойства пыли Кантора имеют огромное значение, особенно учитывая тот факт, что многие известные фракталы являются близкими родственниками этого множества.
Построение классической пыли Кантора начинается с выбрасывания средней трети (не включая концы) единичного отрезка. То есть исходное множество есть отрезок [0,1], и первый шаг состоит в удалении открытого интервала (1/3,2/3). На следующем и всех остальных шагах мы выкидываем среднюю треть (невключая концы) всех отрезков текущего уровня. Таким образом, мы получаем (рис. 2.20) последовательность множеств:
2.3 Пыль Кантора • 39
Рис. 2.20. Построение пыли Кантора
Со |
= |
[0,1] |
d |
= |
[0,1/3] U[2/3,1] |
С2 |
= |
[0,1/9] U[2/9,1/3] U[2/3,7/9] U[8/9,1] |
Предельное множество С, которое представляет собой пересечение множеств Сп, п = 0,1,2,..., называется классической пылью Кантора. В дальнейшем мы будем называть его просто канторовой пылью.
Свойства канторовой пыли.
1. Канторова пыль есть самоподобный фрактал размерности
d = log(2)/log(3) « 0,6309,
так как соотношение Nrd = 1 выполняется при N — 2 и г = 1/3.
2.Канторова пыль не содержит интервалов положительной длины. Это очевидно из построения.
3.Сумма длин интервалов, удаленных при построении множества С, в точности равна 1. Чтобы показать это, рассмотрим следующее доказательство. Длина первого интервала, который мы выкинули,
40 • Глава 2 / Классические фракталы
составляет 1/3. Чтобы получить Сг, мы выкинули два интервала, каждый длиной 1/32. На следующем шаге мы выбросили 22 интервалов, каждый длиной 1/33, и т. д. Таким образом, сумма длин удаленных интервалов 5 составляет:
5 = 1/3 + 2/32 + 22/33 + • • • 4- 2п~1/Зп + • • •.
Но это выражение можно переписать в виде:
5 = (1/3)(1 + 2/3 + (2/3)2 + (2/3)3 + •••),
и с помощью формулы для суммы геометрической прогрессии, а именно,
1-х |
1 + + 2 |
+ 3 |
| | 1 |
|
|
|
мы получаем:
Можно предположить, что если в С что-нибудь и осталось после удаления всех этих интервалов, то, наверное, не очень много. Однако это не так, что подтверждается следующим свойством.
4. Удивительный результат сравнения множества Кантора с интервалом состоит в том, что мощности этих множеств равны. Два множества обладают равной мощностью, если существует взаимно однозначное соответствие между точками этих множеств. В случае конечных множеств данное утверждение тривиально. Для бесконечных множеств, таких как интервал или множество Кантора, понятие мощности требует аккуратного обращения. В качестве простой иллюстрации сказанного достаточно заметить, что отрезки [0,1] и [0,2]
— равной мощности, несмотря на то, что второй интервал в два раза длиннее первого. Взаимно однозначное соответствие в этом случае задается отображением /(х) = 2х, где х € [0,1].
Прежде чем приступить к доказательству основной теоремы о мощности множества Кантора, вспомним, как представить точку х отрезка [0,1] в системе счисления с основанием N, N > 2. Разобьем отрезок [0,1] на N равных интервалов, каждый длины 1/N. Пронумеруем эти интервалы следующим образом: 0,1,2,..., N — 1. Если оказалось, что точка х принадлежит интервалу с номером 5, то положим xi = 5. Затем разобьем этот интервал на N новых интервалов, каждый длины 1/iV2. Пронумеруем эти интервалы, как и раньше: