Itinerario su mappa, come Google Maps?

Question

Sono sempre stato incuriosito dal Map Routing, ma non ho mai trovato nessun buon tutorial di livello introduttivo (o addirittura avanzato!) su di esso.Qualcuno ha indicazioni, suggerimenti, ecc?

Aggiornamento: Cerco principalmente indicazioni su come viene implementato un sistema di mappe (strutture dati, algoritmi, ecc.).

Answer 1

Dai un'occhiata a progetto di mappa stradale aperta per vedere come questo genere di cose viene affrontato in un progetto di software veramente libero utilizzando solo i dati forniti dall'utente e concessi in licenza e avere un wiki contenente cose che potresti trovare interessanti.

Qualche anno fa i ragazzi coinvolti sono stati piuttosto accomodanti e hanno risposto a molte domande che avevo, quindi non vedo motivo per cui non siano ancora un bel gruppo.

Answer 2

Barry Brumitt, uno degli ingegneri della funzione di ricerca dei percorsi di Google Maps, ha scritto un post sull'argomento che potrebbe interessare:

La strada per una migliore individuazione del percorso06/11/2007 15:47:00

Answer 3

A* è in realtà molto più vicino agli algoritmi di mappatura della produzione.Richiede un po' meno esplorazione rispetto all'algoritmo originale di Dijikstra.

Answer 4

Per Map Routing intendi trovare il percorso più breve lungo una rete stradale?

L’algoritmo del cammino minimo di Dijkstra è il più conosciuto.Wikipedia non ha una brutta introduzione: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

C'è un applet Java qui dove puoi vederlo in azione: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html e Google ti porta al codice sorgente praticamente in qualsiasi lingua.

Qualsiasi implementazione reale per la generazione di percorsi di guida includerà una serie di dati sulla rete stradale che descrivono i costi associati all'attraversamento di collegamenti e nodi: gerarchia della rete stradale, velocità media, priorità degli incroci, collegamento dei segnali stradali, svolte vietate, ecc.

Answer 5

Invece di apprendere le API per ciascun fornitore di servizi di mappa (come Gmaps, Ymaps API), è bello imparare Mappaestrazione

"Mapstraction è una libreria che fornisce un'API comune per varie API di mappatura JavaScript"

Ti suggerirei di andare all'URL e apprendere un'API generale.C'è anche una buona quantità di How-To.

Answer 6

Devo ancora trovare un buon tutorial sul routing ma ci sono molti codici da leggere:

Esistono applicazioni di routing GPL che utilizzano i dati Openstreetmap, ad es. Gosmore che funziona su Windows (+ mobile) e Linux.Esistono numerose [applicazioni interessanti che utilizzano gli stessi dati, ma gosmore ha alcuni usi interessanti per esempio.interfaccia con i siti web.

Il problema più grande con il routing sono i dati errati e non si ottengono mai dati abbastanza buoni.Quindi, se vuoi provarlo, mantieni il test molto locale in modo da poter controllare meglio i dati.

Answer 7

Da un punto di vista concettuale, immagina di far cadere una pietra in uno stagno e di osservare le increspature.I percorsi rappresenterebbero lo stagno e la pietra la tua posizione di partenza.

Ovviamente l'algoritmo dovrebbe cercare una certa proporzione di n^2 percorsi all'aumentare della distanza n.Prenderesti la tua posizione di partenza e controllerai tutti i percorsi disponibili da quel punto.Quindi richiama ricorsivamente i punti alla fine di tali percorsi e così via.

È possibile aumentare le prestazioni non tornando indietro su un percorso, non ricontrollando i percorsi in un punto se è già stato percorso e rinunciando a percorsi che impiegano troppo tempo.

Un modo alternativo è utilizzare l'approccio dei feromoni delle formiche, in cui le formiche strisciano casualmente da un punto di partenza e lasciano una scia olfattiva, che si accumula man mano che più formiche attraversano un determinato percorso.Se invii (abbastanza) formiche sia dal punto di partenza che da quello finale, alla fine il percorso con l'odore più forte sarà il più breve.Questo perché il percorso più breve sarà stato percorso più volte in un dato periodo di tempo, dato che le formiche camminano ad un ritmo uniforme.

EDIT @ Spikie

Come ulteriore spiegazione su come implementare l'algoritmo del laghetto, vengono evidenziate le potenziali strutture di dati necessarie:

Dovrai archiviare la mappa come rete.Questo è semplicemente un insieme di nodes E edges fra loro.Un insieme di nodes costituiscono un route.Un bordo unisce due nodi (possibilmente entrambi lo stesso nodo) e ha un associato cost ad esempio distance O time per attraversare il bordo.Un bordo può essere bidirezionale o unidirezionale.Probabilmente è più semplice avere solo quelli unidirezionali e raddoppiarli per i viaggi bidirezionali tra i nodi (ad es.un bordo da A a B e uno diverso da B ad A).

A titolo di esempio immaginiamo tre stazioni ferroviarie disposte in un triangolo equilatero rivolto verso l'alto.Ci sono anche altre tre stazioni ciascuna a metà strada tra loro.I bordi uniscono insieme tutte le stazioni adiacenti, il diagramma finale avrà un triangolo invertito situato all'interno del triangolo più grande.

Etichetta i nodi partendo dal basso a sinistra, andando da sinistra a destra e verso l'alto, come A,B,C,D,E,F (F in alto).

Supponiamo che i bordi possano essere attraversati in entrambe le direzioni.Ogni bordo ha un costo di 1 km.

Ok, quindi desideriamo percorrere il percorso dalla A in basso a sinistra alla stazione a monte F.Esistono molti percorsi possibili, compresi quelli che raddoppiano su se stessi, ad es.ABCEBDEF.

Abbiamo una routine, diciamo NextNode, che accetta a node e un cost e chiama se stesso per ogni nodo verso cui può viaggiare.

Chiaramente se lasciamo eseguire questa routine alla fine scoprirà tutti i percorsi, compresi quelli potenzialmente di lunghezza infinita (ad esempio ABABABAB ecc.).Evitiamo che ciò accada controllando il file cost.Ogni volta che visitiamo un nodo che non è mai stato visitato prima, mettiamo a confronto sia il costo che il nodo da cui proveniamo.Se un nodo è stato visitato prima controlliamo rispetto al costo esistente e se siamo più economici, aggiorniamo il nodo e proseguiamo (ricorrente).Se siamo più costosi, saltiamo il nodo.Se tutti i nodi vengono saltati, si esce dalla routine.

Se raggiungiamo il nostro nodo target, usciamo anche dalla routine.

In questo modo vengono controllate tutte le tratte praticabili, ma soprattutto solo quelle con i costi più bassi.Alla fine del processo ogni nodo avrà il costo più basso per raggiungere quel nodo, incluso il nostro nodo target.

Per ottenere il percorso lavoriamo all'indietro dal nostro nodo di destinazione.Dato che abbiamo memorizzato il nodo da cui proveniamo insieme al costo, saltiamo semplicemente all'indietro costruendo il percorso.Per il nostro esempio finiremmo con qualcosa del tipo:

Nodo A - Costo (totale) 0 - Dal nodo Nessuno
Nodo B - Costo 1 - Dal nodo A
Nodo C - Costo 2 - Dal nodo B
Nodo D - Costo 1 - Dal nodo A
Nodo E - Costo 2 - Dal Nodo D / Costo 2 - Dal Nodo B (questa è un'eccezione in quanto il costo è uguale)
Nodo F - Costo 2 - Dal Nodo D

Quindi il percorso più breve è ADF.

Answer 8

Dalla mia esperienza di lavoro in questo campo, A* svolge il lavoro molto bene.È (come accennato in precedenza) più veloce dell'algoritmo di Dijkstra, ma è comunque abbastanza semplice da essere implementato e compreso da un programmatore normalmente competente.

Costruire la rete di collegamenti è la parte più difficile, ma può essere suddivisa in una serie di semplici passaggi:prendi tutte le strade;ordinare i punti in ordine;trasformare gruppi di punti identici su strade diverse in intersezioni (nodi);aggiungi archi in entrambe le direzioni dove i nodi si collegano (o in una sola direzione per una strada a senso unico).

Lo stesso algoritmo A* lo è ben documentato su Wikipedia.Il punto chiave da ottimizzare è la selezione del nodo migliore dall'elenco aperto, per il quale è necessaria una coda con priorità ad alte prestazioni.Se utilizzi C++ puoi utilizzare l'adattatore STL priorità_queue.

Personalizzare l'algoritmo per instradare su diverse parti della rete (ad esempio pedoni, automobili, trasporti pubblici, ecc.) favorendo la velocità, la distanza o altri criteri è abbastanza semplice.Puoi farlo scrivendo filtri per controllare quali segmenti di percorso sono disponibili, quando costruisci la rete, e quale peso è assegnato a ciascuno di essi.

Answer 9

Mi viene in mente un'altra riflessione riguardante il costo di ogni attraversamento, ma aumenterebbe il tempo e la potenza di elaborazione necessari per il calcolo.

Esempio: Ci sono 3 modi che posso prendere (dove vivo) per andare dal punto A al punto B, secondo GoogleMaps.Le unità Garmin offrono ciascuno di questi 3 percorsi nel Quickest calcolo del percorso.Dopo aver attraversato ciascuno di questi percorsi molte volte e aver calcolato la media (ovviamente ci saranno errori a seconda dell'ora del giorno, della quantità di caffeina, ecc.), ritengo che gli algoritmi potrebbero prendere in considerazione il numero di curve della strada per un elevato livello di precisione , per esempio. Una strada diritta di 1 miglio sarà più veloce di una strada di 1 miglio con curve strette.Non è un suggerimento pratico ma sicuramente lo utilizzo per migliorare i risultati dei miei spostamenti quotidiani.