Google Maps: Учитывая точку, как найти все точки на данном дорожном расстоянии?
В моем приложении GPS выбирает местоположение механизма. Это, как затем предполагается, помещает маркеры во все точки, где механизм мог быть то, если это управляет для 1 KM в каком-либо направлении (обратите внимание, что дороги могут много раз разветвляться в его 1-километровой досягаемости).
Кто-то может предложить меня, как сделать это?Заранее спасибо.
3 ответа
Это очень сложная проблема, которую можно решить с помощью API Карт Google. Вот один из методов, который вы, возможно, захотите рассмотреть:
Вы можете легко вычислить ограничивающий круг длиной 1 км вокруг вашей точки GPS, а также легко вычислить точки, которые попадают на окружность этого круга, для любого угла. Это расстояние будет "как файлы ворона", а не фактическое расстояние дороги, но вы можете проверить следующий пост Stack Overflow для конкретной реализации этого:
Как рассчитать широту точки на определенном расстоянии вдали от другого?
Снимок экрана с маркерами с интервалом в 20 градусов на ограничивающем круге с радиусом 1 км:
удалена неработающая ссылка на ImageShack - Как рассчитать широту точки на определенном расстоянии от другой?
Там также уловка для привязки этих точек к ближайшей улице. Вы можете проверить Примеры привязки к улицам Майка Уильямса , где это хорошо реализовано.
Расчет расстояния от точки GPS до каждой привязанной точки дороги можно выполнить с помощью службы маршрутов API Карт Google.Обратите внимание, что это будет работать только в странах, которые поддерживают направления в Google Maps, но, что более важно, расстояние по дороге почти всегда будет больше 1 км, потому что наш ограничивающий круг имеет радиус 1 км "по прямой". Однако, если вы можете работать с приблизительной информацией, это уже может быть одним из возможных решений.
Вы также можете начать с вышеуказанного решения (ограничивающий круг длиной 1 км, вычислить x точек на окружности и привязать их к ближайшей дороге), а затем вычислить расстояние до каждого пути (от вашей точки GPS до каждой привязанной точки. ), а затем вы можете повторять это рекурсивно для каждого пути, каждый раз используя меньший ограничивающий круг, пока не достигнете расстояния дороги, близкого к 1 км. Вы можете уменьшить ограничивающий круг в каждой рекурсии пропорционально допустимой погрешности, чтобы сделать ваш алгоритм более эффективным.
ОБНОВЛЕНИЕ:
Я нашел очень аккуратную реализацию, которая, похоже, использует метод, аналогичный тому, который я описал выше:
Обратите внимание, как вы можете изменить интервал градусов сверху. С большим интервалом вы получите быстрые результаты, но можете легко пропустить несколько маршрутов.
Снимок экрана:
удалена неработающая ссылка на ImageShack - Driving Radius
Алгоритм естественного перебора состоит в построении списка всех возможных узлов с учетом каждого возможного решения на каждом перекрестке.
Я сомневаюсь, что в пределах 1 км у вас будет в среднем более 10 перекрестков, и, если предположить, что на перекрестке в среднем 3 варианта выбора, вы получите 3 ^ 10 - около 59 049 конечных узлов (обратите внимание, что вам нужно иметь 10 перекрестков на каждом перекрестке). ответвление дороги до полного номера).
На самом деле их количество уменьшится, и я предполагаю, что добраться до одного и того же узла другим маршрутом будет не так уж редко, особенно в городах.
Такой подход даст вам точный ответ (при условии, что у вас будет хорошая карта улиц в качестве входных данных). Это потенциальное время, но n не кажется таким большим, так что это может быть практично.
Дальнейшие улучшения и оптимизации могут быть возможны в зависимости от того, для чего вам нужны эти узлы (или какие сценарии вы сочтете достаточно похожими, чтобы их сократить).
Немного развивая вышеизложенный подход Дэниела, вы хотите сначала найти все точки в радиусе прямой линии от начала координат. Это ваш начальный набор узлов. Теперь включите ВСЕ ребра, инцидентные этим узлам и другим узлам начального набора. Теперь проверьте, что узлы соединены, и что нет никаких узлов, до которых вы не можете добраться. Теперь создайте "дерево кратчайших путей", начиная с узла автомобиля.
Дерево даст вам кратчайшие пути от вашего начального узла до всех остальных узлов. Обратите внимание, что если вы начнете с создания путей в самых дальних узлах, то все подпути также будут кратчайшими путями к этим узлам на пути. Обязательно помечайте эти узлы на подпутях по мере продвижения, чтобы не пришлось их вычислять. В худшем случае вам потребуется разработать кратчайший путь для всех узлов, но на практике это займет гораздо меньше времени.