How to draw a movable grid using Canvas?

The effect

instructions

This was a requirement encountered in a real project, and I pulled it out of the way, masking the business-related stuff, and just looking at it from a code perspective. First, the mesh size is configurable and each vertex can be moved. See this problem, do not know everybody is how to think. Let’s start with my own thinking.

Analysis of the

First, you need to have a starting point, so that you can determine where the grid is, and then you need to know how long each square in the grid is, and then you need to move the edges as each vertex moves.

So there are really only two types of objects to store, lines and vertices.

How do you store vertices and lines? We use a library called fabric.js, which makes it easy to create vertices and edges, and it also provides a way to move edges. However, problems also occur: as shown above, a point is associated with at most four edges, and at least two edges.

The first idea is to use an array to store vertices and lines, and then determine whether the line is connected to a vertex based on the vertex coordinates contained in the line. If so, it will be added to the associated properties of the vertex. Later when moving the vertex, according to the vertex to get its associated line, to dynamically change the coordinates of the line, so that can achieve the above effect.

implementation

Based on the above analysis, let’s implement the code. The first objects that need to be stored are vertices and edges. It is then easy to calculate all vertex coordinates based on the starting point coordinates and the side lengths of each small rectangle.

function Grid({node, unit, row, col, matrix = []}) {

    // Store vertices

    this.vertexes = [];

    / / store

    this.lines = [];

    

    // Calculate according to the starting coordinates and the unit side length

    for (let i = 0; i <= row; i++) {

        for (let j = 0; j <= col; j++) {

            const newVertex = makeRect(node.x + i * unit, node.y + j * unit);

            this.vertexes.push(newVertex);

        }

    }

    

    // Add event listeners for vertex objects

    this.addListener();

}

Copy the code

So and how to calculate, tectonic boundary, need only two vertices can be together, so we can choose to traverse the vertices to construct the edge, but it can lead to duplicate edge, and we only need an edge is ok, or moving, you will find that moving out, the following also shows a overlapping edges. Of course, in fact, the most important reason is the efficiency problem. If we do not reduce the weight, it will lead to too high time complexity of calculation.

There are two ways to do this, one is to mark the vertices, the vertices on both ends of the current line are already marked, then skip the current round of traversal. Another way is to obtain edges based on the specific shape of the grid, as shown in the figure below, which calculates the horizontal and vertical edges in two different colors.

In this case, the horizontal direction, two of each row to form an edge, and the vertical direction, according to a certain interval between the two vertices to form an edge. This method is used because the format that needs to be passed to the algorithm is a two-dimensional array.

/ /... omitted



// Construct the matrix

this.matrix = [];

let index = - 1;

for (let i = 0; i < this.vertexes.length; i++) {

    if (i % (col + 1) = = =0) {

        index++;

        this.matrix[index] = [];

    }

    this.matrix[index].push(this.vertexes[i]);

}



// Add edges according to the matrix

let idx = 0;

for (let i = 0; i < this.matrix.length; i++) {

    for (let j = 0; j < this.matrix[i].length; j++) {

        // Cross render edges so that they can be shown first in the viewable area

        this.matrix[i][j+1] && this.makeLine(this.matrix[i][j], this.matrix[i][j+1]);

        this.vertexes[idx + col + 1] &&

            this.makeLine(this.vertexes[idx], this.vertexes[idx + col + 1]);

        idx++;

    }

}

Copy the code

And then I’m going to find out how many edges are associated with each vertex

for (let i = 0; i < this.vertexes.length; i++) {

  const vertex = this.vertexes[i];

  // Determine whether a vertex is associated with an edge based on whether the vertex's coordinates are the starting or ending coordinates of both ends of the edge

  const associateLines = this.lines.filter(item= > {

    return (item.x1 === vertex.left && item.y1 === vertex.top) ||

      (item.x2 === vertext.left && item.y2 === vertex.top);

  });

  vertex.lines = associateLines;

}

Copy the code

For those of you who have eye trouble, you can tell at a glance that the time complexity is too high. So although grid draw out, but when the vertex number too much computation time is too long, cause sticking up almost 2 s, browser when horizontal has 50 points, vertical direction has 50 points, can clearly see the browser’s card, at this time if there is a interactive UI input box, is unable to do any action, there is no drop.

To improve the

So what’s an efficient way to find relationships between vertices and edges? I don’t want to keep you in suspense. There may be other, better ways, but my knowledge is limited.

Solution is to figure this kind of structure, because the figure edge can use adjacency list or the adjacency matrix to store, so if I stored a vertex, then the edge associated with the vertices are defined, that is to say, we are adding vertex, just by the way can solve the problem of the vertex of the association, no longer need to traverse all come to the edge of relevance. (The graph data structure will not be introduced in detail here, interested students can find their own information, the actual use of the graph here is the association between the edge and the vertex, other graph traversal are not used)

Let’s improve our code.

function Grid({node, unit, row, col, matrix = []}) {

    this.vertexes = [];

    this.lines = [];

    this.edges = new Map(a);



    this.addEdges = addEdges;

    this.addVertexes = addVertexes;

}

Copy the code

A new property, edges, has been added to store the mapping between edges and vertices. The other steps are the same as before, except that the method of adding vertices and edges is changed.

function Grid({node, unit, row, col, matrix = []}) {

    / /... omit



    // Add edges according to the matrix

    let idx = 0;

    for (let i = 0; i < this.matrix.length; i++) {

        for (let j = 0; j < this.matrix[i].length; j++) {

            // Cross render edges so that they can be shown first in the viewable area

            this.matrix[i][j+1] && this.addEdges(this.matrix[i][j], this.matrix[i][j+1]);

            this.vertexes[idx + col + 1] &&

                this.addEdges(this.vertexes[idx], this.vertexes[idx + col + 1]);

            idx++;

        }

    }



    // Associate edges to vertices

    this.edges.forEach((value, key) = > {

        key.lines = value;

    });

}

Copy the code

Here we reduce the O(mn) computation to O(n), where M is the length of lines and n is the length of Vertexes. And then let’s see if I can calculate 100 by 100 vertices in 200ms, which is good enough for me. So how does the graph implement this association? In fact, every time an edge is added, two vertices of the edge are added to the association, which is the structure of the Map.

function addEdges(v, w) {

    const line = makeLine({point1: v, point2: w});

    // Vertex V is associated with edge line

    this.edges.get(v).push(line);

    // Vertex w is also associated with edge line

    this.edges.get(w).push(line);

    this.lines.push(line);

}



function addVertexes(v) {

    this.vertexes.push(v);

    // Set a Map structure for each vertex

    this.edges.set(v, []);

}

Copy the code

After all the vertices are computed, the edges associated with the actual vertices are determined, and you only need to iterate over the edges.

Once that’s done, we can happily call the Fabric API and add these objects to the Canvas.

// Fabric API to add fabric objects to canvas

canvas.add(... this.vertexes);

canvas.add(... this.lines);

Copy the code

All right, we’re done. We’re ready to go. Run the page, open it up and look, boy, the computation is much faster, but the rendering speed is terrible, the number of vertices is 30*30, the page is still stuck, what’s going on?

When you think about it, adding so many objects to the canvas is a lot of computation, but there’s nothing you can do to change the rendering cost. A compromise was to use time slicing. In short, the requestAnimationFrame API was used to split the rendering task into fragments that would be rendered when the browser was idle so that it would not block other browsers’ tasks. Here’s a look at some browser rendering.

function renderIdleCallback(canvas) {

    // Task slice

    const points = this.points.slice();

    const lines = this.lines.slice();

    const task = (a)= > {

        // Break the render while cleaning the canvas

        if (this.interrupt) return;

        if(! points.length && ! lines.length)return;

        let slicePoint = [], sliceLine = [];

        for (let i = 0; i < 10; i++) {

            if (points.length) {

                const top = points.shift();

                slicePoint.push(top);

            }

            if (lines.length) {

                const top = lines.shift();

                sliceLine.push(top);

            }

        }

canvas.add(... slicePoint);

canvas.add(... sliceLine);

        window.requestAnimationFrame(task);

    }

    task();

}

Copy the code

The above code adds an identifier to interrupt the rendering, because there is a situation where the mesh is cleaned up and re-rendered before it has finished rendering, and the previous rendering needs to be stopped and a new rendering needs to be started.

conclusion

Well, that’s the end of it. Because the author’s knowledge is shallow, can only achieve this kind of optimization to meet the demand, the more extreme optimization will see you big guy guidance. At the same time, this attempt is the first time for the author to combine the data structure and optimization methods he has learned into the project, which gives me a great sense of accomplishment and also makes me feel the importance of data structure algorithm for programmers. If I want to break through my own technical bottleneck, this is also an unavoidable point.