Быстрая интерактивная схема зала на canvas

ky2yf4arjtfuilhixft4b3auuy8.png


Разрабатываем библиотеку для отображения больших интерактивных схем залов на canvas без фреймворков и заставляем хорошо работать в ie и мобильных устройствах. Попутно разбираемся с особенностями работы canvas.



Почему TypeScript?
Во-первых, мне хотелось попробовать. А во-вторых, полноценная поддержка ООП.
Да и строгая типизация, на мой взгляд, может уменьшить количество багов. А вообще я на PHP программирую, так что замечания по коду приветствуются.


Постановка задачи


Первым делом сформируем требования:


  • Производительность: 5–10 тысяч объектов не должны смущать нашу библиотеку даже в ie
  • На каждый объект можно навести курсор/кликнуть, и объект должен иметь возможность это обработать
  • Схема должна масштабироваться и двигаться
  • Адаптивность под размеры контейнера
  • Поддержка touch устройств

Введение


Не будем тянуть и сразу посмотрим демо, так будет понятнее о чем речь.
В статье я буду вставлять только небольшие участки кода, остальное можно посмотреть на 
GitHub


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

Постоянно перебирать все объекты на схеме и сверять их координаты не оптимально. Хотя это и будет происходить достаточно быстро, мы все равно сделаем лучше: построим деревья поиска, разбив карту на сектора.

Кроме оптимизации поиска, постараемся следовать следующим правилам работы с canvas:


requestAnimationFrame


У браузера есть свой таймер отрисовки, и с помощью метода requestAnimationFrame можно попросить браузер отрисовать наш кадр вместе с остальными анимациями, — это позволит избежать двойной работы браузера. Для отмены анимации есть cancelAnimationFrame. Полифил.


Кеширование сложных объектов


Не обязательно постоянно перерисовывать сложные объекты, если они не изменяются. Можно отрисовать их заранее на скрытом canvas, а потом брать оттуда.


Отрисовывать только видимые объекты


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


Перерисовывать только изменившиеся объекты


Нет смысла перерисовывать всю сцену, если изменился один элемент.


Меньше текста


Отрисовка текста для canvas тяжелая задача, поэтому нужно избегать большого количества
объектов с текстом. Даже если хочется на каждое место поставить цифру — лучше ограничить отображение этой цифры масштабом: например, показывать цифру только при определенном приближении, когда эта информация будет полезна.

Архитектура


htd3u8n2xggybhjcyrfrfhi0zf8.png


Scheme — основной класс.
View — класс знает canvas, на котором нужно рисовать, и его параметры (у нас их будет два).
SchemeObject — класс объекта схемы знает свое местоположение, как себя отрисовать и как обрабатывать события. Может содержать дополнительные параметры, например, цену.
EventManager — класс обработки и создания событий. При получении события передает его нужному классу.
ScrollManager — класс, отвечающий за скролл схемы.
ZoomManager — класс, отвечающий за зум схемы.
StorageManager — класс, отвечающий за хранение объектов схемы, создание дерева поиска и поиск объектов по координатам.
Polyfill — класс с набором поллифилов для кроссбраузерности.
Tools — класс с различными функциями, типа определения пересечения квадратов.
ImageStorage — класс создания канвасов для хранения изображений

Конфигурация


Очень хочется, чтобы у схемы были гибкие настройки. Для этого создадим такой нехитрый метод конфигурации объекта:


         /**
         * 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]);
                    }
                }
        }


Теперь можно конфигурировать объекты так:


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


Это удобно: нужно только создать сеттеры у объектов, которые могут не просто установить значение в свойство, но и свалидировать или изменить значение при необходимости.

Хранение и отображение объектов


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

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


d0sjeuqlou3x-9_wqhv4vu744-i.png

Код


TreeNode — класс узла дерева знает своего родителя, своих детей и координаты квадрата содержащихся в нем объектов:


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;
        }

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


Два метода, которые этим занимаются
        /**
         * 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();
        }

Теперь нам очень просто найти желаемые объекты как по квадрату, так и по координатам. Здесь уже есть поправки на скролл и зум, про них чуть ниже поговорим.

По координатам
        /**
         * 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;
        }

Про линии в 1 px
При попытке нарисовать линию в 1 px Вы можете получить неожиданный результат: она будет толщиной в два и полупрозрачная. Чтобы этого избежать, нужно сместить координаты на 0.5 px.
Подробное описание проблемы.

Еще мы можем легко определить, какие объекты лежат в зоне видимости и требуют отрисовки без перебора всех объектов:


Код
        /**
         * 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');
        }


Класс хранения и поиска объектов: src/managers/StorageManager.ts

Масштабирование


Зум — это просто. У canvas есть метод scale, который трансформирует сетку координат. Но нам нужно не просто зумить, нам нужно зумить в точку, в которой находится курсор или центр.


Для зума в точку нужно всего лишь знать две точки: старый центр зума (при старом масштабе) и новый, и добавить их разницу к смещению схемы:


Метод
         /**
         * 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
                );
            }
        }

Но мы же хотим поддерживать тач устройства, поэтому нужно обработать движение двух пальцев и запретить нативный зум:


Код
            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();
            });

В айфонах 6 и старше была найдена неприятная особенность: при быстром двойном касании возникал нативный зум с фокусом на канвасе, причем в таком режиме канвас начинал жутко тормозить. На viewport никакой реакции. Лечится так:


           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 раз больше начального масштаба и, при перемещении/зуме не рендерить объекты, а просто подставлять нашу картинку, пока разрешение карты не превысило разрешение снимка. А потом уже и оставшиеся реальные объекты будут быстро рисоваться в виду своего количества.


Но эта картинка тоже должна иногда меняться. Например, при выборе места оно меняет вид и мы не хотим, чтобы выбранные места исчезали на время перемещения схемы. Перерисовывать весь снимок (в n раз больше начального размера карты) при клике дорого,
, но в тоже время мы можем позволить себе на снимке не сильно заботиться о пересечении объектов и обновлять только квадрат, в котором находиться измененный объект.

Код
/**
         * 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;
        }

Таким вроде бы нехитрым способом мы очень сильно повысили скорость работы схемы.


Спасибо, что дочитали до конца. В процессе работы над схемой я подглядывал в исходники fabricjs и chartjs чтобы меньше велосипедить.

© Habrahabr.ru