Как повысить производительность редактора маршрута с помощью дерева квадрантов

Нина Фурсова

разработчик в компании Axmor

Дерево квадрантов — это древовидная структура данных, которая позволяет разбивать 2d-пространство и быстро искать пересечения объектов. Активно используется в областях, где есть динамический контекст, например, в геймдеве или в приложениях с геоиндексацией, в которых требуется следить за движущимся объектом, назначать и редактировать маршруты.

Мы в Axmor занимаемся разработкой ИТ-решений на заказ, в том числе создаем системы для автоматизации бизнес-процессов в судоходстве. В данной статье мы расскажем, как применили дерево квадрантов при разработке одного из приложений для заказчика, который работает в сфере речного судоходства. Оно прокладывает маршрут на карте для речного грузового транспорта, и, естественно, от оптимальности этого маршрута и скорости работы приложения зависит рентабельность бизнеса. При выполнении задачи остро стоял вопрос производительности: обработка пересечений занимала много времени и делала инструмент медленным. Мы применили дерево квадрантов и решили проблему производительности, но, забегая вперед, советуем не ждать, пока она возникнет, а использовать дерево сразу.

Описание решаемой задачи

Имеется судовой ход, который представляет из себя набор ломаных без ветвлений.

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

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

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

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

Когда редактирование завершено, короткие отрезки обратно склеиваются в максимально длинные ломаные, соединяющие так называемые «особые» точки: граничные точки, точки ветвлений и точки, примыкающие к геозонам.

При изменении модели (добавлении, удалении точки/отрезка и т.п) необходимо пересчитывать пересечения отрезков, примыкание к геозонам и обновлять свойства точек и модели, хранить информацию, какие участки добавились/обновились/изменились.

На начальном этапе, когда судовой ход не проложен и точек мало, все вычисления простым перебором занимают доли секунд. Но по мере того, как большая часть судового хода была проложена, сразу возник вопрос производительности. В какой-то момент начальная загрузка данных стала занимать 20-40 секунд, а на одно простое действие пользователя, такое как соединить 2 точки, требовалось около 8 секунд. Отклик системы стал неприемлемо большим даже для самого терпеливого пользователя. Надо было срочно ее оптимизировать.

Основная идея — это ограничить область пересчетов. Так, например, когда добавляется точка, чтобы найти, около какой геозоны она расположена, нужно перебирать не все геозоны, а только те, которые расположены вблизи этой точки. То есть заранее можно уменьшить список объектов, на котором будут применяться уже более «тяжелые» вычисления.

Для ограничения области пересчета и ускорения подсчетов были использованы следующие алгоритмы.

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

Дерево квадрантов заполняется элементами модели (точками, отрезками и геозонами) и затем используется для поиска объектов в ограниченной области. Например, по точке определяются расположенные рядом геозоны и отрезки. Или по отрезку определяются расположенные рядом другие отрезки, и т.п.

Уже на этом этапе для модели судового хода из ~2500 точек, ~2500 отрезков, 180 геозон, количество перебираемых объектов существенно сократилось (от 2 до 40 в зависимости от типа объекта).

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

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

Применение этих двух методов позволило значительно ускорить вычисления и существенно сократить отклик на действие пользователя. В результате все расчеты для формирования данных стали занимать меньше минуты, обработка действий пользователя — меньше 200 миллисекунд.

Доступные действия пользователя

В упрощении судовой ход состоит из отрезков. Модель — из отрезков и точек (концов этих отрезков).

Для построения судового хода пользователю доступны следующие операции:

Добавление точки

Если пользователь кликает мышкой на свободное место, создается новая активная точка.

При этом, если пользователь кликает на существующую точку, она становится активной.

Если пользователь кликает на участок отрезка, за исключением концевых, отрезок разбивается этой точкой на два отрезка.

Добавление отрезка (последовательное добавление точек)

Если при выбранной активной точке создается новая точка, эти две точки соединяются отрезком. Таким образом добавляется новый отрезок. При этом все новые пересечения этого отрезка с остальными создают новые точки.

Удаление точки

Если есть активная точка, к которой примыкают 1 или 2 отрезка, то для нее доступна операция удаления. При этом, если точка концевая — с ней удаляется и отрезок. Если точка соединяла 2 отрезка, то после ее удаления вместо двух отрезков остается один.

Удаление отрезка

Есть возможность выбрать отрезок и удалить его. При этом, если отрезок был частью ломаной, ломаная разрывается.

Перемещение точки и примыкающих к ней отрезков с помощью операции drag-and-drop

При перетаскивании активной точки с помощью операции drag-and-drop все примыкающие к этой точке отрезки изменяют свое расположение, вследствие чего могут возникнуть новые пересечения. Поэтому опять же ищутся новые пересечения, и для каждого из них добавляется объект точки.

В случае, когда точка перемещается на место другой точки, происходит объединение двух точек в одну и, если один накладывается на другой, происходит объединение отрезков.

Описание модели

В очень упрощенном виде модель судового хода состоит из точек и отрезков, соединяющих две точки.

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

В зависимости от количества отрезков, исходящих из точки, точка классифицируется по типу, и логика операций с ней может отличаться.

Типы точек

Одиночная (single point)

Точка не является концом какого-либо отрезка. На карте это активная точка, которую еще не соединили с другой точкой отрезком. Доступные операции: удаление, перемещение.

Концевая (end point)

Точка является концом ровно одного отрезка. Доступные операции: удаление, перемещение. При удалении такой точки удаляется также примыкающий к ней отрезок.

Промежуточная (middle point)

Точка является концом ровно двух отрезков. Доступные операции: удаление, перемещение. При удалении такой точки из двух отрезков получается один отрезок.

Точка ветвления (branch point)

Точка является концом трех и более отрезков. Доступные операции: перемещение. Удаление такой точки не предусмотрено, так как неочевиден результат такого действия.

Расчеты системы

При подготовке системы происходит разбиение ломаных на отрезки. Далее основные вычисления производятся с полученными отрезками и точками, а также геозонами, известными заранее.

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

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

Особенности вычислений

Так при клике на карту практически невозможно точно попасть в координату, почти везде совпадение точек подразумевает примерное совпадение. То есть, если две точки «достаточно близки», то считаем, что они совпадают. Если точка «достаточно близка» к прямой, то считаем, что она лежит на прямой. Для этого вводится некоторая условная величина delta, и понятие объекты «достаточно близки» означает, что расстояние между ними меньше delta.

Если при пересечении получаются «достаточно близкие» точки, то они склеиваются в одну точку. Края новых отрезков соответственно смещаются за точкой.

При перемещении точек пользователем с помощью операции drag-and-drop, либо при слиянии точек, нужно проверять отрезки с одинаковыми (или почти одинаковыми) координатами и отсеивать дубликаты.

Если этого не делать, то при многократном пересечении отрезков количество новых точек в одном месте начинает бесконтрольно расти.

Таким образом, основная и самая частая операция – сравнение новых и измененных элементов модели с остальными, расположенных достаточно близко.

Для сужения множества перебираемых объектов было выбрано дерево квадрантов, которое дает быстрый доступ к таким объектам.

Применение дерева квадрантов

Дерево квадрантов используется для быстрого доступа к объектам, расположенным в определенной области пространства. Каждый лист дерева рекурсивно разбивается на 4 квадранта, субквадранты и так далее. Таким образом образуется система вложенных областей пространства (в простом случае — прямоугольников или квадратов). Каждый лист дерева соответствует определённой области пространства. У каждого узла дерева либо 4 потомка, либо их нет.

Элементы данного дерева заполняются объектами модели: отрезками, точками, полигонами.

Ниже и далее схематично приведен вид используемого дерева.

			class QuadTree {

  // Константа — количество элементов, которые можно хранить в одном узле
  // Ограничивающий параллелепипед, выровненный по координатным осям,
  // показывает границы дерева

  boundary: AABB;
  parent: QuadTree;  // Указатель на родительский элемент
  level: number;  // Глубина или уровень дерева

  points;  // Точки
  segments;  // Отрезки
  polygons;  // Геозоны

  // Указатели на дочерние узлы дерева

  northWest: QuadTree;
  northEast: QuadTree;
  southWest: QuadTree;
  southEast: QuadTree;
}
		

Добавление отрезка в дерево квадрантов

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

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

			public insert(segment): boolean {
  // Возвращает false если объекты не принадлежит дереву
  if (!this.boundary.contains(segment))
	return false; // Объект не может быть добавлен

  // Далее разделяем область и проверяем, можем ли добавить отрезок в какой-либо узел
  if (this.northWest == null) {
  // … инициализируем дочерние элементы
}

  if (this.northWest.insert(segment)) return true;
  if (this.northEast.insert(segment)) return true;
  if (this.southWest.insert(segment)) return true;
  if (this.southEast.insert(segment)) return true;

  // Не получилось вставить в дочерний элемент - вставляем в этот
  this.segments.push(segment);
  // … инициализируем вспомогательные свойства объекта
  return true;
}
		

Добавление полигона в дерево квадрантов

Рекурсивно ищется лист квадродерева наименьшего размера, содержащий в себе полигон.

С учетом того, что требуется искать не точные пересечения, ищется такой лист дерева, в котором полигон не примыкает к границам, а находится на некотором расстоянии delta от границ.

Таким образом, ищется такой лист дерева, в котором полигон содержится полностью и находится на расстоянии от границ не меньше заданного delta, но ни один из его дочерних элементов не удовлетворяет этому условию.

Схема аналогична вставке отрезка в дерево.

Добавление точки в дерево квадрантов

Аналогично вставке полигонов, в случае точек ищется лист квадродерева, содержащий в себе точку, и в котором точка располагается от границ листа на расстоянии не меньше delta.

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

•  количество точек в листе дерева не должно превышать заданного порога NODE_CAPACITY. В текущем решении максимальное количество точек, которое вмещает лист дерева = 4.
•  уровень листа в дереве ограничен снизу MIN_LEVEL. Точки вставляются в дерево, начиная с этого уровня. Для нижней границы использовалось значение MIN_LEVEL = 12.

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

•  уровень листа в дереве ограничен сверху MAX_LEVEL.  Использовалось значение MAX_LEVEL = 100, это ограничение выбрано сильно с запасом, и в выполняемой задаче практически не достигалось. Это условие может противоречить первому условию, но оно считается более приоритетным.

Таким образом, условие вставки точки в дерево выглядит следующим образом:

			If (this.level > MAX_LEVEL || (this.level
> MIN_LEVEL && this.points.length < NODE_CAPACITY))
{
   // … вставить точку в дерево (insert point to this)
}
		

Нахождение объектов в заданной области

Задача нахождения пересечений объектов (отрезков, точек, геозон или их комбинаций), или объектов, расположенных близко друг к другу, на первом этапе сводится к задаче пересечения листов квадродерева, в которых находятся объекты.

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

Применение необходимого условия пересечения проекций

Необходимое условие пересечения следует из того, что если два объекта на плоскости пересекаются, то пересекаются и их проекции на оси координат. Это справедливо для отрезков, для точек и полигонов.

Отсюда следует, что если проекции двух фигур не пересекаются, то и сами фигуры не пересекаются.

Таким образом, для поиска пересечений точек, отрезков, полигонов и их комбинаций проверяется, пересекаются ли их проекции. Если не пересекаются — объект исключается из результата запроса.

Так как при решении задачи требуется не точное пересечение, то и для проекций применяется то же условие: ищется пересечение проекций, увеличенных с двух сторон на delta.

Пусть [A’, B’] и [A” B”] — проекции первой фигуры (отрезка, точки или полигона) на оси координат, [C’, D’] и [C’’, D’’] — проекции второй фигуры на оси координат.

Тогда условие будет выглядеть следующим образом:

			// пересечение проекций на первую ось координат
(A' - delta <= D' + delta) && (B' + delta >= C' – delta) &&

  // пересечение проекций на вторую ось координат
(A'' - delta <= D'' + delta) && (B'' + delta >= C'' – delta);
		

Метрики

Веб-приложение было написано на языке JavaScript с использованием Angular 6 + TypeScript.

Для отображения карт и элементов судового хода использовался Mapbox GL JS , для взаимодействия пользователя с картой и редактирования элементов судового хода — mapbox-gl-draw. Также для вычислений пересечений использовалась Turf.js — вспомогательная JavaScript-библиотека для работы с геообъектами.

На момент снятия метрик использовался построенный на тот момент судовой ход, который состоял примерно и 2596 отрезков и 2549 точек.

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

Ниже на диаграмме приведены времена выполнения операций, с входящими данными 725, 1291 и 2596 отрезков для четырех случаев: когда используется простой перебор, только дерево квадрантов, только условие пересечения проекций и дерево квадрантов с последующим применением необходимого условия пересечений проекций. Цифры носят примерный характер, тем не менее хорошо иллюстрируют эффективность примененных алгоритмов.

Для используемых алгоритмов приводится среднее время загрузки данных и среднее время, требуемое на выполнение одной атомарной операции, такой, как добавление/перемещение/удаление точки или отрезка.

Ниже в таблицах дополнительно к средним временам добавлены среднее количество отрезков, возвращаемых для заданного отрезка после применения алгоритма, и среднее количество точек, возвращаемое для заданного отрезка после применения алгоритма.

1. Входные данные — 725 отрезков, 770 точек, 146 геозон.

Максимальные уровень листа (глубина) дерева=18, максимальное количество отрезков в листе=5, максимальное количество точек в листе=8.

2. Входные данные – 1291 отрезков, 1336 точек, 146 геозон.

Максимальные уровень листа (глубина) дерева=19, максимальное количество отрезков в листе=6, максимальное количество точек в листе=8.

3. Входные данные — 2596 отрезков, 2549 точек, 146 геозон.

Максимальные уровень листа (глубина) дерева=19, максимальное количество отрезков в листе=8, максимальное количество точек в листе=10.

Графическое представление данных таблиц:

Выводы

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

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

Применение дополнительно необходимого условия пересечения проекций помогает отбросить те мелкие объекты, которые расположены на границах квадрантов и попадают почти во все запросы. При конфигурации точек и отрезков для судового хода в результате остается в среднем 2-8 объектов, с которыми производятся более точные вычисления.

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