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

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

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

Сгущение есть не что иное, как сжатие с нулевым показателем сжатия, так как .

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

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

Теорема. Пусть , , , . Тогда и — аттрактор системы итерируемых функций со сгущением.

Далее нам понадобится комплексная запись аффинных преобразований плоскости. Напомним, как это делается. Векторное пространство можно рассматривать как множество комплексных чисел 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;
}
	

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

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;
}
	

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

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

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);
	}
}
	

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

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


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

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

В результате итерирования получится Y-дерево. Ниже приведены рисунки при , .

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-дерево Системы итерируемых функций со сгущением, Y-дерево

Пусть множеством сгущения является множество в виде буквы H: . А аффинные преобразования имеют вид:

В результате итерирования этой системы получим 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-дерево

Пусть теперь множество сгущения имеет вид: . Зададимся двумя преобразованиями сжатие-сдвиг:

В этом случае получим 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-дерево

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

где — угол наклона правого верхнего квадрата.

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;
}
	

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

Скачать:

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

Ссылки: