Generating Kronecker Product Based Fractals

• Download full project source - 12 Kb

Introduction

Fractals [1-6] are amazing and often colorful images that have been created and enjoyed for centuries, but their study and computer generation started only at the end of the last century.

Here is a simple definition:

In our case, fractals are looking like a geometric pictures, and they are called often simply a plot or a graph.

There are many types/categories of fractals, e.g.: IFS based [7], L-system generated [8], created using Chaos game method [9], etc. Enjoy a huge gallery of fractals shown in [6] and become familiar with some of them. Actually, both [7] and [8] are very good online generators of fractals. They even allow to enter user's own object: table in [7] and a set of axiom, production rules and other parameters in [8].

This project is offering to any website owner to use the set of project components as online generator of unlimited (well, almost...) number of fractals. In addition, any user can use this project software as a desktop application. Just download it and start using.

Only 4 HTML pages and 1 JavaScript file are presenting a whole very compact source code you need to become a special type of fractal designer. Everyone with a computer already has a reliable tool able generating fractals: this is the browser, and the only requirement for it is to support "canvas" object.

About Kronecker product based fractals

Only Kronecker product [10] based fractals (KPBF) are described here together with their pecularities related to our "KPBF generator".

It should be emphasized, that in many books and articles [11-20] the possibility to make fractals using Kronecker product is mentioned and picture of a few fractals are shown. In some of them samples of a few initial matrices are shown, but not even one of them described clear the procedure required to use Kronecker product.

Let's start with a definition:

Remarks:

• In other words, it simply means that such matrix can be used to produce a fractal image.
• All definitions would be applied mostly to Kronecker product related fractals.

The following statement/lemma could be easily checked and even proved formally:

The essence of the fractal image is self-replications (at least, self-similar replications). The method to produce such self-similar replications in our case is amazingly simple. A formal recurrent algorithm of creating fractal matrix is the following.

Let's take a closer look at VOE.js - small JavaScript library containing only really generic plotting helper functions that were already used many times and proved their usefulness and reliability [21]

Only 2 key functions will be described briefly here, i.e.: mkp2() and pmat01().

The first one is the function mkp2() realizing Kronecker product:

  // HFJS#5: Return the Kronecker product of the a and b matrices.
  // Note: both a and b must be matrices, i.e., 2D rectangular arrays.
  function mkp2(a,b) {
    var m=a.length, n=a[0].length, p=b.length, q=b[0].length;
    var rtn=m*p, ctn=n*q; var r=new Array(rtn);
    // Building final matrix filled with zeros.
    for (var i=0; i<rtn; i++) {r[i]=new Array(ctn)
      for (var j=0;j<ctn; j++) {r[i][j]=0} }
    // Calculating final KP matrix.
    for (var i=0; i<m; i++) {
      for (var j=0; j<n; j++) {
        for (var k=0; k<p; k++) {
          for (var l=0; l<q; l++) {
            r[p*i+k][q*j+l]=a[i][j]*b[k][l];
          }}}}//all4forend
    return(r);
  }

As you can see, it has straightforward 2 steps:

• Building final matrix filled with zeros.
• Calculating final KP matrix using nested 4 loops over 4 dimensions of 2 matrices.

Oh, historically the first such function was mkp() - the arrow function for the same product [21]. Here mkp2() is used, because it would be easier to "translate" it to your language if you want to. By the way, find if there is the one for you in [21] among more than 20 language samples.

Even just looking at the resultant matrix you can see fractal to be plotted. In other words: starting from second order fractal matrix is already good to be plotted.

To understand plotting technique, please take a closer look at pmat01().

  // HFJS#3: Plot any matrix mat (filled with 0 & not 0 items).
  //         Set error p in the page: <p id="epId"></p>, sc - Scale (0..max)
  //         fgc/bgc - FG/BG colors; rt - rotate 90 degree if true (once).
  function pmat01(mat, fgc, bgc, sc, rt) {
    // Setting basic vars for canvas and matrix
    var cvs = document.getElementById('cvsId');
    var ctx = cvs.getContext("2d");
    var w = cvs.width, h = cvs.height;
    var m = mat[0].length, n = mat.length, k=0, dsz=1;
    console.log("MAT rxc", n, "x", m); // n - rows. m - cols
    if(n<21&&m<21) {matl2cons("MAT2PLOT",mat)}
    if(sc!=1) {ctx.scale(sc,sc)};
    if(sc<0.9) {dsz=2};
    // Setting BG and plotting FG colors
    ctx.fillStyle=bgc; ctx.fillRect(0,0,w,h);
    ctx.fillStyle=fgc;
    // Plotting "dots" (!=0 values in matrix) & counting them.
    // n - rows. m - cols
    for(var i=0; i<n; i++) {
      for(var j=0; j<m; j++) {
        if(mat[i][j]!=0) { k++;
          if(rt&&n==m) {ctx.fillRect(i,j,1,1)} else {ctx.fillRect(j,i,1,1)}
        };
      }//fend j
    }//fend i
    // Outputting fractal matrix "signature": matrix sizes & number of dots.
    var ms="Matrix("+n+"x"+m+") "+k+" dots";
    var ep=document.getElementById("epId").innerHTML;
    document.getElementById("epId").innerHTML=ep+"<br>"+ms;
  }//func end

As you can see, it is a very small, simple function, and it will plot any fractal matrix, which is a legal rectangular JavaScript matrix. This function is very clear, nothing complicated: it interprets a matrix as a canvas points/dots with x, y coordinates and prints a dot if a value in the matrix is not equal to zero.

In our case of KPBF, we already have matrix, and it was not difficult to find out how to plot it.

A few years ago I was puzzled: why there is no even one picture of a Brownian tree made in PARI/GP or in R scripts?.

So, I've started with PARI/GP:

• Matrix was created to collect. random "movements" and was initially filled with zeros. Later 1 is put in the visited cell of this matrix.
• Plotting helper function similar to used here was created.
• As result, 4 types of a Brownian tree [22] were generated and plotted.

Later I've repeated all these steps in R. Now there are a lot of Brownian trees, including made in PARI/GP and R [22].

Now, any user have a clear algorithm for creating KPBF and plotting helper function to plot fractals. Moreover, this helper function can be used for plotting any other type of points based fractals, e.g., as Brownian tree mentioned above.

There are virtually infinitely many fractals of this type. You are limited only by your creativity and the power of your computer.

Informal virtual infinity definition is short and simple: a different size and a different content of matrix will produce a different fractal. Let's add to infinity definition a color: different color - different fractal. Of course, it's a little bit of a speculation, but it is still good for our understanding.

Usually user starts from order 2, because order 1 means initial matrix itself (no Kronecker product yet).

Next order replications could be scaled up or scaled down or/and just spreading in one or many directions up to to infinity. In most cases, user can count order of plotted fractal starting from the smallest basic sub-figure (e.g., tiny "+" in "Plus sign" fractal) to the biggest plotted figure. This is shown in the picture below for orders 1, 2 and 3 of this fractal.

Note: both the smallest and the biggest sub-figures could be not visible or only partially visible.

Some authors call special type of fractals looking differently from the well-known one a "mutant". I prefer to call them "siblings", because, in most cases, they are actually new type of a "carpet" fractal, for example. These "siblings" have: different configuration of multiple sub-images, different quantity of them in each order and layer. I prefer to call them "Rug fractals", instead of "carpet". And they really look like small area rugs for me.

See it for yourself in the figures below.

I would agree to call the next one a "Sierpinski carpet mutant", because it copies the Sierpinski carpet [3] structure (in general), but has central square dislocated.

Surprisingly, it was the only one "mutant" I've found in [17]. All others shown here are mine "siblings". Additionally, find a few others in "Demo" page.

Next figure shows Sierpinski triangle fractal and three Triangle sibling fractals.

As you can see they are really new Triangle fractals. The only common thing with the Sierpinski triangle [4] is the basic image of a triangle. Find a few additional Triangle sibling fractals in "Demo" page.

Remarks:

• The Kronecker product is stubborn, sometimes it refuses produce a fractal from any matrix, especially from a rectangular matrix (i.e., not a square one).
• Also, basic matrix/image could rotate unpredictably.
• Remember: nice colorful fractal's background is coming from number 1, zero gives you fractal's basic figure in white. But it depends on an opinion of the fractal creator, i.e., "what is a basic image?".

Using the pages

Using "Demo" page

Start with "Demo" page, which is a part of "KPBF Generator" and has the educational purpose. You can play with different orders and colors of selected popular fractals and many new ones. In the drop-down list of the "Demo" page the first 4 fractals are well known, but the others were "discovered" last year using R scripts. The well-known fractals are following: Sierpinski carpet and triangle [3,4,11,13,15,16] (already shown above), Vicsek [2,20], At LaGuardia [18,20], Checkerboard [15,16] and Hexagon [18]. They are shown in the figures below. The first three can be found on Wikipedia also, but implemented using different methods.

The new fractals are nice too, never seen before, or, at least, hard to find: Chessboard, "H", Rug, "5/2" and many additional fractals.

Using "Design" page

The Duo "Design"/"Plot" pages is a part of "KPBF Generator". It allows any user visually design and build fractal matrix using "Design" page, then send it to selected plotting page and try all orders available for this matrix.

The "Design" page is a unique one, but a regular "Plot" page is almost a copy of "Demo" page. It uses already familiar to user drop-downs and messages, etc.

In the figure below you can see both pages (presented partially).

"Design" page will tell a user if the matrix he created is good or bad one. If it is still bad, then user need to correct this matrix code, according to the error message, or any other clue. Anyway, the "Plot" button is blocked in case of any error.

Pay attention to the displayed fractal matrix "signature" that shows matrix dimensions and a number of dots generated. A signature in the figure above is the following: Matrix(243x243) 3125 dots. (for Vicsek fractal, order 5).

It should be mentioned, that all pages are checking any created matrix intensively, to prevent browser from crash, i.e., checking everything that can be checked easily. It's a little bit complicated, because there is no matrix object in standard JavaScript. Anyway, it's not worth to write/test a compiler like script. In case of error, - no harm done, just extra click to go back or reload page. In fact, user still can get additional error notices from browser debugger (in Chrome). In this case, - just save matrix code and reload "Design" page.

Note: Created matrix can be viewed in natural rectangular form in the console log (in Chrome). It's recommended to keep console opened while testing the new matrix code.

Before adding such thorough control for matrix, in case any page hit a memory limit, - my Chrome browser was upset and telling me: "Aw, Snap! Something went wrong while displaying this webpage. Kill or Reload page." Now, this is not the case anymore.

It is recommended that the new user insert JavaScript matrix code in the big text-area of the "Design" page exactly as it is shown in the picture above. Because it helps user to control visually number of columns and code syntax of the matrix. Anyway, later matrix code will be converted to 1 line of code, after all white spaces will be deleted by script.

In the script of the "Demo" page find code of used matrices (mostly written in one line, as it is shown below).

  // Well known fractals
  if(fi==1) M=[[1,1,1],[1,0,1],[1,1,1]];
  if(fi==2) M=[[1,1],[0,1]];
  if(fi==3) M=[[0,1,0],[1,1,1],[0,1,0]];
  if(fi==4) M=[[1,1,1,1],[1,1,0,0],[1,0,1,0],[1,0,0,1]];
  // New fractals
  if(fi==5) M=[[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[0,0,0,0,1,1,1,1],[0,0,0,0,1,1,1,1],[0,0,0,0,1,1,1,1],[0,0,0,0,1,1,1,1]];
  if(fi==6) M=[[1,1,1,1,1,1,1],[1,0,0,0,0,0,1],[1,1,1,0,1,1,1],[1,1,1,0,1,1,1],[1,1,1,0,1,1,1],[1,0,0,0,0,0,1],[1,1,1,1,1,1,1]];
  ...

Using "Plot" pages

There are two plotting pages: for regular test plotting and for fine publishing quality plotting. If testing - use "Regular plot" page. It works faster.

If preparing article for Code Project - use "Fine plot" page (shown below partially).

"Fine plot" page allows user:

• To enter foreground color (FG) and/or background color (BG). This will trump selected color (if any) and default white BG.
• To set scale, which helps to fit image nicely in the canvas frame.
• To set square size of the canvas (the bigger, - the better).
• Rotate image once by 90°.

• If you set matrix size to 600, and there is no any image in the canvas area, then look at a signature. If it shows: "Matrix(2187x2187) 78125 dots", then generated image would be too big. Actually, almost 4 times bigger (2187/600). In this case, - set scale to 0.25 first and plot again.
• If scale is set less then 1 then color will fade. So, choose order to fit canvas size as close as possible. E.g., in case of Vicsek fractal: It is better to use order 6, than 5.
• Clicking "Back to Design" link will reset "Design" page, which is good for the new matrix. Use browser "Back" button if you need to update the designed matrix, for example.

Conclusion

"KPBF Generator" consists of 4 HTML pages and 1 JavaScript file, and this is a whole source code for this project.

Also, find a bonus file with a list of selected tested matrix codes.This list will help user to understand how such fractals generation works and what to expect from any matrix.

Here is a summery of some new (or at least hard to find) properties related to this type of fractals:

• Not each fractal matrix (even the one filled only with 0/1) will produce fractal image.
• If 0 and 1 will be swapped then the so called "reversed" fractal could be produced. But it depends on which one fractal is called "direct" and which one is called "reversed".
• Only 1 zero is required, but instead of the number 1 any integer can be used.
• In addition to the well-known fractals, it is easy to generate "siblings" for them, and they are nice too.
• Using different languages/tools (e.g., R, PARI/GP, etc.) the differently looking fractals can be produced from the same fractal matrix. It happens, because some plotting tools automatically applying different type of scaling, and it's often uncontrolled.

For languages not having built-in function (or operator) for Kronecher product many custom functions already built and presented on Rosetta Code Wiki [21]. Find also a few new fractals there [23].

It is interesting and remains as an open question: Why using different approaches, e.g., IFS based, L-system generation, etc., or even using just a recursive function, - it is still possible to reproduce Sierpinski carpet or triangle [3,4], for example?

Theoretical and practical uses can be found in [12,17,18]. Almost all branches of applications are covered in Fractals Journal [19].

Finally, having "KPBF Generator" any person, even without programming background, could be the designer, inventor and creator of this pretty broad (virtually infinite) category of fractals.

References

1. Fractal, Wikipedia, the free encyclopedia, URL: https://en.wikipedia.org/wiki/Fractal.
2. Vicsek fractal, Wikipedia, the free encyclopedia, URL: https://en.wikipedia.org/wiki/Vicsek_fractal.
3. Sierpinski carpet, Wikipedia, the free encyclopedia, URL: https://en.wikipedia.org/wiki/Sierpinski_carpet.
4. Sierpinski triangle, Wikipedia, the free encyclopedia, URL: https://en.wikipedia.org/wiki/Sierpinski_triangle.
5. Category:Fractals, Wikipedia, the free encyclopedia, URL: https://en.wikipedia.org/wiki/Category:Fractals.
6. List of fractals by Hausdorff dimension, Wikipedia, the free encyclopedia, URL: https://en.wikipedia.org/wiki/List_of_fractals_by_Hausdorff_dimension.
7. Toal R., Iterated Function Systems, URL: http://cs.lmu.edu/~ray/notes/ifs/.
8. Roast K., L-Systems Turtle Graphics Renderer, URL: http://www.kevs3d.co.uk/dev/lsystems/.
9. Chaos game, Wikipedia, the free encyclopedia, URL: https://en.wikipedia.org/wiki/Chaos_game.
10. Kronecker product, Wikipedia, the free encyclopedia, URL: https://en.wikipedia.org/wiki/Kronecker_product.
11. Gazalé, Midhat J. (1999), Gnomon: From Pharaohs to Fractals, Princeton University Press, ISBN 9780691005140.
12. Xue D., Zhu Ya., Zhu G.-X. and Yan X. Generalized kronecker product and fractals, Proc. SPIE 2644, Fourth International Conference on Computer-Aided Design and Computer Graphics, 75, (1996), doi:10.1117/12.235499.
13. Haugland K, Fractals in theory and practice, (2013), URL: https://www.codeproject.com/Articles/650821/Fractals-in-theory-and-practice.
14. Steeb W.-H. (1997), Matrix Calculus and Kronecker Product with Applications and C++ Programs., World Scientific Publishing, ISBN 9810232411
15. Hardy A., Steeb W.-H. (2008), Mathematical Tools in Computer Graphics with C# Implementations, World Scientific, ISBN 9789812791023.
16. Steeb W.-H. (2014), The Nonlinear Workbook. Chaos, Fractals, Cellular Automata, Genetic Algorithms, Gene Expression Programming, Support Vector Machine, Wavelets, Hidden ... Java and SymbolicC++ Programs, (6th Edition), World Scientific Publishing Company, ISBN: 9789814583473.
17. Stepanyan I.V., Petoukhov S.V. The Matrix Method of Representation, Analysis and Classification of Long Genetic Sequences. (2013). URL: https://arxiv.org/abs/1310.8469v1.
18. Leskovec J., Chakrabarti D., Kleinberg J. at al. Kronecker Graphs: An Approach to Modeling Networks. (2010), Journal of Machine Learning Research 11, URL: https://cs.stanford.edu/people/jure/pubs/kronecker-jmlr10.pdf.
19. Fractals Journal, World Scientific, URL: http://www.worldscientific.com/page/fractals/aims-scope.
20. Wicklin R., Self-similar structures from Kronecker products, (2014), URL: http://blogs.sas.com/content/iml/2014/12/17/self-similar-structures-from-kronecker-products.html.
21. Kronecker product, Rosetta Code Wiki, URL: http://rosettacode.org/wiki/Kronecker_product.
22. Brownian tree, Rosetta Code Wiki, URL: http://rosettacode.org/wiki/Brownian_tree
23. Kronecker product based fractals, Rosetta Code Wiki, URL: http://rosettacode.org/wiki/Kronecker_product_based_fractals..

History

05/27/2017 Article published initially.

05/30/2017 Cleaning up leftovers from stripped (by submission wizard) tags, etc. Adding “History”.