Рассмотрим кривую Леви. На рис. 4.5 показаны первые фазы ее построения. Фактически приближение фрактала определяется своими вершинами. Поэтому то, что нам нужно сделать, это на каждом шаге найти вершины (и соединить их прямыми линиями). На рис. 4.5 можно обнаружить два поворота-сжатия. Первое преобразование, $L$, имеет центр в точке $O, \pi / 4$ – угол вращения и $1 / \sqrt{2}$ – показатель уменьшения.
Рис. 4.5. Подобные преобразования во фрактале Леви
Второе преобразование, $R$, имеет центр в точке $(1,0)$, угол вращения $-\pi / 4$ и показатель сжатия $1 / \sqrt{2}$. Как $L$, так и $R$ преобразуют вершины в другие вершины так, что фрактал Леви является инвариантным множеством относительно $L, R$ и их комбинаций.
\[
L:\left\{\begin{array}{l}
x^{\prime}=(x-y) / 2 \\
y^{\prime}=(x+y) / 2
\end{array} \quad R:\left\{\begin{array}{c}
x^{\prime}=(x+y+1) / 2 \\
y^{\prime}=(-x+y+1) / 2
\end{array}\right.\right.
\]

Из (4.13) следует: $\Delta=1 / 2<1, \cos \alpha=\sqrt{2} / 2$.
Точки фрактала Леви на каждом шаге (фазе) $p$ можно получать, например, подвергая правую точку $(1,0)$ последовательности комбинаций преобразований $L$ и $R$. Здесь можно использовать двоичную систему счисления, интерпретируя $L$ как двоичную цифру 1 , а $R$ – как 0 . Таким образом, фрактал состоит из такого же числа точек, сколько чисел между 0 и 1 в двоичной системе, а их бесконечное множество.

Если мы выберем произвольную точку $P$ в качестве начальной и подвергнем ее преобразованиям $L$ и $R$ несколько раз, то число точек на каждом шаге будет удваиваться. Мы можем изобразить этот процесс в виде дерева с числовыми индексами (рис. 4.6). Например, точка с номером 18 получится в результате преобразования $L R L L(P)$.
Рис. 4.6. Нумерация двоичного дерева
Если точка $P$ является точкой фрактала, то и все ее итерации, которые получаются из нее, также будут точками фрактала. Это один из способов написания программы для построения вершин фрактала. Этот метод быстрый и эффективный, но требует много машинной памяти.

Есть другой способ, который требует значительно меньше памяти компьютера. Он называется методом «обратного следа» [3] и включен в программу «Fractals». Для этого необходимо по-другому перенумеровать дерево (рис. 4.7).

Рис. 4.7. Нумерация с использованием метода «обратного следа»

С помощью этого метода перенумерации мы приходим к самым маленьким ветвям и затем возвращаемся.

Приведем пример программы на языке Basic [3] (с небольшой модернизацией) построения фракталов, для которых $L$ и $R$ имеют вид:
\[
L:\left\{\begin{array}{l}
x^{\prime}=a x-b y \\
y^{\prime}=b x+a y,
\end{array} \quad R:\left\{\begin{array}{l}
x^{\prime}=c x-d y+1-c \\
y^{\prime}=d x+c y-d
\end{array}\right.\right.
\]

Итак, $L$ – это поворот-сжатие относительно точки $(0,0)$ с показателем сжатия $\sqrt{a^{2}+b^{2}}$, а $R$ – поворот-сжатие относительно точки $(1,0)$ с показателем сжатия $\sqrt{c^{2}+d^{2}}$.

Программа использует метод обратного следа, и читатель сможет ее понять, используя рис. 4.7 и полагая $p=4$.
REM Программа построения конструктивных фракталов
SCREEN 12: CLS
WINDOW $(-1.1,-1)-(2.1,1.4)$
INPUT \”Введите число уровней $\mathrm{P}$ \”; $\mathrm{P}$
DIM $\mathrm{X} 1(\mathrm{P}), \mathrm{Y} 1(\mathrm{P}), \mathrm{X} 2(\mathrm{P}), \mathrm{Y} 2(\mathrm{P})$
INPUT \”Введите параметры преобразования $\mathrm{a}, \mathrm{b}, \mathrm{c}, \mathrm{d}$ \”; $\mathrm{a}, \mathrm{b}, \mathrm{c}, \mathrm{d}$
\[
\begin{array}{l}
\mathrm{X} 1(0)=\mathrm{a}: \mathrm{Y} 1(0)=\mathrm{b} \\
\operatorname{PSET}(0,0): \operatorname{PSET}(1,0): \operatorname{PSET}(\mathrm{a}, \mathrm{b}) \\
\mathrm{S}=1: \operatorname{GOSUB} 140 \\
\text { FOR } \mathrm{m}=1 \mathrm{TO} 2^{\wedge}(\mathrm{P}-1)-1 \\
\mathrm{~S}=\mathrm{P}: \mathrm{n}=\mathrm{m} \\
\mathrm{IF} \mathrm{n} \bmod 2=0 \mathrm{THEN} \mathrm{n}=\mathrm{INT}(\mathrm{n} / 2) \\
\mathrm{S}=\mathrm{S}-1: \text { GOTO } 110:
\end{array}
\]

REM четные $\mathrm{m}$ пропускаем, метод обратного следа
\[
\text { GOSUB } 140
\]

NEXT m
BEEP
120 a $\$=$ INKEY\$: IF a\$ = \”‘\” THEN 120
END
\[
140 \mathrm{X} 1(\mathrm{~S}-1)=\mathrm{X} 2(\mathrm{~S}-1): \mathrm{Y} 1(\mathrm{~S}-1)=\mathrm{Y} 2(\mathrm{~S}-1)
\]

FOR $\mathrm{J}=\mathrm{S}$ TO $\mathrm{P}$
$\mathrm{X}=\mathrm{X} 1(\mathrm{~J}-1): \mathrm{Y}=\mathrm{Y} 1(\mathrm{~J}-1)$
$\mathrm{X} 1(\mathrm{~J})=\mathrm{a} * \mathrm{X}-\mathrm{b} * \mathrm{Y}: \mathrm{Y} 1(\mathrm{~J})=\mathrm{b} * \mathrm{X}+\mathrm{a} * \mathrm{Y}$
$X 2(J)=C * X-d * Y+1-c: Y 2(J)=d * X+C * Y-d$
$\operatorname{PSET}(\mathrm{X} 1(\mathrm{~J}), \mathrm{Y} 1(\mathrm{~J})$ )
$\operatorname{PSET}(\mathrm{X} 2(\mathrm{~J}), \mathrm{Y} 2(\mathrm{~J}))$

NEXT J
RETURN
END

Примеры:
1) Положив $a=d=0, b=c=0.7, p=17$, получим рис. 4.8. Здесь $L-$ четверть оборота с показателем уменьшения 0.7 и $R$ – обычное центральное сжатие с показателем сжатия 0.7 относительно $(1,0)$.
2) Положив $a=b=0.6, c=0.53, d=0, p=18$, получим рис. 4.9. Здесь $L$ и $R$ имеют такой же тип, как и в примере 1. Угол вращения для $L$ равен $\pi / 4$. Результат напоминает ветвь с листьями.
3) Выбрав $a=0, b=1 / \sqrt{2}, c=1 / 2, d=-1 / 2$, получаем рис. 4.10 ( $p=17$ ). Здесь $L$ и $R$ являются поворотами с одинаковым сжатием $1 / \sqrt{2}$. Углы вращения $\pi / 2$ и $-\pi / 4$ соответственно.
Рис. 4.8. Фрактал, полученный с помощью «поворота-сжатия»

Рис. 4.9. Фрактал, полученный с помощью «поворота-сжатия»

Рис. 4.10. Фрактал, полученный с помощью двойного «поворотасжатия»