|
Системы итерированных функций СИФАрхив проекта: 10_fractals.py Мы теперь знаем, что генерировать фракталы можно с помощью L-систем, которым была посвящена основная доля прошлых занятий. Но это не единственный подход. Существует другой распространенный метод формирования фрактальных кривых – системы итерированных функций (СИФ). Идея состоит в том, чтобы к некоторому начальному изображению (компактному множеству точек), например, черному квадрату, применить набор сжимающих отображений, которые бы переводили начальное множество точек в новое другое компактное множество точек:
На следующей
итерации повторяется это же преобразование, но уже для множества точек
И так далее. После n итераций у нас получится компакт:
соответствующий фракталу «ковер Серпинского»:
Это и есть принцип
построения фракталов с помощью системы итерированных функций. Здесь под
функциями понимаются как раз эти самые сжимающие отображения: Давайте
посмотрим, какие следует взять преобразования, чтобы сформировать ковер
Серпинского. Как видно из первого рисунка (где применяются преобразования к Предположим,
имеется точка
Новая точка с
координатами
Но гораздо лучше записать это преобразование в общем виде через матрицу:
И, кроме того, добавим сюда еще вектор смещения, который для формирования первого квадратика, равен нулю:
Вот мы с вами получили первое преобразование, которое на выходе даст множество точек для первого квадрата ковра Серпинского. Мало того, матрично-векторная запись позволит в будущем определять любые сжимающие преобразования на плоскости, задавая нужные коэффициенты в матрице и векторе смещения. Остальные два квадратика формируются аналогичным образом, только с разными смещениями:
Здесь в
последнем преобразовании смещение Все, пробегая
все точки исходного множества
И, далее, по рекурсии мы будем все ближе и ближе приближаться к фрактальному множеству – ковру Серпинского. Первая СИФ на PythonДавайте следующим шагом реализуем программу, которая бы делала такие преобразования. Для этого я воспользуюсь модулем Pygame языка Python, в котором удобно выполнять рисование и делать простую анимацию на плоскости. Вначале импортируем необходимые модули и определим две переменные: import pygame import numpy as np import os WHITE = (255, 255, 255) BLACK = (0, 0, 0) Затем, выполним стандартную инициализацию модуля Pygame (если вы раньше не работали с Pygame и не знакомы с его функционалом, то на этом канале есть занятия по этой теме): # ---------- чтобы окно появлялось в верхнем левом углу ------------ x = 20 y = 40 os.environ['SDL_VIDEO_WINDOW_POS'] = "%d,%d" % (x,y) # -------------------------------------------------------------------- pygame.init() W = 1200 H = 600 sc = pygame.display.set_mode((W, H)) pygame.display.set_caption("Система итерированных функций") sc.fill(WHITE) FPS = 30 # число кадров в секунду clock = pygame.time.Clock() И создаем главный цикл приложения: while True: for event in pygame.event.get(): if event.type == pygame.QUIT: exit() pygame.display.update() clock.tick(FPS) У нас все
готово, чтобы реализовать идею системы итерированных функций. Вначале нужно
подумать как представить компактное множество точек surf_e = pygame.Surface((200, 200)) surf_e.fill(BLACK) Это и будет начальное множество точек в виде черного квадрата. Но для лучшего визуального эффекта, я у этого квадрата нарисую белую рамку шириной в 60 пикселей: pygame.draw.rect(surf_e, WHITE, surf_e.get_rect(), 60) Вы сейчас поймете для чего она нужна. Далее, в программе нам нужно представить сжимающие преобразования. Из приведенных формул для операций на плоскости, каждое преобразование описывается шестью числами:
Именно в таком виде я их и запишу: C = [(0.5, 0, 0, 0.5, 0, 0), (0.5, 0, 0, 0.5, 0.5, 0), (0.5, 0, 0, 0.5, 0.25, 0.433), ] Теперь пришло время описать класс SIF для реализации итерационных преобразований над компактным множеством точек: class SIF: def __init__(self, coeffs): self.coeffs = coeffs Вначале мы ему передаем список коэффициентов для сжимающих отображений, а затем, с помощью метода create_funcs() преобразуем этот список в набор матриц и векторов, используя массивы пакета numpy: def create_funcs(self): T = [] for c in self.coeffs: t = np.array(c[:4]).reshape(2, 2) h = np.array(c[4:]) T.append((t, h)) return T (Если вы не знакомы с numpy, то на этом канале также есть занятия по этому пакету). Здесь мы делаем следующее. Из каждой строчки параметров первые четыре числа образуют матрицу 2х2, а остальные два – вектор смещения. Сохраняем эти данные в списке T и в конце возвращаем его. Все эти матрицы и векторы используются в методе create_attractor(): def create_attractor(self, surf_e, n_iter): size = surf_e.get_size() T = self.create_funcs() surf_res = pygame.Surface(size) surf_iter = pygame.Surface(size) surf_res.blit(surf_e, (0, 0)) size_np = np.array(size) for n in range(n_iter): surf_iter.fill(WHITE) for t in T: size_scale = np.int32(np.round(t[0] @ size_np)) offset = np.int32(np.round( t[1] * size_np)) s = pygame.transform.smoothscale(surf_res, size_scale) surf_iter.blit(s, offset) surf_res.blit(surf_iter, (0, 0)) return surf_res Вначале мы передаем ему компактное множество в виде поверхности и указываем число итераций. Затем, формируем две вспомогательные поверхности: surf_res – для хранения результирующего преобразования; surf_iter – для рисования точек на текущей итерации. Соответственно, начальное множество – это точки поверхности surf_e, поэтому мы их переносим на поверхность surf_res. Далее, нам нужно будет масштабировать (сжимать) множество точек поверхности. Для этого я воспользовался методом smoothscale(), где вторым параметром нужно указывать новые размеры фигуры (компактного множества). Чтобы вычислить эти размеры, я создал массив numpy из исходных размеров компактного множества: size_np = np.array(size) Зачем это сделано? Смотрите, если применить матрицу сжимающего отображения к этому вектору:
то на выходе, как раз, получим эти уменьшенные размеры компактного множества. А само сжатие для всех точек сделает уже функция smoothscale(). Вот так здесь это реализовано. Аналогичным образом определяем смещение образа в пикселах, путем поэлементного умножения векторов:
И формируем изображение этого множества на поверхности surf_iter. После того, как все преобразования будут выполнены, результат из surf_iter копируется на surf_res. И так на каждой итерации. В конце функция create_attractor() возвращает сформированное изображение на плоскости surf_res. Давайте посмотрим, как все это будет работать. Создадим экземпляр класса SIF, передадим ему список коэффициентов сжимающих отображений и вызовем метод create_attractor() с одной итерацией: sif = SIF(C) surf_res = sif.create_attractor(surf_e, 1) surf_res = pygame.transform.flip(surf_res, False, True) Затем, зеркально отображаем поверхность по вертикали, чтобы видеть результат в привычном нам виде. А в главном цикле добавим строчку: sc.blit(surf_res, (100, 200)) На выходе у нас сформируются три вот таких квадрата:
Они четко отделены друг от друга благодаря белой границе, которую мы нарисовали вначале в 60 пикселей. Давайте теперь сделаем так, чтобы результат показывался итерационно в виде анимации и мы наглядно видели как происходит построение аттрактора «ковер Серпинского». Для этого в главном цикле пропишем следующие строчки: n_iter = 1 step = 0 while True: for event in pygame.event.get(): if event.type == pygame.QUIT: exit() step += 1 if step > 30 and n_iter < 8: step = 0 surf_res = sif.create_attractor(surf_e, n_iter) surf_res = pygame.transform.flip(surf_res, False, True) sc.blit(surf_res, (100, 200)) n_iter += 1 pygame.display.update() А вместо первой итерации, перед циклом, укажем сформировать начальное множество точек: surf_res = sif.create_attractor(surf_e, 0) surf_res = pygame.transform.flip(surf_res, False, True) После запуска увидим постепенное построение фрактала ковра Серпинского. Следует отметить, что в нашей реализации СИФ можно использовать только сжимающие отображения без возможности поворота поверхностей. Но, так как это учебный пример, то я не стану усложнять программу, тем более, что на следующем занятии мы рассмотрим другой итеративный подход формирования фрактальных изображений с помощью СИФ, используя только координаты точек. Видео по теме |
:
.
),
исходное множество точек сжимается в два раза по каждой пространственной оси.
множества
,
очевидно, может быть получена по формуле:
взято,
чтобы образовывался равносторонний треугольник из квадратиков.
