Структура данных помогает нам хранить значения в наших данных и помогает нам эффективно выполнять операции с этими данными, если они нам нужны. Например, если мы хотим хранить одномерные точки данных, натуральные числа, которые вы будете отображать в одной строке или строке, мы можем использовать одномерный массив для хранения этих данных. Чтобы создать быстрое извлечение (поиск), мы будем использовать индексирование в естественном порядке (1 ‹2‹ 3) или с использованием такой структуры данных, как Trie или Binary Tree.

Что, если мы хотим работать с 2D-пространством и хранить наши данные для быстрого извлечения? Что, если мы собираемся найти порядок близости, например, найти все ближайшие точки, которые находятся рядом с этой точкой?

Индексирование в естественном порядке не будет работать, поскольку нам нужно иметь два разных индекса, один для точки X, а другой для точки Y, и мы должны искать все места, которые находятся в базе данных X + delta и Y + delta, и выполнять пересечение.

Нам нужно будет использовать пространственное индексирование.

Пространственное индексирование часто используется для эффективного доступа к 2D-пространству. Сценарии использования, использующие пространственную индексацию: приложение для совместного использования пассажиров (Lyft, Uber), служба доставки еды (Door dash), которая должна найти ближайшую доставку еды, Yelp хочет сообщить вам ближайший ресторан от вашего местоположения, нажмите обнаружение и многое другое.

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

Запрос диапазона: поиск объекта, содержащего заданную точку (точечный запрос) или перекрывающегося с интересующей областью (окно запроса).

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

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

Что такое QuadTree?

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

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

В этой статье я буду реализовывать квадродерево региона.

Прежде чем мы начнем, в QuadTree есть три компонента. Один из них - это точечный объект, который вам нужно сохранить. В этом случае мы можем делать x и y. Во-вторых, это QuadNode, который является узлом, который вы хотите удерживать внутри своего QuadTree. Наконец, само дерево.

Класс точки

Класс QuadNode

Класс QuadTree

Вставка

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

Затем мы вставляем точку в листовой узел дерева квадрантов и проверяем, нужно ли дереву квадрантов двигаться дальше subdivide. Если ему нужно продвинуть subdivide, мы subdivide разделим регион на четыре квадранта и перераспределим значение внутри его дочерним элементам.

Поиск

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

Заключение

  • Для сохранения геолокации последовательного поиска с естественным упорядочением недостаточно. Мы будем использовать пространственное индексирование для поиска 2D-пространства.
  • QuadTree похож на эквивалентную структуру данных для двоичного дерева в одномерном пространстве. Однако мы можем использовать QuadTree в любое время, когда у вас есть разреженные данные, которые нужно искать.

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

Вы можете подписаться на меня и подписаться на меня на Medium, чтобы увидеть больше подобных сообщений.