Карты Google: учитывая точку, как найти все точки на заданном расстоянии от дороги?

Question

В моем приложении GPS выбирает местоположение автомобиля. Затем предполагается установить маркеры во всех точках, где может находиться транспортное средство, если оно движется на 1 км в любом направлении (обратите внимание, что дороги могут разветвляться много раз в пределах его досягаемости в 1 км).

Может кто-нибудь подсказать мне, как это сделать? Заранее спасибо.

Answer 1

Это очень сложная проблема, которую нужно решить с помощью Google Maps API. Ниже приведен один из методов, который вы можете рассмотреть:

1. Вы можете легко рассчитать ограничивающий круг в 1 км вокруг вашей точки GPS, а также легко рассчитать точки, которые попадают на окружность этого круга, для любого угла. Это расстояние будет «в виде вороньих файлов», а не фактическое дорожное расстояние, но вы можете проверить следующую публикацию переполнения стека для конкретной реализации этого:

   Как рассчитать ширину точки на определенном расстоянии от другой?

   Снимок экрана с маркерами с интервалами 20 градусов на ограничительном круге радиусом 1 км:

удалена мертвая ссылка ImageShack - Как рассчитать ширину точки на определенном расстоянии от другой?

2. Существует также хитрость для привязки этих точек к ближайшей улице. Вы можете проверить Привязку Майка Уильямса к примерам улиц для хорошей реализации этого.

   Расчет расстояния дороги от точки GPS до каждой привязанной точки дороги можно выполнить с помощью службы указаний API Карт Google. Обратите внимание, что это будет работать только в тех странах, которые поддерживают направления в Картах Google, но, что более важно, расстояние до дороги почти всегда будет больше 1 км, поскольку наш ограничительный круг имеет радиус 1 км «по прямой линии». Однако, если вы можете работать с приблизительной информацией, это может быть одним из возможных решений.

3. Вы также можете рассмотреть возможность начать с вышеуказанного решения (1 км ограничивающего круга, рассчитать x точек на окружности и привязать их к ближайшей дороге), а затем рассчитать расстояние до каждой трассы (от точки GPS до каждой привязанной точки), и затем вы можете повторить это рекурсивно для каждого пути, каждый раз используя меньший ограничивающий круг, пока не достигнете расстояния дороги, близкого к 1 км. Вы можете уменьшить ограничивающий круг в каждой рекурсии пропорционально допустимому количеству ошибок, чтобы сделать ваш алгоритм более эффективным.

---

UPDATE:

Я нашел очень аккуратную реализацию, которая, похоже, использует метод, аналогичный описанному выше:

• Радиус вождения (несколько направлений)

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

Скриншот:

удалена мертвая ссылка ImageShack - Driving Radius

Answer 2

Немного подробнее остановившись на подходе Даниила, вы хотите сначала найти все точки в радиусе прямой линии от вашего источника. Это ваш начальный набор узлов. Теперь включите ВСЕ ребра, инцидентные этим узлам и другим узлам, в ваш начальный набор. Теперь убедитесь, что узлы соединены и что вокруг нет плавающих узлов, к которым вы не можете добраться. Теперь создайте « дерево кратчайших путей », начиная с узла вашего транспортного средства.

Дерево даст вам кратчайшие пути от вашего начального узла до всех других узлов. Обратите внимание, что если вы начнете с создания путей в самых дальних узлах, любые подпуть также будут кратчайшими путями к этим узлам на этом пути. Обязательно пометьте эти узлы в подпути по мере продолжения, чтобы вам не нужно было их вычислять. В худшем случае вам нужно разработать кратчайший путь для всех узлов, но на практике это займет гораздо меньше времени.

Answer 3

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

Я сомневаюсь, что в течение 1 км вы получите в среднем более 10 перекрестков, и если принять среднее значение 3 вариантов на перекрестке, вы получите 3 ^ 10 - около 59 049 конечных узлов (обратите внимание, что на каждом перекрестке должно быть 10 ветка дороги до полного номера).

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

Этот подход даст вам точный ответ (при условии, что у вас есть хорошая карта улиц в качестве входных данных). Это потенциальное время, но n, кажется, не настолько велико, поэтому оно может быть практичным.

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

Answer 4

1. Список всех возможных узлов с учетом каждого возможного решения на каждом перекрестке (А как это сделать автоматически?
2. Используйте алгоритм Дейкстры, чтобы найти близкий маршрут ко всем точкам.
3. Визуализация данных. (Это немного сложно, потому что внутри недосягаемой области могут быть недоступные области.