Географические препятствия в поисках радиуса

Question

Я новичок здесь, и у меня плохие баллы, поэтому я могу предложить только 50 баллов.

Предположим, у меня есть приложение для поиска всех автозаправочных станций в радиусе 10 миль от определенного местоположения.,Однако одна сторона этого места окружена горным хребтом, который вы должны проехать 50 миль, чтобы обойти.Вы не хотели бы возвращать результаты с другой стороны горы.Какие есть хорошие алгоритмы / методы для решения такой проблемы?Я знаю, что при поиске «точка-точка» вы можете использовать стоимость пути, но я не уверен, что это за метод поиска радиуса.

Вот пример:

Красная линия - это аккорд на радиусном круге от 40, -74 до 41, -72 лат в длину (не совсем точно). Пользователь в 40, -73 выполняет поиск географического радиуса для чего-то, что также охватывает области через LIзвук в Коннектикуте, к которому непрактично добираться.Алгоритм должен знать, что существует аккорд, полностью пересекающий круг поиска, и не возвращать результаты, которые находятся на другой стороне этого аккорда.Таким образом, только точки в зеленой зоне будут возвращены.

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

Answer 1

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

РЕДАКТИРОВАТЬ Поскольку вы, похоже, настроены не использовать сетевой анализ, почему бы некарта растровой стоимости, в которой значение соответствует сложности пересечения этой местности?Это может быть основано на других данных (например, водоемы, высота над уровнем моря, почва и т. Д.).Затем вы можете вернуть станцию ​​с наименьшей стоимостью или выполнить выборку по атрибуту, используя карту цен ...

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

Лучшим инструментом для этой задачи по-прежнему является анализ сети ...

Answer 2

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

Пожалуйста, обратитесь к главам 5.10.1 и 15.2 в Steven Skienn'a "Руководство по разработке алгоритмов »для более подробной информации.Расширенная библиотека графов обеспечивает реализацию алгоритма топологической сортировки.

Я по-прежнему считаю, что это строго графическая проблема, поэтому «радиус 10 миль» - это не то, что ваш алгоритм будет использовать для поиска совпадений, а скорее расстояние до дороги.Хорошее решение должно также включать такие факторы, как ограничение скорости на дорогах, улицах с односторонним движением и т. Д., И позволяет пользователю включать в функцию расчета стоимости для лучшего соответствия.

Answer 3

Вы должны изменить свою метрику, что значит «рядом».В вашем примере 10 миль, рядом - 10 миль Билайн.Тем не менее, вы, возможно, захотите запросить информацию о любых заправочных станциях, где кратчайший путь по улице не превышает 10 миль.

Вы также можете объединить оба подхода и сначала запросить все окружающие точки, а затем отфильтровать их, т. Е. Рассчитав длину маршрута.

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