PHP: Как реализовать пересечение маршрутов в пути?

Question

[Максим Гречушников]

Есть 2 автомобиля.
Один выехал из пункта А, другой выехал из пункта Б.
В каком то месте своего пути они, допустим, могут встретиться. Как определить в каком месте, через какое время две машины столкнулись?

В планах использовать php, google/yandex/osm maps.
На js визуализировать могу пересечение. Но интересует именно тема с рассчетом в бэкэнде.

Answer 1

[red_led]

Если использовать OSM, то есть вот способы узнать маршрут между точками: Routing/online_routers

Я бы рекомендовал OSRM, на гитхабе можно прочитать про API.

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

Comments

[Максим Гречушников]

а если у меня будет тысяча машин? про реалтайм, как я понимаю, могу забыть?

[red_led]

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

Для первого варианта возникает некоторое количество проблем с объёмами перебора.
В теории вы можете один раз запросить маршрут и сохранить результат к себе на сервер (или поднять свой, если запросов много). Можно даже как нибудь хитро построить индекс и искать пересечения не со всеми маршрутами.

При втором варианте таких проблем возникнуть особо не должно, но всё те же оптимизации лишними не будут.