Fast interactive hall layout on canvas


    We are developing a library for displaying large interactive hall schemes on canvas without frameworks and making them work well in ie and mobile devices. Along the way, we deal with the features of canvas.


    Why TypeScript?
    Firstly, I wanted to try. And secondly, full support for OOP.
    Yes, and strict typing, in my opinion, can reduce the number of bugs. In general, I program in PHP, so comments on the code are welcome.

    Formulation of the problem


    First of all, we will formulate the requirements:


    • Performance: 5-10 thousand objects should not confuse our library even in ie
    • You can hover / click on each object, and the object must be able to process this
    • The circuit must scale and move.
    • Adaptability to container dimensions
    • Touch device support

    Introduction


    We will not pull and immediately see the demo , so it will be clearer what it is about.

    In the article I will insert only small sections of code, the rest can be viewed on
    GitHub

    We recall that canvas is essentially a picture with api, therefore, processing of hovers and clicks is on our conscience: we need to consider the coordinates ourselves, taking into account the scale and scroll, look for objects by their coordinates. But at the same time, we completely control the performance and draw only what we need.

    Constantly sorting out all the objects in the diagram and checking their coordinates is not optimal. Although this will happen rather quickly, we will still do better: we will build search trees by breaking the map into sectors.

    In addition to search optimization, we will try to follow the following rules for working with canvas:


    requestAnimationFrame


    The browser has its own rendering timer, and using the requestAnimationFrame method, you can ask the browser to draw our frame along with the rest of the animations, this will avoid the browser working twice. To cancel the animation there is cancelAnimationFrame . Polyphil .


    Caching Complex Objects


    It is not necessary to constantly redraw complex objects if they do not change. You can draw them in advance on a hidden canvas, and then take them from there.


    Draw only visible objects


    Even if an element extends beyond the borders of the canvas, it still takes time to render it.
    This is especially noticeable in ie, he honestly draws everything, while in chrome it is optimized, and much less time is spent on it.


    Redraw only changed objects


    It makes no sense to redraw the whole scene if one element has changed.


    Less text


    Drawing text for canvas is a difficult task, so you need to avoid a large number of
    objects with text. Even if you want to put a number in each place, it’s better to limit the display of this number to scale: for example, show the number only at a certain approximation, when this information will be useful.


    Architecture




    Scheme is the main class.
    View - the class knows the canvas on which to draw, and its parameters (we will have two of them).
    SchemeObject - the class of the schema object knows its location, how to draw itself and how to handle events. May contain additional parameters, for example, price.
    EventManager - a class for processing and creating events. When an event is received, passes it to the desired class.
    ScrollManager - the class responsible for scrolling the scheme.
    ZoomManager - the class responsible for the zoom scheme.
    StorageManager - a class that is responsible for storing schematic objects, creating a search tree and searching for objects by coordinates.
    Polyfill- A class with a set of polifil for cross-browser compatibility.
    Tools - a class with various functions, such as determining the intersection of squares.
    ImageStorage - a canvas creation class for storing images


    Configuration


    I really want the scheme to have flexible settings. To do this, create such a simple object configuration method:


             /**
             * Object configurator
             * @param obj
             * @param params
             */
            public static configure(obj: any, params: any)
            {
                    for (let paramName in params) {
                        let value = params[paramName];
                        let setter = 'set' + Tools.capitalizeFirstLetter(paramName);
                        if (typeof obj[setter] === 'function') {
                            obj[setter].apply(obj, [value]);
                        }
                    }
            }
    

    Now you can configure objects like this:


                    Tools.configure(this, params.options);
                    Tools.configure(this.scrollManager, params.scroll);
                    Tools.configure(this.zoomManager, params.zoom);
    

    This is convenient: you only need to create setters for objects that can not only set a value in a property, but also validate or change a value if necessary.


    Storage and display of objects


    First of all, you need to learn how to simply place objects on the diagram. But for this you need to understand what objects are now in sight. We agreed not to constantly sort through all the objects, but to build a search tree.


    To build a tree, you need to divide the hall scheme into parts, write one part to the left node of the tree, and the other to the right. The key of the node will be the rectangle bounding the area of ​​the circuit. Because the object represents a plane, not a point, it can appear at once in several nodes of a tree - it is not terrible. Question: how to break the circuit? To achieve maximum profit, the tree must be balanced, i.e. the number of elements in the nodes should be approximately the same. In our case, you can not particularly bother, because usually the objects in the diagram are located almost uniformly. Just divide in half alternately in width and height. Here is a partition for a tree with a depth of 8:




    The code


    TreeNode - the tree node class knows its parent, its children, and the coordinates of the square of the objects it contains:

    Treenode
        /**
         * Tree node
         */
        export class TreeNode {
            /**
             * Parent node
             */
            protected parent: TreeNode;
            /**
             * Children nodes
             */
            protected children: TreeNode[] = [];
            /**
             * Bounding rect of node
             */
            protected boundingRect: BoundingRect;
            /**
             * Objects in node
             */
            protected objects: SchemeObject[] = [];
            /**
             * Depth
             */
            protected depth: number;
            /**
             * Constructor
             * @param parent
             * @param boundingRect
             * @param objects
             * @param depth
             */
            constructor(parent: null | TreeNode, boundingRect: BoundingRect, objects: SchemeObject[], depth: number)
            {
                this.parent = parent;
                this.boundingRect = boundingRect;
                this.objects = objects;
                this.depth = depth;
            }
            /**
             * Add child
             * @param child
             */
            public addChild(child: TreeNode): void
            {
                this.children.push(child);
            }
            /**
             * Get objects
             * @returns {SchemeObject[]}
             */
            public getObjects(): SchemeObject[]
            {
                return this.objects;
            }
            /**
             * Get children
             * @returns {TreeNode[]}
             */
            public getChildren(): TreeNode[]
            {
                return this.children;
            }
            /**
             * Is last node
             * @returns {boolean}
             */
            public isLastNode(): boolean
            {
                return this.objects.length > 0;
            }
            /**
             * Get last children
             * @returns {TreeNode[]}
             */
            public getLastChildren(): TreeNode[]
            {
                let result: TreeNode[] = [];
                for (let childNode of this.children) {
                    if (childNode.isLastNode()) {
                        result.push(childNode);
                    } else {
                        let lastChildNodeChildren = childNode.getLastChildren();
                        for (let lastChildNodeChild of lastChildNodeChildren) {
                            result.push(lastChildNodeChild);
                        }
                    }
                }
                return result;
            }
            /**
             * Get child by coordinates
             * @param coordinates
             * @returns {TreeNode|null}
             */
            public getChildByCoordinates(coordinates: Coordinates): TreeNode | null
            {
                for (let childNode of this.children) {
                    if (Tools.pointInRect(coordinates, childNode.getBoundingRect())) {
                        return childNode;
                    }
                }
                return null;
            }
            /**
             * Get child by bounding rect
             * @param boundingRect
             * @returns {TreeNode[]}
             */
            public getChildrenByBoundingRect(boundingRect: BoundingRect): TreeNode[]
            {
                let result: TreeNode[] = [];
                for (let childNode of this.children) {
                    if (Tools.rectIntersectRect(childNode.getBoundingRect(), boundingRect)) {
                        result.push(childNode);
                    }
                }
                return result;
            }
            /**
             * Remove objects
             */
            public removeObjects(): void
            {
                this.objects = [];
            }
            /**
             * Get bounding rect
             * @returns {BoundingRect}
             */
            public getBoundingRect(): BoundingRect
            {
                return this.boundingRect;
            }
            /**
             * Get  depth
             * @returns {number}
             */
            public getDepth(): number
            {
                return this.depth;
            }
    


    Now you need to recursively create a tree, filling it with objects. It looks like this: we take the next node, if the depth is less than that set in the configs - we break the objects of this node along the dividing line and create two child nodes, place objects in them.

    Two methods that do this
            /**
             * Recursive explode node
             * @param node
             * @param depth
             */
            protected explodeTreeNodes(node: TreeNode, depth: number): void
            {
                this.explodeTreeNode(node);
                depth--;
                if (depth > 0) {
                    for (let childNode of node.getChildren()) {
                        this.explodeTreeNodes(childNode, depth);
                    }
                }
            }
            /**
             * Explode node to children
             * @param node
             */
            protected explodeTreeNode(node: TreeNode): void
            {
                let nodeBoundingRect = node.getBoundingRect();
                let newDepth = node.getDepth() + 1;
                let leftBoundingRect = Tools.clone(nodeBoundingRect) as BoundingRect;
                let rightBoundingRect = Tools.clone(nodeBoundingRect) as BoundingRect;
                /**
                 * Width or height explode
                 */
                if (newDepth % 2 == 1) {
                    let width = nodeBoundingRect.right - nodeBoundingRect.left;
                    let delta = width / 2;
                    leftBoundingRect.right = leftBoundingRect.right - delta;
                    rightBoundingRect.left = rightBoundingRect.left + delta;
                } else {
                    let height = nodeBoundingRect.bottom - nodeBoundingRect.top;
                    let delta = height / 2;
                    leftBoundingRect.bottom = leftBoundingRect.bottom - delta;
                    rightBoundingRect.top = rightBoundingRect.top + delta;
                }
                let leftNodeObjects = Tools.filterObjectsByBoundingRect(leftBoundingRect, node.getObjects());
                let rightNodeObjects = Tools.filterObjectsByBoundingRect(rightBoundingRect, node.getObjects());
                let leftNode = new TreeNode(node, leftBoundingRect, leftNodeObjects, newDepth);
                let rightNode = new TreeNode(node, rightBoundingRect, rightNodeObjects, newDepth);
                node.addChild(leftNode);
                node.addChild(rightNode);
                node.removeObjects();
            }
    


    Now it is very easy for us to find the desired objects both by square and by coordinates. There are already corrections for scroll and zoom, we’ll talk about them a little lower.


    By coordinates
            /**
             * Find node by coordinates
             * @param node
             * @param coordinates
             * @returns {TreeNode|null}
             */
            public findNodeByCoordinates(node: TreeNode, coordinates: Coordinates): TreeNode | null
            {
                let childNode = node.getChildByCoordinates(coordinates);
                if (!childNode) {
                    return null;
                }
                if (childNode.isLastNode()) {
                    return childNode;
                } else {
                    return this.findNodeByCoordinates(childNode, coordinates);
                }
            }
             /**
             * find objects by coordinates in tree
             * @param coordinates Coordinates
             * @returns {SchemeObject[]}
             */
            public findObjectsByCoordinates(coordinates: Coordinates): SchemeObject[]
            {
                let result: SchemeObject[] = [];
                // scale
                let x = coordinates.x;
                let y = coordinates.y;
                x = x / this.scheme.getZoomManager().getScale();
                y = y / this.scheme.getZoomManager().getScale();
                // scroll
                x = x - this.scheme.getScrollManager().getScrollLeft();
                y = y - this.scheme.getScrollManager().getScrollTop();
                // search node
                let rootNode = this.getTree();
                let node = this.findNodeByCoordinates(rootNode, {x: x, y: y});
                let nodeObjects: SchemeObject[] = [];
                if (node) {
                    nodeObjects = node.getObjects();
                }
                // search object in node
                for (let schemeObject of nodeObjects) {
                    let boundingRect = schemeObject.getBoundingRect();
                    if (Tools.pointInRect({x: x, y: y}, boundingRect)) {
                        result.push(schemeObject)
                    }
                }
                return result;
            }
    


    About lines in 1px
    When you try to draw a line in 1px, you may get an unexpected result: it will be two times thick and translucent. To avoid this, you need to shift the coordinates by 0.5px.
    Detailed description of the problem .

    We can also easily determine which objects lie in the visibility zone and require rendering without enumerating all the objects:


    The code
            /**
             * Render visible objects
             */
            protected renderAll(): void
            {
                if (this.renderingRequestId) {
                    this.cancelAnimationFrameApply(this.renderingRequestId);
                    this.renderingRequestId = 0;
                }
                this.eventManager.sendEvent('beforeRenderAll');
                this.clearContext();
                let scrollLeft = this.scrollManager.getScrollLeft();
                let scrollTop = this.scrollManager.getScrollTop();
                this.view.setScrollLeft(scrollLeft);
                this.view.setScrollTop(scrollTop);
                let width = this.getWidth() / this.zoomManager.getScale();
                let height = this.getHeight() / this.zoomManager.getScale();
                let leftOffset = -scrollLeft;
                let topOffset = -scrollTop;
                let nodes = this.storageManager.findNodesByBoundingRect(null, {
                    left: leftOffset,
                    top: topOffset,
                    right: leftOffset + width,
                    bottom: topOffset + height
                });
                for (let node of nodes) {
                    for (let schemeObject of node.getObjects()) {
                        schemeObject.render(this, this.view);
                    }
                }
                this.eventManager.sendEvent('afterRenderAll');
            }
    


    Object storage and search class: src / managers / StorageManager.ts


    Scaling


    Zoom is easy. Canvas has a scale method that transforms a grid of coordinates. But we need to not only zoom, we need to zoom to the point where the cursor or center is located.


    For zoom to a point, you only need to know two points: the old center of the zoom (at the old scale) and the new one, and add their difference to the offset of the scheme:


    Method
             /**
             * Zoom to point
             * @param point
             * @param delta
             */
            public zoomToPoint(point: Coordinates, delta: number): void
            {
                let prevScale = this.scheme.getZoomManager().getScale();
                let zoomed = this.scheme.getZoomManager().zoom(delta);
                if (zoomed) {
                    let newScale = this.scheme.getZoomManager().getScale();
                    let prevCenter: Coordinates = {
                        x: point.x / prevScale,
                        y: point.y / prevScale,
                    };
                    let newCenter: Coordinates = {
                        x: point.x / newScale,
                        y: point.y / newScale,
                    };
                    let leftOffsetDelta = newCenter.x - prevCenter.x;
                    let topOffsetDelta = newCenter.y - prevCenter.y;
                    this.scheme.getScrollManager().scroll(
                        this.scheme.getScrollManager().getScrollLeft() + leftOffsetDelta,
                        this.scheme.getScrollManager().getScrollTop() + topOffsetDelta
                    );
                }
            }
    


    But we want to support the device’s touch, so we need to handle the movement of two fingers and prohibit the native zoom:


    The code
                this.scheme.getCanvas().addEventListener('touchstart', (e: TouchEvent) => {
                    this.touchDistance = 0;
                    this.onMouseDown(e);
                });
                this.scheme.getCanvas().addEventListener('touchmove', (e: TouchEvent) => {
                    if (e.targetTouches.length == 1) {
                        // one finger - dragging
                        this.onMouseMove(e);
                    } else if (e.targetTouches.length == 2) {
                        // two finger - zoom
                        const p1 = e.targetTouches[0];
                        const p2 = e.targetTouches[1];
                        let distance = Math.sqrt(Math.pow(p2.pageX - p1.pageX, 2) + Math.pow(p2.pageY - p1.pageY, 2));
                        let delta = 0;
                        if(this.touchDistance) {
                            delta = distance - this.touchDistance;
                        }
                        this.touchDistance = distance;
                        if (delta) {
                            this.scheme.getZoomManager().zoomToPointer(e, delta / 5);
                        }
                    }
                    e.preventDefault();
                });
    


    In iPhones 6 and older, an unpleasant feature was found: with a quick double tap, a native zoom with focus on the canvas appeared, and in this mode, the canvas began to slow down terribly. There is no reaction to the viewport. It is treated like this:


               this.scheme.getCanvas().addEventListener('touchend', (e: TouchEvent) => {
                    // prevent double tap zoom
                    let now = (new Date()).getTime();
                    if (this.lastTouchEndTime && now - this.lastTouchEndTime <= 300) {
                        e.preventDefault();
                    } else {
                        this.onMouseUp(e);
                    }
                    this.lastTouchEndTime = now;
                });
    

    Класс, отвечающий за масштабирование: src/managers/ZoomManager.ts


    Перемещение схемы


    Я решил просто прибавлять к координатам смещение слева и сверху.
    Правда есть метод translate, который смещает сетку координат. На момент разработки он показался мне не очень удобным, но, возможно, я им еще воспользуюсь. Но это все мелочи, больше всего нас интересуют вопросы обработки событий.


    Некоторые люди при клике могут немного смещать курсор, это мы должны учесть:


    Код
            /**
             * Mouse down
             * @param e
             */
            protected onMouseDown(e: MouseEvent | TouchEvent): void
            {
                this.leftButtonDown = true;
                this.setLastClientPositionFromEvent(e);
            }
            /**
             * Mouse up
             * @param e
             */
            protected onMouseUp(e: MouseEvent | TouchEvent): void
            {
                this.leftButtonDown = false;
                this.setLastClientPositionFromEvent(e);
                if (this.isDragging) {
                    this.scheme.setCursorStyle(this.scheme.getDefaultCursorStyle());
                    this.scheme.requestRenderAll();
                }
                // defer for prevent trigger click on mouseUp
                setTimeout(() => {this.isDragging = false; }, 10);
            }
            /**
             * On mouse move
             * @param e
             */
            protected onMouseMove(e: MouseEvent | TouchEvent): void
            {
                if (this.leftButtonDown) {
                    let newCoordinates = this.getCoordinatesFromEvent(e);
                    let deltaX = Math.abs(newCoordinates.x - this.getLastClientX());
                    let deltaY = Math.abs(newCoordinates.y - this.getLastClientY());
                    // 1 - is click with offset
                    if (deltaX > 1 || deltaY > 1) {
                        this.isDragging = true;
                        this.scheme.setCursorStyle('move');
                    }
                }
                if (!this.isDragging) {
                    this.handleHover(e);
                } else {
                    this.scheme.getScrollManager().handleDragging(e);
                }
            }
            /**
             * Handle dragging
             * @param e
             */
            public handleDragging(e: MouseEvent | TouchEvent): void
            {
                let lastClientX = this.scheme.getEventManager().getLastClientX();
                let lastClientY = this.scheme.getEventManager().getLastClientY();
                this.scheme.getEventManager().setLastClientPositionFromEvent(e);
                let leftCenterOffset =  this.scheme.getEventManager().getLastClientX() - lastClientX;
                let topCenterOffset =  this.scheme.getEventManager().getLastClientY() - lastClientY;
                // scale
                leftCenterOffset = leftCenterOffset / this.scheme.getZoomManager().getScale();
                topCenterOffset = topCenterOffset / this.scheme.getZoomManager().getScale();
                let scrollLeft = leftCenterOffset + this.getScrollLeft();
                let scrollTop = topCenterOffset + this.getScrollTop();
                this.scroll(scrollLeft, scrollTop);
            }
    


    Класс, отвечающий за скролл: src/managers/ScrollManager.ts


    Оптимизация


    Вот вроде бы уже есть рабочий вариант схемы, но нас ждет неприятный сюрприз:
    наша схема сейчас быстро работает только в хроме. Проблема в том, что при перемещении схемы в полном размере и зуме из этого полного размера, перерисовываются все объекты. А когда уже в масштабе помещается только часть объектов — работает нормально.


    Сначала я хотел объединить ближайшие места в кластеры, чтобы место сотни объектов рисовать один при мелком масштабе. Но не смог найти/придумать алгоритм, который бы делал это за разумное время и был бы устойчивым, т.к. объекты на карте могут быть расположены как угодно.


    Потом я вспомнил правило, которое написано на каждом заборе (и в начале этой статьи) при работе с canvas: не перерисовывать неизменяющиеся части. Действительно, при перемещении и зуме сама схема не изменяется, поэтому нам нужно просто иметь «снимок» схемы в n раз больше начального масштаба и, при перемещении/зуме не рендерить объекты, а просто подставлять нашу картинку, пока разрешение карты не превысило разрешение снимка. А потом уже и оставшиеся реальные объекты будут быстро рисоваться в виду своего количества.


    But this picture should also sometimes change. For example, when choosing a place, it changes its appearance and we do not want the selected places to disappear during the movement of the scheme. Redrawing the entire image (n times the initial size of the map) during a click is expensive,
    but at the same time we can afford to not really care about the intersection of objects in the image and update only the square in which the changed object is located.


    The code
    /**
             * Update scheme cache
             * @param onlyChanged
             */
            public updateCache(onlyChanged: boolean): void
            {
                if (!this.cacheView) {
                    let storage = this.storageManager.getImageStorage('scheme-cache');
                    this.cacheView = new View(storage.getCanvas());
                }
                if (onlyChanged) {
                    for (let schemeObject of this.changedObjects) {
                        schemeObject.clear(this, this.cacheView);
                        schemeObject.render(this, this.cacheView);
                    }
                } else {
                    let boundingRect = this.storageManager.getObjectsBoundingRect();
                    let scale = (1 / this.zoomManager.getScaleWithAllObjects()) * this.cacheSchemeRatio;
                    let rectWidth = boundingRect.right * scale;
                    let rectHeight = boundingRect.bottom * scale;
                    this.cacheView.setDimensions({
                        width: rectWidth,
                        height: rectHeight
                    });
                    this.cacheView.getContext().scale(scale, scale);
                    for (let schemeObject of this.getObjects()) {
                        schemeObject.render(this, this.cacheView);
                    }
                }
                this.changedObjects = [];
            }
             /**
             * Draw from cache
             */
            public drawFromCache()
            {
                if (!this.cacheView) {
                    return false;
                }
                if (this.renderingRequestId) {
                    this.cancelAnimationFrameApply(this.renderingRequestId);
                    this.renderingRequestId = 0;
                }
                this.clearContext();
                let boundingRect = this.storageManager.getObjectsBoundingRect();
                let rectWidth = boundingRect.right;
                let rectHeight = boundingRect.bottom;
                this.view.getContext().drawImage(
                    this.cacheView.getCanvas(),
                    this.getScrollManager().getScrollLeft(),
                    this.getScrollManager().getScrollTop(),
                    rectWidth,
                    rectHeight
                );
            }
            /**
             * Request draw from cache
             * @returns {Scheme}
             */
            public requestDrawFromCache(): this
            {
                if (!this.renderingRequestId) {
                    this.renderingRequestId = this.requestFrameAnimationApply(() => { this.drawFromCache(); });
                }
                return this;
            }
    


    In a seemingly simple way, we greatly increased the speed of the circuit.


    Thank you for reading to the end. In the process of working on the circuit, I peeked at the sources of fabricjs and chartjs to cycle less.


    Also popular now: