Научная библиотека

4.3. СИФ со сгущением

Будем по-прежнему понимать под пространство всех непустых компактных подмножеств оснащенное метрикой Хаусдорфа. Сгущающим преобразованием, или просто сгущением, называется отображение :

где С — произвольное подмножество которое мы будем называть множеством сгущения. Другими словами, задает тривиальное отображение на

Сгущение на К, есть не что иное, как сжатие с нулевым коэффициентом, так как для любых А, В Е К, имеет место:

Пусть в нашем распоряжении имеется СИФ, заданная сжимающими отображениями . Добавим к ним сгущение . Полученную систему итерированных функций будем называть системой итерированных функций со сгущением (ССИФ). Очевидно, основная теорема п. 4.1 остается в силе для ССИФ, то есть существует и притом единственное множество , такое, что вне зависимости от выбора начального множества , выполняется:

где

Тем самым мы уже почти доказали основную теорему о ССИФ.

Теорема 4.3.3. Пусть ССИФ задана сжимающими отображениями , где — сгущение:

Пусть

а также

Положим

Тогда

и

— аттрактор ССИФ.

Доказательство. Для доказательства первого утверждения мы воспользуемся следующим соотношением (см. упр. 5 в конце этого параграфа):

Имеем:

Второе утверждение, следует из теоремы 4.1.2, в шторой надо положить

Пример ССИФ представлен на рис. 4.10. Здесь множество сгущения С — фрактал, а именно фигура «сорняка», полученная с помощью L-системы. Данная ССИФ задается единственным сжимающим отображением, помимо тривиального:

Для вывода на экран можно использовать программу ТЕРТЛ-ГРАФИКА, предусмотрев возможность изменения масштаба и положения изображения каждый раз, когда встречается кодовое слово для фигуры «сорняк». Само кодовое слово есть результат работы алгоритма 2.2.1 (-системы) после двух итераций, инициализированного следующим образом:

То есть кодовое слово задается выражением:

Продолжая в том же ключе, мы можем пойти дальше и использовать все множество ССИФ, показанное на рис. 4.10, в качестве множества сгущения для новой ССИФ. Добавим к тривиальному отображению сжимающее отображение, которое все уменьшает и сдвигает вправо и вверх, например такое:

Результат показан на рис. 4.11. Полученное изображение можно рассматривать как дважды итерированную ССИФ, подобно двойному интегралу в математическом анализе.

Эта дважды итерированная ССИФ, очевидно, не эквивалентна ССИФ с тремя сжимающими отображениями и Результат одновременного применения всех трех отображений гораздо сложнее, как видно из рис. 4.12. Усложнение здесь происходит по той причине, что появляются всевозможные смешанные произведения а так как отображения не коммутируют (то есть ), то смешанные члены разного порядка дают разный результат.

С помощью алгоритма ССИФ можно строить огромное количество разнообразнейших фрактальных конфигураций. Фигура «дерево» представляет собой удачный с точки зрения эстетического восприятия пример такого построения. Здесь множество сгущения С (рис. 4.13) играет роль ствола дерева с двумя главными ветвями.

Мы выбрали аффинные преобразования таким образом, чтобы они уменьшали (и искажали) множество С, поворачивали его, а затем сдвигали получившийся элемент к концу одной из ветвей. На каждой итерации все ветви выпускают новые ветки, очень похожие на оригинал С, за исключением размера и ориентации (рис. 4.14).

Для компьютерной реализации описанного алгоритма применяется рекурсия. Главная программа ДЕРЕВО (которую мы не приводим) инициализирует графический режим, определяет и выводит на экран множество сгущения С и вызывает рекурсивную подпрограмму ВЕТВЬ (алгоритм 4.3.3). В этой подпрограмме на каждом уровне рекурсии вычисляются новые вершины, которые соединяются отрезками с вершинами предыдущего уровня.

Множество С хранится в виде массива вершин:

Добавление ветвей осуществляют следующие четыре аффинных преобразования (рис. 4.13):

В следующем алгоритме команда «построить V» (или «построить V1» и т. п.) означает такую последовательность действий:

Рис. 4.10. ССИФ

Рис. 4.11. Итерирование предыдущей фигуры с помощью

Рис. 4.12. Та же ССИФ, с использованием

Рис. 4.13. Множество сгущения С и первая итерация

Рис. 4.14. Дерево, построенное с помощью ССИФ Алгоритм 4.3.3. (ВЕТВЬ)

Назначение: рекурсивная часть кода ССИФ для фигуры «дерево»

Вход:

Выход:

изображение фигуры «дерево».

Шаги:

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