Как бы вы сделали бэкенд для такого приложения?

Question

[Павел]

Суть вопроса. Нужно сделать бэк для приложения. Помимо всего прочего есть такая задача. Клиент, например, каждые 30 секунд будет присылать по API данные о своем положении, эти координаты записываются в БД. Потом прислылается запрос показать всех, кто рядом, например в 100 метрах. Понятно, что перебирать все координаты в БД и сравнивать с координатами клиента - это чушь.

Отсюда вопрос, как такое можно реализовать.

Просьба не разводить холивар по поводу выбора языка)). Это не проект на продажу, а учебный проект. И делаться точно будет на PHP, скорее всего на Laravel.

Спасибо

Answer 1

[Олег Гамега]

postgresql умеет работать с геоданными, я такое делал даже на обрезном sqlite на android, для учебного проекта сгодится любая бд

Comments

[sim3x]

postgis.net

Answer 2

[Сергей Соколов]

«В радиусе 100 метров» это круг, вписанный в квадрат 200x200 метров.
Поэтому выбрать только те, что находятся по X-координате в +-100 метрах. Из них только те, что по Y-координате в +-100 метрах. Из этой выборки проверить каждый на расстояние от точки центра.

Если в БД сделать индексы по X и Y координатам, такая выборка будет быстрой.

Понадобится вычислять координаты углов квадрата, переводя широту, долготу в метры (+–100) и обратно в широту, долготу. Поможет формула.

Можно решить задачу целиком в MySQL – в презентации есть пример запроса и его дальнейшей оптимизации.

Comments

[Сергей Соколов]

Артём Петренков: как там найти все точки не далее X метров от точки (lat,lng) ?

Answer 3

[Philipp]

Для этой задачи идеально подходит MongoDB. В ней просто указываешь точку и радиус https://docs.mongodb.com/v3.2/reference/operator/q...
С точки зрения производительности здесь аналогов практически нет, особенно, если вы можете позволить себе InMemory storage.

Answer 4

[stoitli]

Это называется Spatial Index.
Их поддерживают очень и очень многие современные СУБД.
;)))
MySQL, PostgreSQL, MS SQL, Oracle, Tarantool, Redis и т.д.

Answer 5

[freeExec]

Не совсем то что хотел автор, но вдруг кто-то захочет узнать как это работает изнутри
https://medium.com/@agafonkin/a-dive-into-spatial-...

Answer 6

[devalone]

Индексировать значения по тому, в какой они квадрат карты входят. Т.е. разбиваем всю карту на области(квадраты) определённого размера и при поступлении данных от клиента проверяем, в какой квадрат эти данные входят. Когда же клиент запрашивает кого-то в радиусе, отдаём ему данные из соседних N квадратов, если нужно точно, то пробегаемся по этим данным и считаем расстояние до каждого.

Comments

[Павел]

Такое предложение я видел. Здесь мне не ясно одно. Как разбить карту на квадраты?

[devalone]

Павел: по широте и долготе, получится сетка.

[Сергей Соколов]

devalone: квадрат у полюса совсем не то же, что у экватора.

[stoitli]

Сергей Соколов: с учетом неточности GPS - вряд ли это большая проблема

[Сергей Соколов]

stoitli: неточность GPS ~6 метров. Длина дуги параллели между двумя меридианами с разницей в 1° у экватора (0° долготы) 111.3 км, на 80° долготы – 19.8 км, на полюсе – 0. «Неточность GPS» тут вообще мимо.

[stoitli]

Сергей Соколов: да ты что?
в условиях города? 6 метров?

это в чистом поле точность.

ты то ли ГПС не пользовался на практике никогда, о великий теоретик?
мне частенько показывает, что я нахожусь на противоположенной стороне широкой улицы с 3 х полосным движением в каждую сторону.

[Сергей Соколов]

stoitli: пустой диалог какой-то.. У меня в телефоне GPS определяет позицию верно до 3 метров, отображает на карте. Регулярно пользуюсь навигатором и Strava. Москва то ещё чистое поле. Но речь вообще не об этом. Повторю: нельзя использовать сетку с квадратами «по широте и долготе» из-за разности их площади в четыре порядка у экватора и полюсов.

[stoitli]

Сергей Соколов:
что вы тут втираете?
ГПС в городах с высотной застройкой нередко ВООБЩЕ не ловит достаточное число спутников.
и отдает координаты последней точки, где еще ловило, а это может быть и в километре.

[Сергей Соколов]

stoitli: нельзя использовать сетку с квадратами «по широте и долготе» из-за разности их площади в четыре порядка у экватора и полюсов.

[stoitli]

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

[devalone]

stoitli: Сергей не про то вам говорит, он говорит про то, что размер квадрата будет у полюсов очень маленький и это не связано с точностью GPS.

[stoitli]

devalone: на Полюсах (в т.ч. и недалеко от них) это приложение нафиг никому не нужно.
;)
я это гарантирую на 200%
;)

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

[huwesu]

Сергей Соколов:

У меня в телефоне GPS определяет позицию верно до 3 метров

Да будет врать-то.

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

Причин этому 2:

Погрешность по бит-тайму https://en.wikipedia.org/wiki/Bit_time
Она составляет для бытовых приборов в норме 10 наносекундам. Меньше смысла нет делать и никто из производителей не делает более точные чипы для бытового использования. За это время свет проходит 3 метра.

Вторая причина - недостаточно точные часы в вашем приемнике. Кварц - весьма капризное устройство. Для устранения этой погрешности нужно иметь 4+ более спутников в зоне видимости.

Сумма этих причин даже в самом идеальном случае дает погрешность уже заведомо больше 3 метров.

На практике точность бытовых приборов, предназначенных для ориентирования - 20 метров. Точность профессиональных приборов, предназначенных для геодезии, действительно, выше. Но для того чтобы добиться высокой точности они работают в паре + куча других ухищрений.

То, что вы видите в вашей навигационной программе - это не точные абсолютные, а "приблизительные абсолютные+относительные координаты", то есть выравненный самой программой сглаженный трек относительно самого себя, относительно старого местоположения вашего телефона.

Мы же говорим о двух пользователях двух разных устройств. Там вполне можно рассчитывать на вранье GPS на уровне 50 метров. Что уже сопоставимо с максимальным расстоянием между пользователями. Так что прочие неточности, такие как разные квадраты, - уже и не важны.

Вы можете в этом легко убедиться сами:

Найдите программу, которая просто фиксирует трек, не сглаживая его.
Пройдитесь по улице.
Посмотрите трек.

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

3 метра в бытовом приборе вы можете получить только с помощью Спутниковой системы дифференциальной коррекции

А она доступна далеко не во всяком смартфоне и далеко не на всякой местности.
Поймать в городе сигнал наземных вышек куда как сложнее, чем спутников.

Зная, что ЛККС используется для посадки самолетов, и могу предположить у вас не будет проблем с определением координат с точностью до 3 м - гарантировано только в аэропорту.