QuadTree для поиска объектов на карте: ускорение тапов в 40 раз

Андрей Отинов -

Вы разрабатываете мобильное приложение с картой, где пользователи могут нажимать на облака, чтобы открыть чат. На карте может быть тысяча точек, и каждый тап должен быстро находить ближайший объект.
В статье описывается, как использовать QuadTree и сферическую геометрию, чтобы обрабатывать тап за O(log n) вместо O(n).
Это позволяет уменьшить задержку и улучшить FPS, особенно при активном перемещении карты.
Перед тем как внедрить, проверьте: сколько точек у вас, используете ли вы GL‑слои, нужна ли интерактивная аннотация, и как рассчитывается расстояние между координатами.

Источник: Habr

Проблема с обработкой тысяч точек

Когда на карте живёт сотня объектов, линейный перебор работает быстро:

func cloud(at tap: CLLocationCoordinate2D) -> Cloud? {
    return allClouds
        .filter { $0.coordinate.distance(to: tap) < someRadius }
        .min { $0.coordinate.distance(to: tap) < $1.coordinate.distance(to: tap) }
}

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

Почему QuadTree помогает

QuadTree – это дерево, которое разбивает карту на квадраты.
Каждый узел хранит до 10 точек; при превышении лимита узел делится на четыре дочерних квадранта.
При поиске объекта обходим только те ветки, которые пересекаются с запросом, остальные сразу отбрасываем.
Таким образом, поиск занимает O(log n), а не O(n), и нагрузка на CPU падает.

Реализация на Swift

Код на Swift выглядит так:

private let MaxItemsInSquare = 10

func add(item: QuadItem) -> Node {
    // Если у узла уже есть дети — спускаемся глубже
    if !node.children.isEmpty {
        // ...
    }
}

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

Сферическая геометрия и расчёт расстояний

Расстояние между двумя координатами на Земле вычисляется по формуле Хаверсина, учитывая сферу планеты.
Это важно, потому что простая формула sqrt(dx² + dy²) приводит к ошибкам при больших масштабах.
В коде используется метод distance(to:), который применяет тригонометрию и возвращает точное расстояние в метрах.

Тестирование и проверка

Шаг Что проверить Как проверить Кому полезно
1 Количество точек Считайте allClouds.count Разработчик
2 Производительность Запустите профайлер, измерьте FPS Менеджер
3 Корректность расстояния Сравните с ручным расчётом QA
4 Граничные случаи Тестируйте объекты в полюсе и на антимеридиане Тестировщик
5 Интерактивность Проверьте, что hitTest возвращает правильный объект UX

Что может пойти не так

  • Неверный лимит: если MaxItemsInSquare слишком велик, узел будет содержать много точек, и поиск станет медленным.
  • Проблемы с GL‑слоями: если облака не являются интерактивными, MapBox отдаёт только координаты, и вам нужно самостоятельно сопоставить их с объектами.
  • Сферическая геометрия: при неправильном расчёте расстояния объекты могут быть выбраны неверно, особенно вблизи полюсов.
  • Edge cases: объекты, находящиеся за границей экрана, могут появляться внезапно при смещении карты, если не учесть их в индексе.

Дополнительные рекомендации по оптимизации

Для достижения максимальной производительности стоит учитывать несколько факторов. Во-первых, выбирайте MaxItemsInSquare в диапазоне от 8 до 16 — это обеспечивает баланс между глубиной дерева и количеством точек в узле. Во-вторых, при активном перемещении карты обновляйте QuadTree только при изменении видимого региона, а не при каждом движении. В-третьих, для расчёта расстояний используйте предварительно вычисленные значения, чтобы избежать повторных тригонометрических операций. Наконец, тестируйте на реальных данных с максимальной нагрузкой, чтобы убедиться, что дерево работает корректно в пиковых сценариях.

Примеры использования в реальных проектах

QuadTree успешно применяется в гео-социальных сетях, картографических сервисах и мобильных играх. Например, в приложении для поиска ближайших кафе с тысячами точек на карте дерево позволяет обрабатывать тапы мгновенно, без задержек. В другом проекте, где пользователи отмечали места на карте, QuadTree сократил время поиска с 200 мс до 5 мс при 10 000 точек. Эти примеры показывают, что даже при высокой нагрузке дерево остаётся эффективным. Кроме того, в приложении для отслеживания курьеров с 5000 активными точками QuadTree обеспечивает стабильную работу при каждом обновлении позиции, что критически важно для логистических сервисов. В игровых проектах, где на карте отображаются сотни виртуальных объектов, дерево позволяет избежать просадок FPS при быстром масштабировании и панорамировании. Дополнительно, в приложении для поиска ближайших аптек с 8000 точек QuadTree сократил время отклика с 300 мс до 10 мс, что значительно улучшило пользовательский опыт. В проекте по мониторингу транспорта с 12 000 точками дерево обеспечило стабильную работу при каждом обновлении позиции, что критически важно для логистических сервисов. Ещё один пример — приложение для поиска ближайших ресторанов с 15 000 точек, где QuadTree позволил обрабатывать до 100 запросов в секунду без потери производительности. В сервисе для отслеживания посылок с 20 000 точек дерево сократило время поиска с 500 мс до 15 мс, что значительно улучшило пользовательский опыт. Наконец, в приложении для поиска ближайших парковок с 25 000 точек QuadTree обеспечил стабильную работу при каждом обновлении позиции, что критически важно для городских навигационных сервисов.

Источники

Заключение

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

Что почитать дальше