Ostruzioni geografiche nelle ricerche di raggio

Question

Sono nuovo qui e punti povero quindi posso offrire solo 50 punti di taglie.

Supponiamo Ho un'applicazione una ricerca di tutte le stazioni di gas entro 10 miglia di raggio di un determinato luogo. Tuttavia un lato di questa posizione è circondato da una catena montuosa che devi percorrere 50 miglia per spostarti. Non vorresti restituire risultati dall'altra parte della montagna. Quali sono alcuni buoni algoritmi/tecniche per affrontare un simile problema? So che con ricerche puntuali si possono usare i costi di percorso, ma non sono sicuro di quale sia la tecnica con le ricerche di raggio.

Ecco un esempio:

La linea rossa è un accordo sul cerchio di raggio da 40, -74 a 41, -72 Lat Long (non preciso solo dicendo) L'utente a 40 , -73 esegue una ricerca del raggio geografico per qualcosa che comprende anche aree attraverso il suono LI in Connecticut che sono poco pratiche da raggiungere. L'algoritmo dovrebbe sapere che esiste un accordo che interseca completamente il cerchio di ricerca e non restituisce risultati che si trovano sull'altro lato dell'accordo. Quindi solo i punti nell'area verde verrebbero restituiti.

Questo dovrebbe essere possibile eseguire senza l'analisi della rete stradale se il programmatore definisce queste linee di delimitazione. Ad esempio, in alcuni paesi potrebbe esserci un'area pericolosa da attraversare e si vorrebbe che le persone su entrambi i lati di quell'area siano limitate a quella parte. O un confine internazionale, ecc. Sto solo chiedendo questo perché sono abbastanza sicuro che la gente lo stia facendo.

Answer 1

Sebbene la soluzione migliore sarebbe quella di calcolare la distanza lungo una rete stradale (piuttosto che una distanza lineare) utilizzando, ad esempio, l'Analista di rete di ArcGIS, un attacco sporco sarebbe creare linee rette tra il centro del raggio e ciascuna stazione, quindi calcolare il guadagno di elevazione totale lungo quel profilo (uno script per farlo automaticamente viene dato here). È quindi possibile impostare una soglia per rifiutare quelli con guadagni di elevazione totali superiori a un certo valore (quelli che è necessario attraversare montagne per raggiungere).

EDIT dal momento che sembra impostato a non utilizzando l'analisi di rete, perché non creare una mappa raster costo in cui il valore corrisponde alla difficoltà di attraversare quel terreno? Questo potrebbe essere basato su altri dati (cioè corpi idrici, elevazione, copertura del terreno, ecc.). Quindi è possibile restituire la stazione di costo più basso o effettuare una selezione per attributo utilizzando la mappa dei costi ...

Un'altra opzione sarebbe quella di creare un livello vettoriale poligono che mostri le zone invalicabili (montagne, corpi idrici, ecc.) E quindi crea una linea tra la tua posizione e tutte le stazioni nel raggio. Usando select by location puoi vedere se quella linea interseca uno dei poligoni invalicabili; se lo fa, deseleziona la stazione.

Lo strumento migliore per il compito è ancora Network Analysis ...

Answer 2

Si dovrebbe modificare la metrica, che cosa "vicino" allora significa. Nel tuo esempio 10 miglia nelle vicinanze meami 10 miglia beeline. Tuttavia, potresti preferire interrogare qualsiasi stazione di servizio, in cui il percorso stradale più breve non è più lungo di 10 miglia.

È possibile anche combinare i due approcci e prima query tutti i punti circostanti e poi filtrare, cioè calcolando la lunghezza del percorso.

Se siete più in algoritmi, vi suggerisco di dare un'occhiata al algoritmi pathfinding utilizzati per gli assistenti di navigazione.

Answer 3

La soluzione che è probabilmente più vicina a ciò che si richiede è di prendere posizioni di tutte le stazioni di servizio nell'area, aggiungere punti di intersezione tra il cerchio e le linee di confine delle zone di esclusione e quindi eseguire l'ordinamento topologico sul set di nodi risultante in 2 spazio tridimensionale. Trovare stazioni di servizio all'interno di determinate aree sarà semplice come restituire un insieme di valori che rientrano nell'intervallo dato dato che le voci di un set sono ordinate.

Fare riferimento ai Capitoli 5.10.1 e 15.2 in "Algorithm Design Manual" di Steven Skienn "per ulteriori dettagli. La libreria grafica potenziata fornisce l'implementazione dell'algoritmo di ordinamento topologico.

Continuo a pensare che questo sia strettamente un problema di grafico quindi "il raggio di 10 miglia" non è quello che il tuo algoritmo userebbe per trovare le corrispondenze, ma piuttosto una distanza stradale. Una buona soluzione dovrebbe includere anche fattori come il limite di velocità su strade, strade a senso unico, ecc. E consentire all'utente di includere la funzione di calcolo dei costi per la migliore corrispondenza.