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

Произведение Кронекера

Пусть — матрица размером , — матрица размером . Произведением Кронекера матриц и называется блочная матрица размера вида

Другими словами, элементы матрицы вычисляются по формуле:
Напишем функцию для вычисления произведения Кронекера матриц.

public static int[][] product(int[][] A, int[][] B) {
    int m = A.length;
    int n = A[0].length;
    int p = B.length;
    int q = B[0].length;
    int r = m * p;
    int s = n * q;
    int C[][] = new int[r][s];
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int u = 0; u < p; ++u) {
                for (int v = 0; v < q; ++v) {
                    C[i * p + u][j * q + v] = A[i][j] * B[u][v];
                }
            }
        }
    }
    return C;
}

Произведение Кронекера обладает многими хорошими свойствами, здесь же отметим только ассоциативность, и что матрица является нейтральным элементом относительно этой операции.

Определим -ую степень Кронекера матрицы , где — натуральное число, по формуле:

public static int[][] power(int[][] A, int n) {
    if (n == 0) {
        return new int[][] {{1}};
    }
    return product(power(A, n - 1), A);
}

Теперь по матрице построим изображение следующим очевидным образом: если не равно нулю, то пиксель с координатами покрасим в чёрный цвет, иначе же покрасим в белый.

public static Image draw(int[][] A)
{
    int r = A.length;
    int s = A[0].length;
    BufferedImage image = 
	new BufferedImage(s, r, BufferedImage.TYPE_INT_RGB);
    Graphics2D graphics = image.createGraphics();
    graphics.setColor(Color.WHITE);
    graphics.fill(new Rectangle2D.Double(0, 0, s, r));
    graphics.setColor(Color.BLACK);
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < s; ++j) {
            if (A[i][j] != 0) {
                graphics.fillRect(j, i, 1, 1);
            }
        }
    }
    return image;
}

Пусть матрица имеет вид

Рассмотрим степень Кронекера матрицы . Несложно заметить, что получится -ое приближение ковра Серпинского.

public static Image drawSierpinskiCarpet(int n) {
    return draw(
            power(new int[][]
            {{1, 1, 1},
             {1, 0, 1},
             {1, 1, 1}},
            n));
}
public static Image image;

public static void main(String[] args) {
    image = drawSierpinskiCarpet(6);

    int width = image.getWidth(null);
    int height = image.getHeight(null);
    JFrame frame = new JFrame();
    frame.addNotify();
    frame.setSize(frame.getInsets().left +
            frame.getInsets().right + width,
            frame.getInsets().top +
            frame.getInsets().bottom + height);
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

    frame.add(new JPanel() {
        @Override
        public void paintComponent(Graphics g) {
            Graphics2D G = (Graphics2D) g;
            if (image != null) {
                G.drawImage(image, 0, 0, null);
            }
        }

    });
    frame.setVisible(true);
}

Ковёр Серпинского

Рассматривая степени матрицы

получим пыль Кантора.

public static Image drawCantorDust(int n) {
    return draw(
        power(new int[][]
           {{1, 0, 1},
            {0, 0, 0},
            {1, 0, 1}},
            n));
}

Пыль Кантора

public static Image drawBoxFractal(int n) {
    return draw(
        power(new int[][]
            {{1, 0, 1},
             {0, 1, 0},
             {1, 0, 1}},
            n));
}


public static Image drawSierpinskiTriangle(int n) {
    return draw(
        power(new int[][]
            {{1, 0},
             {1, 1}},
            n));
}

Треугольник Серпинского

Пойдём дальше, теперь элементы матриц будут не целые числа, а вычеты по модулю какого-нибудь числа. Но код вычисления произведения и степени трогать не будем, а изменим функцию draw().

public static Image draw(int[][] A, int m) {
    Color[] colors = new Color[] {Color.WHITE, Color.RED, Color.GREEN, 
    	Color.BLUE, Color.ORANGE, Color.BLACK, Color.MAGENTA /*, ...*/};
    int r = A.length;
    int s = A[0].length;
    BufferedImage image = 
	new BufferedImage(s, r, BufferedImage.TYPE_INT_RGB);
    Graphics2D graphics = image.createGraphics();
    graphics.setColor(Color.WHITE);
    graphics.fill(new Rectangle2D.Double(0, 0, s, r));
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < s; ++j) {
            graphics.setColor(colors[A[i][j] % m]);
            graphics.fillRect(j, i, 1, 1);
        }
    }
    return image;
}

Построим модифицированный ковёр Серпинского.

public static Image drawModifiedSierpinskiCarpet(int n, int m) {
    return draw(
            power(new int[][]
            {{1, 1, 1},
             {1, 2, 1},
             {1, 1, 1}},
            n), m);
}

Ниже приведены избражения для и .


Ковёр Серпинского


Ковёр Серпинского

public static Image drawYetAnotherModifiedSierpinskiCarpet(int n, int m) {
    return draw(
            power(new int[][]
            {{1, 1, 1, 1, 1},
             {1, 2, 2, 2, 1},
             {1, 2, 0, 2, 1},
             {1, 2, 2, 2, 1},
             {1, 1, 1, 1, 1}},
            n), m);
}

Ниже приведены избражения для и .


Ковёр Серпинского


Ковёр Серпинского

public static Image drawModifiedSierpinskiTriangle(int n, int m) {
    return draw(
            power(new int[][]
            {{1, 0, 0},
             {1, 1, 0},
             {1, 2, 1}},
            n), m);
}

Аналогично, и .


Треугольник Серпинского Треугольник Серпинского

Сделаем фрактальный смайлик.

public static Image drawSmile(int n)
{
    return draw(
            power(new int[][]
            {{0, 1, 1, 1, 1, 1, 0},
             {1, 1, 2, 1, 2, 1, 1},
             {1, 1, 2, 1, 2, 1, 1},
             {1, 1, 1, 1, 1, 1, 1},
             {1, 2, 1, 1, 1, 2, 1},
             {1, 1, 2, 2, 2, 1, 1},
             {0, 1, 1, 1, 1, 1, 0}},
            n), 3);
}

Фрактальный смайлик

Ещё несколько картикок, без каких-либо комментариев.


Треугольник Серпинского Треугольник Серпинского

Ещё одним способом построения фракталов, очень близким к рассмотренному, являются двумерные переписывающие системы. Идея следующая: пусть задана матрица с элементами из множества и набор матриц , . На первом шаге в матрице каждый элемент заменим на блок . К полученной матрице, на втором шаге применим ту же процедуру, и т. д.

Заметим, что если , и ялвяется нулевой матрицей, то в результате применения шагов переписывающей системы получится -ая степень Кронекера матрицы . То есть, например, ковру Серпинского соответствует система

.

Более интересным примером является ковёр Хафермана.

.

package ru.xaoc.fractalworld.rewritingsystems;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Image;
import java.awt.geom.Rectangle2D;
import java.awt.image.BufferedImage;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class Main {
    public static int[][] rewrite(int[][] A, int[][][] Rs) {
        int r = A.length;
        int s = A[0].length;
        int p = Rs[0].length;
        int q = Rs[0][0].length;

        int[][] C = new int[r * p][s * q];
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < s; ++j) {
                for (int m = 0; m < p; ++m) {
                    for (int n = 0; n < q; ++n) {
                        C[i * p + m][j * q + n] = Rs[A[i][j]][m][n];
                    }
                }
            }
        }
        return C;
    }

    public static int[][] system(int[][] G, int[][][] Rs, int n) {
        if (n == 0) {
            return G;
        }
        return system(rewrite(G, Rs), Rs, n - 1);
    }

    public static Image draw(int[][] A) {
        int r = A.length;
        int s = A[0].length;
        BufferedImage image = 
		new BufferedImage(s, r, BufferedImage.TYPE_INT_RGB);
        Graphics2D graphics = image.createGraphics();
        graphics.setColor(Color.WHITE);
        graphics.fill(new Rectangle2D.Double(0, 0, s, r));
        graphics.setColor(Color.BLACK);
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < s; ++j) {
                if (A[i][j] != 0) {
                    graphics.fillRect(j, i, 1, 1);
                }
            }
        }
        return image;
    }


    private static Image drawSierpinskiCarpet(int n) {
        return draw(
                system(new int[][] {{1}},
                new int[][][] {{
                    {0, 0, 0},
                    {0, 0, 0},
                    {0, 0, 0}},

                   {{1, 1, 1},
                    {1, 0, 1},
                    {1, 1, 1}}
            }, n));
    }


    private static Image drawHafermanCarpet(int n) {
        return draw(
                system(new int[][] {{1}},
                new int[][][] {{
                    {1, 1, 1},
                    {1, 1, 1},
                    {1, 1, 1}},

                   {{0, 1, 0},
                    {1, 0, 1},
                    {0, 1, 0}}
            }, n));
    }

    public static Image image;
    public static void main(String[] args) {
        //image = drawSierpinskiCarpet(6);
        image = drawHafermanCarpet(6);

        int width = image.getWidth(null);
        int height = image.getHeight(null);
        JFrame frame = new JFrame();
        frame.addNotify();
        frame.setSize(frame.getInsets().left +
                frame.getInsets().right + width,
                frame.getInsets().top +
                frame.getInsets().bottom + height);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        frame.add(new JPanel() {
            @Override
            public void paintComponent(Graphics g) {
                Graphics2D G = (Graphics2D) g;
                if (image != null) {
                    G.drawImage(image, 0, 0, null);
                }
            }

        });
        frame.setVisible(true);
    }
}

Ковёр Хафермана

Ещё несколько картинок без комменариев.



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

Ссылки: