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

Question

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

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

Вот пример:

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

Answer 3

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

Для получения более подробной информации см. Главы 5.10.1 и 15.2 в «Руководстве по разработке алгоритмов» Стивена Скинн'а. Библиотека графов Boost обеспечивает реализацию топологического алгоритма сортировки.

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