Мир фракталов

Матрица статей Список статей Всячина Контакты

Системы итерируемых функций со сгущением

Пусть $H = (H(\mathbb{R}^n), h)$ — пространство непустых компактов, оснащённое метрикой Хаусдорфа. Сгущающим преобразованием, или просто сгущением назовём отображение $T_C: H \to H$ такое, что $T_C(E) = C$ , для всех $E \in H$ , где $C \in H$ — множество сгущения.

Сгущение $T_C$ есть не что иное, как сжатие с нулевым показателем сжатия, так как $h(T_C(A), T_C(B)) = h(C, C) = 0$ .

Пусть $\{T_i\}_i$ — система итерируемых функций, заданная набором сжимающих отображений. Тогда $\{T_i\}_i \cup T_C$ назовём системой итерируемых функций со сгущением.

Имеет место следующая теорема.

Теорема. Пусть $T(A) = \bigcup_i T_i(A)$ , $T_{*}(A) = T_C(A) \cup T(A)$ , $A \in H$ , $C_n = T_{*}^n(C)$ . Тогда $C_n = \bigcup_n T^n(C)$ и $E = \lim_{n \to \infty} C_n$ — аттрактор системы итерируемых функций со сгущением.

Далее нам понадобится комплексная запись аффинных преобразований плоскости. Напомним, как это делается. Векторное пространство $\mathbb{R}^2$ можно рассматривать как множество комплексных чисел c операцией сложения комплексных чисел и умножением на вещественное число, установив соответствие:

$(x, y) \leftrightarrow x + iy.$ Тогда любое аффинное преобразование $T$ запишется в виде $T(z) = z' = az + b\overline{z} + c,$ где $a, b, c$ — комплексные постоянные.

Приведём примеры аффинных преобразований, записанных в комплексной форме. Сдвиг на вектор $b$ запишется как $T(z) = z + b$ . Поворот на угол $\alpha$ : $T(z) = e^{i\alpha}z$ . Отражение относительно действительной оси: $T(z)= \overline{z}$ . Отражение относительно мнимой оси: $T(z) = - \overline{z}$ . Сжатие с коэффициентом сжатия $r$ : $T(z) = rz$ .

Рассмотрим несколько примеров. Пусть множеством сгущения является единичная окружность, и пусть $n$ аффинных преобразований таковы, что $k$ -е преобразование переводит в окружность с центром в $k$ -й вершине правильного $n$ -угольника так, что все эти окружности равны, касаются друг друга, и единичная окружность будет описывать эти окружности.

Схема построения фрактала из окружностей

Будем записывать аффинные преобразования в комплексной форме. Несложно заметить, что $T_k$ имеют вид

$T_i(z) = \left(\frac{z}{1 + \frac{1}{\sin{\frac{\pi}{n}}}} + \frac{1}{1 + \sin{\frac{\pi}{n}}}\right)\cdot{e}^{\frac{2 \pi k {i}}{n}}.$ В результате получаются следующие изображения ( $n = 2, 3, 4, 5, 6$ ).

Системы итерируемых функций со сгущением, фрактал из окружностей

Для построения использовался рандомизированный алгоритм, который заключается в следующем. Строится последовательность точек $\{z_m\}_m$ , определённая следующим образом ( $z_0 = a$ ):

$z_m = T_1(z_{m-1}) \vee T_2(z_{m-1}) \vee \ldots \vee T_n(z_{m-1}) \vee c_m,$ где $c_m$ — случайно выбранная из $C$ точка, а какое из преобразований применять также выбирается случайным образом.

Остановимся на реализации данного алгоритма на Java. Для работы с комплексными числами понадобится класс Complex, реализация которого приведена ниже.

/**
 * Класс реализует основные функции и операции над комплексными числами
 */
 public class Complex implements Cloneable
 {
	/**
	 * Конструктор по действительной и мнимой частям
	 */
	public Complex(double real, double imag)
	{
		this.real = real;
		this.imag = imag;
	}

	/**
	 * Конструктор комплексных чисел вида real + i * 0
	*/
	public Complex(double real)
	{
		this(real, 0.0);
	}

	...

	/**
	 * @return z * conj(z)
	*/
	public static double norm(Complex z)
	{
		return z.real * z.real + z.imag * z.imag;
	}

	/**
	 * @return |z| = sqrt(z * conj(z))
	 */
	public static double abs(Complex z)
	{
		return Math.sqrt(norm(z));
	}

	/**
	 * @return this + z
	 */
	public Complex add(Complex z)
	{
		return new Complex(real + z.real, imag + z.imag);
	}

	/**
	 * @return this + r
	*/
	public Complex add(double r)
	{
		return new Complex(real + r, imag);
	}

	/**
	 * @return this - z
	 */
	public Complex sub(Complex z)
	{
		return new Complex(real - z.real, imag - z.imag);
	}

	/**
	 * @return this - r
	 */
	public Complex sub(double r)
	{
		return new Complex(real - r, imag);
	}

	/**
	 * @return this * z
	 */
	public Complex mul(Complex z)
	{
		return new Complex(real * z.real - imag * z.imag,
			imag * z.real + real * z.imag);
	}

	/**
	 * @return this * r
	 */
	public Complex mul(double r)
	{
		return new Complex(real * r, imag * r);
	}

	/**
	 * @return this / z
	 */
	public Complex div(Complex z)
	{
		return this.mul(conj(z)).div(norm(z));
	}

	/**
	 * @return this / r
	 */
	public Complex div(double r)
	{
		return this.mul(1.0 / r);
	}
    
	/**
	 * @return z ^ 2
	 */
	public static Complex sqr(Complex z)
	{
		return z.mul(z);
	}

	/**
	* @return сопряжённое к z число
	*/
	public static Complex conj(Complex z)
	{
		return new Complex(z.real, -z.imag);
	}

	/**
	 * @return аргумент числа z
	 */
	public static double arg(Complex z)
	{
		return Math.atan2(z.imag, z.real);
	}

	/**
	 * @return this * exp(i * phi)
	 */
	public Complex rotate(double phi)
	{
		return this.mul(new Complex(Math.cos(phi), Math.sin(phi)));
	}

	/**
 	 * exp(z) = exp(Re(z)) * (cos(Im(z)) + i * sin (Im(z)))
	 */
	public static Complex exp(Complex z)
	{
		return new Complex(Math.exp(z.real)).rotate(z.imag);
	}
	
	...

	/**
	 * ln(z) = ln(|z|) + i * arg(z)
	 */
	public static Complex ln(Complex z)
	{
		return new Complex(Math.log(abs(z)), arg(z));
	}

	/**
	 * z ^ w = exp(w * ln(z))
	 */
	public static Complex pow(Complex z, Complex w)
	{
		return exp(w.mul(ln(z)));
	}

	/**
	 * z ^ r = exp(r * ln(z))
	 */
	public static Complex pow(Complex z, double r)
	{
		return pow(z, new Complex(r));
	}

	/**
	 * @return z ^ (1/2)
	 */
	 public static Complex sqrt(Complex z)
	{
		return pow(z, 0.5);
	}

	private final double real;
	private final double imag;
	public static final Complex I = new Complex(0, 1);

	...

	/**
	 * Генерация случайных комплексных чисел на отрезке и окружности
	 */
	 public static class Random
	{
		/**
		 * @return случайное комплексное число из отрезка [0, 1]
		 */
		public static Complex random()
		{
			return new Complex(random.nextDouble());
		}
	
		/**
		 * @return случайное комплексное число на единичной окружности
		 */
		public static Complex randomPointOnCircle()
		{
			return exp(I.mul(2 * PI * random.nextDouble()));
		}

		/**
		 * @return exp(2 * PI * I / n * k), k случайное число из 0..n - 1
		 */
		public static Complex randomPointOnCircle(int n)
		{
			return exp(I.mul(2 * PI * random.nextInt(n) / n));
		}
		
		private static java.util.Random random = new java.util.Random();
	}
}

Тогда рандомизированный алгоритм можно реализовать следующим образом.

public class Painter
{
	public static interface Map
        {
        	public Complex map(Complex z);
	}

	/**
	 * Определение прямоугольника, в котором находится фрактал
	 */
	private Rectangle2D getBounds()
	{
		double minX = Double.MAX_VALUE;
		double minY = Double.MAX_VALUE;
		double maxX = Double.MIN_VALUE;
		double maxY = Double.MIN_VALUE;
		
		Complex z = start;
		for (int n = 0; n < TEST_COUNT; ++n)
		{
			z = map.map(z);
			if (n < BEGIN)
				continue;
			if (z.getReal() < minX)
				minX = z.getReal();
			if (z.getReal() > maxX)
				maxX = z.getReal();
			if (z.getImag() < minY)
				minY = z.getImag();
			if (z.getImag() > maxY)
     				maxY = z.getImag();
		}
		return new Rectangle2D.Double(minX, minY, maxX - minX, maxY - minY);
	}

	/**
	 * Определяем, как нужно растянуть и сдвинуть изображение, чтобы оно заняло прямоугольник 
	 *(0, size.width) x (0, size.height)
	*/
	private AffineTransform getTransform()
	{
		Rectangle2D rectangle = getBounds();
		double scale = Math.min((size.width - 2 * BORDER) / rectangle.getWidth(),
			(size.height - 2 * BORDER) / rectangle.getHeight());
		AffineTransform transform =
			AffineTransform.getTranslateInstance(
			-rectangle.getCenterX(), -rectangle.getCenterY());
		transform.preConcatenate(
			AffineTransform.getScaleInstance(scale, -scale));
		transform.preConcatenate(AffineTransform.getTranslateInstance(
			size.getCenterX(), size.getCenterY()));
		return transform;
	}

	public Image createImage()
	{
		BufferedImage image = new BufferedImage(size.width, size.height, 
			BufferedImage.TYPE_INT_RGB);
		Graphics graphics = image.getGraphics();
		graphics.setColor(Color.WHITE);
		graphics.fillRect(0, 0, size.width, size.height);
		AffineTransform resultTransform = new AffineTransform();
		resultTransform.concatenate(getTransform());
		Complex z = start;
		for (int n = 0; n < count; ++n)
		{
			z = map.map(z);
			if (n < BEGIN)
				continue;
			Point2D point = resultTransform.transform(
				new Point2D.Double(z.getReal(), z.getImag()), null);
			if ((point.getX() < 0) || (point.getX() > size.width - 1) || 
				(point.getY() < 0) || (point.getY() > size.height - 1))
		                continue;
			image.setRGB((int)point.getX(), (int)point.getY(), color.getRGB());
		}
		return image;
	}

	public void setMap(Map map)
	{
		this.map = map;
	}
	
	...

	private Complex start = new Complex(0.0, 1.0);
	private int count = 300000;
	private Rectangle size = new Rectangle(640, 480);
	private Color color = Color.BLACK;
	private Map map;
	private static final int TEST_COUNT = 1000;
	private static final int BEGIN = 100;
	private static final int BORDER = 20;
}

Теперь, для того чтобы запрограммировать систему итерируемых функций со сгущением нужно реализовать интерфейс Painter.Map. Например, приведённый выше пример реализуется следующим образом.

public class Circles implements Painter.Map
{
	public Circles(int n)
	{
		this.n = n;
	}

	public Complex map(Complex z)
	{
		double p = Math.random();
		if (p <= 0.05)
			return Complex.Random.randomPointOnCircle();
		return z.div(1 + 1 / sin(PI / n)).add(1 / (1 + sin(PI / n))).mul(
			Complex.Random.randomPointOnCircle(n));
	}

	private int n;
}

Приведём ещё несколько систем со сгущением. Добавим ещё поворот окружности на $\pi$ перед сдвигом, в примере выше:

$T_i(z) = \left(-\frac{z}{1 + \frac{1}{\sin{\frac{\pi}{n}}}} + \frac{1}{1 + \sin{\frac{\pi}{n}}}\right)\cdot{e}^{\frac{2 \pi k {i}}{n}}.$

public class CirclesInv implements Painter.Map
{
	public CirclesInv(int n)
	{
		this.n = n;
	}

	public Complex map(Complex z)
	{
		double p = Math.random();
		if (p <= 0.05)
			return Complex.Random.randomPointOnCircle();
		return z.div(-1 - 1 / sin(PI / n)).add(1 / (1 + sin(PI / n))).mul(
			Complex.Random.randomPointOnCircle(n));
			}

	private int n;
}

Пусть снова множество сгущения — единичная окружность. Рассмотрим два аффинных преобразования:

$T_1(z) = \frac13z + \frac23,$ $T_2(z) = \frac13z + \frac43.$

public class PyramidCircles implements Painter.Map
{
	public Complex map(Complex z)
	{
		double p = Math.random();
		if (p <= 1.0 / 3)
			return Complex.Random.randomPointOnCircle();
		if (p <= 2.0 / 3)
			return z.mul(1.0 / 3).add(2.0 / 3);
		return z.mul(1.0 / 3).add(4.0 / 3);
	}
}

В случае $n = 2$ можно использовать половинку окружности.

Теперь обратимся к деревьям. Пусть множество сгущения является отрезком $[-i, 0]$ . Рассмотрим пару аффинных преобразований:

$T_1(z) = r(z + i) \cdot {e}^{\frac{i\pi}{4}},$ $T_2(z) = r(z + i) \cdot {e}^{-\frac{i\pi}{4}}.$ В результате итерирования получится Y-дерево. Ниже приведены рисунки при $r = \frac12$ , $r = \frac{1}{\sqrt{2}}$ .

public class YTree implements Painter.Map
{
	public YTree(double r)
	{
		this.r = r;
	}

	public Complex map(Complex z)
	{
		double p = random();
		if (p <= 0.005)
			return Complex.Random.random().rotate(-PI / 2);
		if (p <= 0.475)
			return z.add(I).mul(r).rotate(PI / 4);
		return z.add(I).mul(r).rotate(-PI / 4);
	}

	private double r;
}

Системы итерируемых функций со сгущением, Y-дерево

Пусть множеством сгущения является множество в виде буквы H: $[-1, 1] \cup [-1+\frac{i}{2}, -1 - \frac{i}{2}] \cup [1+\frac{i}{2}, 1 - \frac{i}{2}]$ . А аффинные преобразования имеют вид:

$T_1(z) = \frac{z}{2.5} + 1 + \frac{i}{2},$ $T_2(z) = \frac{z}{2.5} + 1 - \frac{i}{2},$ $T_3(z) = \frac{z}{2.5} - 1 + \frac{i}{2},$ $T_4(z) = \frac{z}{2.5} - 1 - \frac{i}{2}.$ В результате итерирования этой системы получим H-дерево.

public class HTree implements Painter.Map
{
	public Complex map(Complex z)
	{
		double p = random();
		if (p <= 0.067)
			return Complex.Random.random().mul(2).sub(1);
		if (p <= 0.133)
			return Complex.Random.random().sub(0.5).rotate(PI / 2).add(1);
		if (p <= 0.2)
			return Complex.Random.random().sub(0.5).rotate(PI / 2).sub(1);
		if (p <= 0.4)
			return z.div(2.5).add(new Complex(1, 0.5));
		if (p <= 0.6)
			return z.div(2.5).add(new Complex(-1, 0.5));
		if (p <= 0.8)
			return z.div(2.5).add(new Complex(1, -0.5));
		return z.div(2.5).add(new Complex(-1, -0.5));
	}
}

Системы итерируемых функций со сгущением, H-дерево

Пусть теперь множество сгущения имеет вид: $\left[0, {e}^{\frac{i\pi}{4}}\right] \cup \left[0, {e}^{\frac{i3\pi}{4}}\right]$ . Зададимся двумя преобразованиями сжатие-сдвиг:

$T_1(z) = \frac{z}{2} + {e}^{\frac{i\pi}{4}},$ $T_2(z) = \frac{z}{2} + {e}^{\frac{i3\pi}{4}}.$ В этом случае получим V-дерево.

public class VTree implements Painter.Map
{
	public Complex map(Complex z)
	{
		double p = random();
		if (p <= 0.005)
			return Complex.Random.random().rotate(PI / 4);
		if (p <= 0.01)
			return Complex.Random.random().rotate(3 * PI / 4);
		if (p <= 0.6)
			return z.div(2).add(exp(I.mul(PI / 4)));
		return z.div(2).add(exp(I.mul(3 * PI / 4)));
	}
}

Системы итерируемых функций со сгущением, V-дерево

И напоследок рассмотрим дерево Пифагора. Множеством сгущения является квадрат единичный квадрат с центром в нуле стороны которого параллельны координатным осям. Несложно понять, что два аффинных преобразования имеют вид

$T_1(z) = \cos(\varphi) z {e}^{-\varphi{i}} + \frac12 + \frac{{i}}{2} + \left(-\frac12 + \frac{{i}}{2}\right) \cos(\varphi) {e}^{-\varphi{i}},$ $T_2(z) = \sin(\phi) z {e}^{\left(\frac{\pi}{2}-\varphi\right){i}} - \frac12 + \frac{{i}}{2} + \left(\frac12 + \frac{{i}}{2}\right) \sin(\varphi) {e}^{\left(\frac{\pi}{2}-\varphi\right){i}},$ где $\varphi$ — угол наклона правого верхнего квадрата.

public class PythagorasTree implements Painter.Map
{
	public Complex map(Complex z)
	{
		double p = random();
		if (p <= 0.005)
			return Complex.Random.random().add(new Complex(-0.5, 0.5));
		if (p <= 0.01)
			return Complex.Random.random().add(new Complex(-0.5, -0.5));
		if (p <= 0.015)
			return Complex.Random.random().rotate(PI / 2).add(new Complex(-0.5, -0.5));
		if (p <= 0.02)
			return Complex.Random.random().rotate(PI / 2).add(new Complex(0.5, -0.5));
		if (p <= 0.02 + 0.98 * cos(phi) * cos(phi))
		return z.mul(cos(phi)).rotate(-phi).add(
			new Complex(0.5, 0.5)).add(new Complex(-0.5, 0.5).mul(cos(phi)).rotate(-phi));
		return z.mul(sin(phi)).rotate(PI / 2 - phi).add(
			new Complex(-0.5, 0.5)).add(new Complex(0.5, 0.5).mul(sin(phi)).rotate(PI / 2 - phi));
	}

	public PythagorasTree(double phi)
	{
		this.phi = phi;
	}

	private double phi;
}

Системы итерируемых функций со сгущением, Дерево Пифагора

Скачать:

Исходный код программы построения.

Смотрите также:

Ссылки:

Р. М. Кроновер. Фракталы и хаос в динамических системах. Основы теории. Москва: Постмаркет, 2000. 112—120,
Kissing Circles - Appolonian Carpet ,
Circular Infinity ,
Construction of IFS Fractals of Specific Similarity Dimension .