Будь то поиск ближайшего к вам кинотеатра или заказ поездки у водителя поблизости. Расстояние становится все более постоянным в нашей повседневной деятельности. Для разработчиков, создающих приложения на основе индексации местоположения, расстояние знакомо. Запрос различных геопространственных API, чтобы найти кратчайшее расстояние до местоположения, или определение времени, необходимого для перехода по маршруту с помощью API карт Google. В этой статье мы собираемся обсудить поиск ближайшего соседа по географической координате из набора данных с использованием Cloud firestore.

Поиск ближайших больниц поблизости на Google Maps или получение ответа от водителя поблизости через Bolt всего через несколько секунд после подачи запроса — это важные действия, которые мы считаем само собой разумеющимися, но невероятно сложные для реализации как разработчики, и за ними скрывается сложная математика. Чиди Уильямс пишет отличный пост о структурах данных, которые эффективно хранят и ищут данные в двумерном пространстве, вам обязательно нужно его прочитать!

Наивно можно предположить, что Земля представляет собой плоское двумерное пространство (это не было бы наивно, если бы я был плоскоземельцем, интересно… используют ли плоскоземельцы Карты Google???) и вычислить расстояния от немного базовой математики Trig. Все это упростит и упростит задачу (на самом деле алгоритмы реального мира реализуют тригонометрические вычисления для расчета расстояний). За исключением того, что земля больше похожа на сферу (на самом деле это сплюснутый сфероид, потому что земля вращается вокруг своей малой оси), и это все усложняет. Некоторые действительно изобретательные люди изобрели способ приписывать точки как адреса местам по всему земному шару… эти точки существуют вдоль линий долготы и широты, которые мы используем сегодня для навигации, GPS и многих других интересных вещей (например, полет на 300 тонн из одного самолета). части земного шара в аэропорт за тысячи километров).

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

Да, я знаю, это не реальный сценарий. Но ваши пользователи (пчелиные матки), пытающиеся найти ближайший окада (дрон), чтобы добраться до рынка 12 миль, чтобы преодолеть сумасшедший трафик на дороге Икороду, должны использовать для этого ваше мобильное приложение. Мы используем приложение Node.js (Express) для обработки запросов от мобильного клиента. Вокруг работают сотни okadas, что означает сотни GPS-координат для отслеживания и беспокойства, сотни записей в секунду в любое хранилище данных, в котором мы находимся. собираюсь использовать. Но вот вариант использования, для которого Cloud Firestore был хорошо разработан, поэтому мы используем Firestore в качестве хранилища данных.

С этого момента я буду предполагать, что вы хорошо умеете настраивать сервер Express, создавать конечные точки, обрабатывать запросы и предоставлять соответствующие ответы клиентским приложениям. Я также предполагаю, что вы хорошо осведомлены об интеграции Firebase Admin SDK в свое экспресс-приложение, чтобы иметь возможность использовать службы Firebase в своем экспресс-приложении. Если вам нужна помощь в настройке экспресс-приложения, см. здесь и инструкции по добавлению Firebase Admin SDK в ваше приложение.

Есть определенные важные вещи, которые нам нужно достичь в нашем сценарии;

  • отслеживать наши окады
  • geohash и проиндексировать местоположение окад (это будет объяснено в ближайшее время)
  • поиск ближайшего всадника окада

Получение GPS-координат от вашего клиента выходит за рамки этой статьи, но я уже писал о том, как получить GPS-координаты, пока ваше родное приложение работает в фоновом режиме. Мы будем постоянно обновлять точки широты и долготы наших пчел-трутней в коллекции Firestore. Третье важное поле — это поле геохеширования. Координаты широты и долготы хэшируются в одну 32-битную строку. Система геохеширования — это система геокодирования, которая представляет собой иерархическую структуру, разделяющую пространство на сетки. Это приложение того, что известно как кривая Z-порядка в математических и компьютерных кругах, кривые, заполняющие пространство.

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

Создание и анализ геохэшей — довольно продвинутая вещь, включающая в себя математику, от которой вы в основном убегали в старшей школе. Следовательно, мы собираемся использовать библиотеку на стороне клиента, чтобы помочь нам в этом. Если вы используете старый добрый ванильный javascript-клиент, перейдите к https://github.com/firebase/geofire-js/releasesзагрузке статического файла. Или вы можете установить из npm. Эта библиотека также доступна в реализациях Swift и Java для использования на клиентах Android и iOS.

npm install --save geofire-common

Здесь мы вычисляем геохеш для точек широты и долготы для гонщика Окада по имени Уче.

Теперь мы собираемся найти ближайшего гонщика окада для Йемиси, которая пытается проехать 12-ю милю. Она берет телефон и делает запрос на гонщика, запрос, связывая ее координаты широты и долготы, идет по «интернет-проводам» на скорость света и доставляется на наш экспресс-сервер через определенную конечную точку.

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

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

Примечание. Имейте в виду, что алгоритм геохеширования имеет некоторые ограничения;

  • вероятность появления ложных срабатываний, поэтому необходимо предпринять дополнительный шаг по фильтрации ложных срабатываний (что может привести к дополнительным накладным расходам при вычислениях)
  • точность запросов снижается по мере приближения координат к полюсам, т.е. ‹66 ºN и ‹66 ºS , поэтому в запросах, включающих координаты в этом диапазоне, будет больше ложных срабатываний.

Есть и другие библиотеки (использующие другие алгоритмы), которые обещают большую точность с любыми координатными точками на земном шаре, пример — sphere-knn. Хотя он больше не поддерживается, вы можете разветвить код на github.

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