Как придумать алгоритм поиска свободных машин такси в радиусе координат пользователя?

Question

[Poligraphist]

Помогите разобраться с концепцией решения задачи.

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

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

Как вы видите схему работы с базой при такой задаче? Если есть формула которая сравнивает координаты двух объектов человека и машины и говорит о том, что объекты в нужном радиусе, мы же не можем постоянно проверять на вхождение в радиус всех машин в базе?

Какие есть идеи?

Comments

[Akina]

Плюньте на радиус, ищите в квадрате. Вычислительно - на порядок проще, и выражение проверки элементарное.

В крайнем случае - после такого отбора проверяйте на радиус только те машины, которые попали в квадрат. Всё одно меньше считать.

[Владимир Коротенко]

Akina, откройте для себя geotype в базах да и в прикладных библиотеках, это и быстрее и уже есть

[Akina]

Владимир Коротенко, Уж не хотите ли Вы сказать, что функции из geotype работают быстрее вульгарного x1 between x2-r and x2+r?

[Владимир Коротенко]

Akina, Именно это я и хочу сказать

[Akina]

Владимир Коротенко, ну попробую поверить.

Хотя из моей практики (да, прямо скажем, небольшой) - в MySQL при использовании spatial data предотбор по отклонению серьёзно ускорял поиск, а сравнимые по скорости результаты получались только когда порядка четверти точек попадали в пред-отбор.

[freeExec]

Akina, Операции сравнения те же самые, но тут в игру вступает пространственный индекс, что сужает объекты, которые нужно непосредственно проверять.

Answer 1

[Владимир Коротенко]

В Базе есть тип геоданные простой запрос вам отдаст все машины в нужном радиусе. Но лучше пользоваться сервисом маршрутов. Поясню почему. Допустим вы стоите на правом берегу в Воронеже , и делаете запрос с 2 километровым радиусом, он захватит машины с левого берега, которым ещё доехать до моста а потом к вам.

Comments

[Poligraphist]

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

[Армянское Радио]

Poligraphist, Любители ML рассматривают вероятности прибытия машины в нужную точку в нужное время, так точнее.

[Владимир Коротенко]

Poligraphist, подсмотрите идеи тут
https://yandex.ru/routing/

[Poligraphist]

Владимир Коротенко, Спасибо большое. Всё стало намного понятнее.

Answer 2

[ComodoHacker]

В базах создаются специальные структуры данных и индексы к ним, которые позволяют эффективно выполнять запросы вида "какие объекты находятся на расстоянии не более R от точки (X,Y)?". Например, если для упрощения вместо круга взять квадрат, хорошо работает R-Tree. Реализация для SQLite.

Более серьезное решение для PostgreSQL: postgis.refractions.net

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