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

Ответ 1

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

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

  Как вычислить latlng точки на некотором расстоянии от другого?

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

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

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

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

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

   ---

UPDATE:

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

• Радиус вождения (несколько пунктов назначения)

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

Скриншот:

удалена мертвая ссылка ImageShack - Радиус движения

Ответ 2

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

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

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

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

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

Ответ 3

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

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

Ответ 4

• Перечислите все возможные узлы с учетом каждого возможного решения на каждом перекрестке (Но как это сделать автоматически?
• Используйте алгоритм Дейкстры, чтобы найти закрывающий маршрут ко всем точкам.
• Визуализировать данные. (Это немного сложно, потому что внутри доступной области могут быть недоступные области.