Obstrucciones geográficas en las búsquedas de radio

Question

Soy nuevo aquí y me siento pobre, así que solo puedo ofrecer recompensas de 50 puntos.

Supongamos que tengo una aplicación para buscar todas las estaciones de servicio dentro de un radio de 10 millas de una determinada ubicación. Sin embargo, un lado de este lugar está rodeado por una cadena montañosa que debe recorrer 50 millas para desplazarse. No querrás devolver resultados del otro lado de la montaña. ¿Cuáles son algunos buenos algoritmos/técnicas para lidiar con tal problema? Sé que con las búsquedas punto a punto puede usar los costos de ruta, pero no estoy seguro de cuál es la técnica con las búsquedas de radio.

Aquí se muestra un ejemplo:

La línea roja es un acorde en el círculo de radio 40, -74 a 41, -72 lat largo (no precisa sólo decir) El usuario en 40 , -73 realiza una búsqueda de radio geográfico para algo que también abarca áreas a través del sonido LI en Connecticut a las que no es factible acceder. El algoritmo debe saber que existe un acorde que se cruza por completo con el círculo de búsqueda y no devuelve los resultados que se encuentran al otro lado de ese acorde. Por lo tanto, solo se devolverán los puntos en el área verde.

Esto debería poder realizarse sin ningún análisis de red de carreteras si el programador define estas líneas delimitadoras. Por ejemplo, puede haber un área en algún país que sea peligrosa para atravesar y desearía que la gente de cualquier lado de esa área esté restringida a ese lado. O un borde internacional, etc. Solo estoy preguntando esto porque estoy bastante seguro de que la gente está haciendo esto.

Answer 1

Aunque la mejor solución sería calcular la distancia a lo largo de una red de carreteras (en lugar de la distancia de línea recta) utilizando, por ejemplo, Network Analyst de ArcGIS, un truco sucio sería crear líneas rectas entre el centro de su radio y cada estación, luego calcule la ganancia de elevación total a lo largo de ese perfil (se da un guión para hacer esto automáticamente here). Luego, puede establecer un umbral para rechazar aquellos con ganancias de elevación totales superiores a un valor determinado (aquellos a los que necesita cruzar para alcanzar las montañas).

EDITAR Ya que parece que no usa el análisis de red, ¿por qué no crea un mapa de coste por puntos en el que el valor corresponde a la dificultad de atravesar ese terreno? Eso podría basarse en otros datos (es decir, cuerpos de agua, elevación, cobertura terrestre, etc.). Luego puede devolver la estación de menor costo o hacer un atributo de selección por el mapa de costos ...

Otra opción sería crear una capa vectorial de polígonos que muestre las zonas intransitables (montañas, masas de agua, etc.) y luego crea una línea entre tu ubicación y todas las estaciones en el radio. Al seleccionar Seleccionar por ubicación, puede ver si esa línea se cruza con cualquiera de los polígonos intransitables; si lo hace, desmarque la estación.

La mejor herramienta para la tarea sigue siendo el análisis de redes ...

Answer 2

Debe cambiar su métrica, lo que "cerca", entonces significa. En su ejemplo, 10 millas cerca de los meams 10 millas a la derecha. Sin embargo, es posible que desee consultar las estaciones de servicio, donde el camino más corto no está a más de 10 millas de distancia.

También puede combinar ambos enfoques y consultar primero todos los puntos circundantes y luego filtrarlos, es decir, calculando las longitudes de ruta.

Si está más interesado en los algoritmos, le sugiero que eche un vistazo a los algoritmos de identificación utilizados para los asistentes de navegación.

Answer 3

Solución que posiblemente esté más cerca de lo que está pidiendo es tomar ubicaciones de todas las gasolineras en el área, agregar puntos de intersección entre el círculo y sus líneas de exclusión y realizar clasificación topológica en el conjunto de nodos resultante en 2 espacio tridimensional Encontrar estaciones de servicio dentro de cierta área será tan simple como devolver un conjunto de valores que se encuentren dentro del rango dado dado que las entradas en un conjunto están ordenadas.

Consulte los Capítulos 5.10.1 y 15.2 en Steven Skienn'a "Algorithm Design Manual" para obtener más información. La biblioteca de gráficos Boost proporciona la implementación del algoritmo de clasificación topológica.

Todavía creo que esto es estrictamente un problema de gráfico, por lo que "10 millas de radio" no es lo que su algoritmo utilizaría para encontrar coincidencias, sino más bien una distancia de la carretera. Una buena solución también debe incluir factores como el límite de velocidad en las carreteras, las calles de una sola dirección, etc., y permite al usuario incluir la función de cálculo de costos para obtener la mejor coincidencia.