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