preface

Fractal, founded and named by B.B.Mandelbrot et al., is a geometry that studies irregular geometric forms.

The fractal graph as a whole is irregular everywhere. But from the local observation, the regularity of the graph is the same, that is, it has the property of self-similarity.

Generally speaking, fractal is defined as the shape of a definite geometric shape (metagrams) generated iteratively on its edge) approximately to that of the metagrams. This time I want to use canvas to draw some typical fractal graphs.

Basic Mathematics

Before drawing fractal graph, we need to clarify the mathematical system of Canvas first, so as to make good use of this tool to complete the drawing of fractal graph.

As we all know, the coordinate system adopted by Canvas is based on the top left corner of Canvas by default, with X-axis moving to the right and Y-axis moving down. The size of the canvas determines the maximum x and y axis of the coordinate system.

Suppose we want to implement a hexagon on a Canvas that is 300 by 300. The length of the hexagon is 50. Think about what to do.

Look at the basic shape of the hexagon and find the 12 edges. The next two edges are drawn in a group. After drawing the first edge, turn 60 degrees counterclockwise, then draw the second edge of the same length.

Let’s say I’m going from P1 to P2, to P3, to P4. So given the coordinates of P1 and P2, we also need to figure out what the coordinates of P3 and P4 are. This is a simple mathematical problem of finding the next coordinate based on coordinates and angles, and we can plot it by simple vertex conversion.

Rotation and coordinate point mapping

Let’s do a quick math review. The coordinates of P1 and P2 are known, and the length of P2P1 is r. After rotating the vector P1P2 clockwise by the Angle α2, the coordinate value of P3 is calculated.

Similarly, the formula for counterclockwise rotation can be obtained. The rotation matrix can also be obtained from the above deduction as follows.

Clockwise \ begin {bmatrix} cosine beta & sin beta \ \ – sine beta & cosine beta \ \ \ end {bmatrix} [cosine beta – sine beta sine beta cosine beta]	Counterclockwise \ begin {bmatrix} cosine beta & – sine beta \ \ sin beta & cosine beta \ \ \ end {bmatrix} [beta sine cosine beta – sine beta cosine beta]

Code implementation

1. Draw the hexagons. Start with the first point P1\(0,50\), P2\(50,50\), put the core module into the hexagon method, and iterate 6 times.Copy the code

  var ctx = canvas.getContext("2d");
      ctx.strikeStyle = "# 000";
      ctx.beginPath();
      const y = 50;
      ctx.moveTo(0, y);
      hexagon(ctx, 0, y, 50, y, 0.6);
Copy the code

2. The input parameters to the hexagon method are (CTX, x1, y1, x2, y2, n, m).

  function hexagon(ctx, x1, y1, x2, y2, n, m) {

    ctx.clearRect(0.0.300.300);

    // Clockwise 60 degrees
    ctx.moveTo(x2, y2);

    const x3 = x2 +

      (x2 - x1) * Math.cos(Math.PI / 3) +

      (y2 - y1) * Math.sin(Math.PI / 3);

    const y3 = y2 -

      (x2 - x1) * Math.sin(Math.PI / 3) +

      (y2 - y1) * Math.cos(Math.PI / 3);

    ctx.lineTo(x3, y3);

    // Counterclockwise 120 degrees
    const x4 = x3 +

      (x3 - x2) * Math.cos((Math.PI * 2) / 3) -

      (y3 - y2) * Math.sin((Math.PI * 2) / 3);

    const y4 = y3 +

      (y3 - y2) * Math.cos((Math.PI * 2) / 3) +

      (x3 - x2) * Math.sin((Math.PI * 2) / 3);

    ctx.lineTo(x4, y4);

    ctx.stroke();

    n++;

    if (n === m) {

      return false;

    } else{ hexagon(ctx, x3, y3, x4, y4, n, m); }}Copy the code

Vector operations

It can be seen from the above process that point drawing by coordinate is very troublesome and time-consuming. In addition, Canvas 2D coordinates are upside down with the conventional data coordinate system, so we will spend a lot of time in the calculation of coordinate points.

Therefore, in order to keep the logic of the code simple and easy to read, we can change our thinking to understand coordinate points as vectors. Just to review the common vector operations are the following.

Vector addition/subtraction.The dot product, the cross product. As shown in Figure 1, vector addition means that the path is drawn along V1 and v2, and the coordinate point of P2 is the sum of two vectors v1 and V2, which is [x1+x2, y1+y2]. The dot product is the geometric meaning of the dot product of a and B vectors, and is the projection component of A vector times b vector on A vector, as shown in Figure 2. The cross product is the area of two vectors, as shown in Figure 3.

Code implementation

Vectors are described as arrays of the form [x,y].

class Vector extends Array {

  constructor(x = 1, y = 0) {

    super(x, y);

  }

  copy() {

    return new Vector(this.x, this.y); }}Copy the code

Vectors plus and minus.

  add(v) {

    this.x += v.x;

    this.y += v.y;

    return this;

  }

  sub(v) {

    this.x -= v.x;

    this.y -= v.y;

    return this;

  }
Copy the code

The vector cross dot dot.

  cross(v) {

    return this.x * v.y - v.x * this.y;

  }

  dot(v) {

    return this.x * v.x + v.y * this.y;

  }
Copy the code

Vector rotation.

  rotate(rad) {

    const c = Math.cos(rad),

      s = Math.sin(rad);

    const [x, y] = this;

    this.x = x * c + y * -s;

    this.y = x * s + y * c;

    return this;

  }
Copy the code

The code for drawing a hexagonal snowflake can be rewritten as follows by vector operations. First, the Canvas coordinate system is flipped up and down to form the coordinate mode we are used to.

 var ctx = canvas.getContext("2d");

 ctx.translate(0, canvas.height);

 ctx.scale(1, -1);
Copy the code

Get v0 and v1 vectors, rotate them counterclockwise and clockwise, and get the same result as before, but the code is much more readable.

const v0 = new Vector(0.250);

const v1 = new Vector(50.250);

hexagon(ctx, v0, v1, 0.6);



function hexagon(ctx, v0, v1, n, m) {

    const v2 = v1.copy().sub(v0);

    v2.rotate((60 * Math.PI) / 180).add(v1); // Counterclockwise 60 degrees



    const v3 = v2.copy().sub(v1);

    v3.rotate((-120 * Math.PI) / 180).add(v2); // 120 degrees clockwisectx.beginPath(); ctx.moveTo(... v1); ctx.lineTo(... v2); ctx.lineTo(... v3); ctx.stroke(); n++;if (n === m) {

      return false;

    } else{ hexagon(ctx, v2, v3, n, m); }}Copy the code

practice

The logic law of fractal graph is the combination of recursion and basic graph. In practice, we select several typical fractal graphs to implement.

Koch snowflake

Koch snowflakes were first proposed by mathematician Helge von Koch and are one of the classic images in fractal geometry. Its generation is based on Koch curves, which are unilateral infinite fractals.

Take a look at the implementation first. Its base shape is an equilateral triangle. The area of the image is limited, but the perimeter is infinite. Each iteration increases the length of the line segment by one-third.

Train of thought

1. Koch Snowflake is composed of Koch curves. Its basic shape is a triangle. Each side of the triangle is divided into three equal parts.
2. Recursively perform step 1 in a recursive module until the set recursive level is reached.

Figure 4.	Figure 5

Code implementation

The first thing is to do the coordinate transformation again, move the origin of the coordinate from the top left to the bottom left, and flip the Y-axis to up.

 var ctx = canvas.getContext("2d");

      ctx.translate(0, canvas.height);

      ctx.scale(1, -1);
Copy the code

Then we find the three vertices of the triangle. Assuming we start with v1(100,100) and the length of the triangle is 100, we can obtain the other two vertices, v2 and V3 vectors by vector transformation.

 var ctx = canvas.getContext("2d");

      const v1 = new Vector(100.100);

      const v2 = new Vector(100.0).add(v1);

      const v3 = new Vector(100.0).rotate((60 * Math.PI) / 180).add(v1);
Copy the code

Then we perform recursive operations on the three edges, namely v1v2, V2v3 and V3V2 vectors respectively.

      koch(ctx, v1, v2.0, deep);

      koch(ctx, v2, v3.0, deep);

      koch(ctx, v3, v1.0, deep);
Copy the code

Function Koch (CTX, v1, v2, n, m) {}

This function takes five arguments: CTX is a Canvas2D context. V1 is the start vector of an edge, v2 is the end vector, n is the current iteration level, and m is the total number of iterations. In the module, according to the description in Figure 5, an edge is divided into four sections, each of which has the same length. You get v3, V4, v5. The termination condition is that the iteration level is the same as the specified number, and then the broken path of V1 ~ V5 is connected. This creates a Koch snowflake. Here’s the code.

function koch(ctx, v1, v2, n, m) { ctx.clearRect(0, 0, 300, 300); // Clean artboard before drawing const oneThirdVector = v2.copy ().sub(v1).scale(1/3); const v3 = oneThirdVector.copy().add(v1); const v4 = oneThirdVector.copy().scale(2).add(v1); const v5 = v4 .copy() .sub(v3) .rotate((-60 * Math.PI) / 180) .add(v3); n++; If (n === m) {// Stop recursion ctx.moveto (... v1); ctx.lineTo(... v3); ctx.lineTo(... v5); ctx.lineTo(... v4); ctx.lineTo(... v2); ctx.stroke(); return false; } // Recursively call Koch (CTX, v1, v3, n, m); koch(ctx, v3, v5, n, m); koch(ctx, v5, v4, n, m); koch(ctx, v4, v2, n, m); }Copy the code

Hexagonal snowflakes

Take a look at the implementation first. Its base shape is hexagonal. Each iteration takes 1/3 of the length of each line segment and draws the next small hexagon at the vertex of each corner. Repeat this step to get a hexagonal snowflake pattern.

Train of thought

1. First of all, according to the formation rule of hexagonal snowflakes mentioned in the basic chapter, each two adjacent sides are a group, the first side turns 60 degrees left, the second side turns 120 degrees right, perform 6 times to get the basic shape of hexagonal snowflakes.
2. Determine if the edge length is less than the specified minimum edge length before drawing the line. If not, change the length of the side to 1/3 of the original length and make a recursive call. If not, start drawing the hexagon.

Code implementation

Coordinate changes and getting the context of Canvas 2D are not covered here. First of all, let’s start from v0 and v1 and draw the pivot function of the hexagon.

const v0 = new Vector(50.200);

const v1 = new Vector(100.200);

hexagon(ctx, v0, v1);
Copy the code

Function hexagon(CTX, v0, v1) {}

This function takes five arguments: CTX is a Canvas2D context. V0v1 is the starting vector, which gives us a starting direction for our drawing. In Hexagon, we calculated the hexagonal edge length hexagonLen of the iteration, and iterated when the termination condition was not met.

  function hexagon(ctx, v0, v1) {

    const hexagonLen = v1.copy().sub(v0).vlength;

    if (hexagonLen > minLine) {
    // Enter the iteration}}Copy the code

Here we divide the hexagon into six cycles. Each loop is from vstart to vmiddle to vend.

// Hexagon (CTX, v0, v1)

let vstart = v1.copy();

let vmiddle = v1.copy().sub(v0);

let vend = new Vector();

for (let i = 0; i < 6; i++) {
// Hexagonal loop
}
Copy the code

In the body of the loop, we first get the vectors of vstart, vMIDDLE, vend in this iteration, and the next side length. If the new edge length is greater than the set minimum edge length minLine, the next iteration is done, otherwise, the three vectors are drawn. After drawing, update vstart and vmiddle.

  // Vector rotation

  vmiddle.rotate((60 * Math.PI) / 180).add(vstart);

  vend = vmiddle.copy().sub(vstart);

  vend.rotate((- 120. * Math.PI) / 180).add(vmiddle);

  const thirdv = vend
          .copy()
          .sub(vmiddle)
          .scale(1 / 3)
          .add(vmiddle);

  const newHexagonLen = thirdv.copy().sub(vmiddle).vlength;


  if (newHexagonLen > minLine) {

  / / recursion

      hexagon(ctx, vmiddle, thirdv);

  } else {

  / / drawingctx.beginPath(); ctx.moveTo(... vstart); ctx.lineTo(... vmiddle); ctx.lineTo(... vend); ctx.stroke(); } vstart = vend.copy(a); vmiddle = vend.copy().sub(vmiddle);
Copy the code

In this way, we have achieved the method of drawing hexagonal snowflakes.

Binary tree

Implementing a binary tree is much easier than Koch snowflakes and hexagonal snowflakes.

Train of thought

1. The first thing we need to know is the starting point and the length of the trunk.
2. In the recursion module, we cut both the length and width of the branch to 1/2 of that of the next level. And a fixed Angle of left and right offset. The termination condition is that the length of the branch is less than the specified minimum length. So you can draw a binary tree.

Code implementation

I’m not going to talk about the code here, but if you’re interested, you can click here to access the code.

conclusion

In the process of drawing fractal graphs, we reviewed the following knowledge points. First of all, we can meet the actual needs through coordinate transformation in Canvas, and reasonable coordinate changes can make our drawing logic easy to understand. Secondly, vector is a very convenient and basic tool in visualization. To master and learn to use vector thinking calculation is the only way to learn visualization. Finally, most of the fractal graphs are meta-images plus iterative methods. Practicing the drawing of fractal graphs also helps us to master various recursive operations and summarize the logical methods of such graphs.

reference

1. Canvas generates Koch snowflake (curve)
2. GitHub – akira- CN/Graphics: Some small examples related to graphics systems
3. Two dimensional rotation matrix and vector rotation
4. Code: Canvas Fenxing – CodeSandbox