Vă mulțumim pentru susținere

Routingul hărților, a la Google Maps?

Întotdeauna am fost intrigat de Map Routing, dar nu am găsit niciodată tutoriale de nivel introductiv (sau chiar avansate). Are cineva indicii, sugestii etc?

Update: I'm primarily looking for pointers as to how a map system is implemented (data structures, algorithms, etc).

0
adăugat editat

9 răspunsuri

Uitați-vă la proiectul de hartă a străzilor deschise pentru a vedea cum se rezolvă acest tip de lucru într-un software liber proiect care utilizează numai date furnizate și licențiate de utilizatori și au o wiki care conține lucruri pe care le-ați putea găsi interesante .

Cu câțiva ani în urmă, băieții implicați în care mergeau destul de ușor și răspundeau la multe întrebări pe care le aveam, așa că nu vedeam nici un motiv pentru care încă nu sunt o grămadă frumoasă.

0
adăugat

Instead of learning APIs to each map service provider ( like Gmaps, Ymaps api) Its good to learn Mapstraction

"Mapstraction este o bibliotecă care oferă un API comun pentru diferite API-uri de mapare javascript"

Aș sugera să mergeți la adresa URL și să aflați un API general. Există o cantitate bună de Cum-Tos prea.

0
adăugat

Barry Brumitt, unul dintre inginerii serviciului Google Maps, a scris o postare pe această temă care ar putea fi de interes:

The road to better path-finding 11/06/2007 03:47:00 PM

0
adăugat

Prin rutarea hărții, vrei să spui că ai găsit calea cea mai scurtă de-a lungul unei rețele de stradă?

Dijkstra shortest-path algorithm is the best known. Wikipedia has not a bad intro: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Există un applet Java aici, unde îl puteți vedea în acțiune: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html și Google vă conduceți la codul sursă în aproape orice limbă.

Orice implementare reală pentru generarea căilor de rulare va include destul de puține date pe rețeaua stradală care descriu costurile asociate cu legăturile și nodurile de traversare? Ierarhia rețelei rutiere, viteza medie, prioritatea de intersecție, legarea semnalului de trafic,

0
adăugat
Hărțile sunt, în general, prea mari pentru a permite algoritmi de traseu mai scurți standard, va trebui să construiți o serie de euristici pentru a selecta un subgraf. În plus, este posibil să utilizați abordări euristice complet diferite (de exemplu, autostrăzile în primul rând, ..) pentru a găsi un traseu.
adăugat autor Don Johe

Am găsit încă un tutorial bun pe rutare, dar există o mulțime de cod pentru a citi:

Există aplicații de rutare GPL care utilizează date Openstreetmap, de ex. Gosmore care funcționează pe Windows (+ mobile) și Linux. Există o serie de aplicații interesante [care utilizează aceleași date, dar gosmore are câteva utilizări reale de exemplu interfață cu site-uri web .

Cea mai mare problemă cu rutarea este datele necorespunzătoare și niciodată nu obțineți date destul de bune. Deci, dacă doriți să încercați să păstrați testul dvs. foarte local, astfel încât să puteți controla mai bine datele.

0
adăugat

A * este de fapt mult mai aproape de algoritmii de mapare a producției. Este nevoie de o cercetare destul de puțin mai puțin comparativ cu algoritmul inițial al lui Dijikstra.

0
adăugat
De fapt, modificat D * este ceea ce este în general folosit în măsura în care știu.
adăugat autor mmcdole

Din punct de vedere conceptual, imaginați-vă că picurați o piatră într-un iaz și vă uitați la valuri. Traseele ar reprezenta iazul și piatra dvs. poziția de plecare.

Desigur, algoritmul ar trebui să caute o anumită proporție de căi n ^ 2 pe măsură ce distanța n crește. Vă luați poziția de plecare și verificați toate căile disponibile din acel moment. Apoi solicitați recursiv punctele de la sfârșitul acelor căi și așa mai departe.

Puteți crește performanța, fără a vă împiedica dublarea pe o cale, dacă nu re-verificați rutele într-un punct dacă a fost deja acoperită și renunțând la căile care durează prea mult.

Un mod alternativ este de a folosi abordarea feromonilor furnici, unde furnicile se târasc aleatoriu dintr-un punct de plecare și lasă un traseu de parfum, care construiește mai multe furnici care traversează o anumită cale. Dacă trimiteți (suficiente) furnici atât din punctul de început, cât și din punctele de sfârșit, atunci în cele din urmă calea cu cel mai puternic miros va fi cea mai scurtă. Acest lucru se datorează faptului că cel mai scurt drum va fi vizitat de mai multe ori într-o anumită perioadă de timp, dat fiind că furnicile se plimbă într-un ritm uniform.

EDIT @ Spikie

Ca o explicație suplimentară a modului de implementare a algoritmului de iaz - sunt evidențiate potențialele structuri de date necesare:

Va trebui să stocați harta ca rețea. Acesta este pur și simplu un set de nodes și edge între ele. Un set de nodes reprezintă un route . O margine se conectează la două noduri (poate la același nod) și are un cod cost asociat, cum ar fi distance sau time pentru a traversa marginea. O margine poate fi fie bidirecțională, fie unidirecțională. Probabil cel mai simplu este să aibă unități direcționale și să se dubleze pentru deplasarea în două direcții între noduri (adică o margine de la A la B și una diferită pentru B la A).

Ca exemplu, imaginați-vă trei stații de cale ferată aranjate într-un triunghi echilateral îndreptat în sus. Există și alte trei stații, fiecare la jumătatea distanței dintre ele. Marginile se alătură tuturor stațiilor adiacente împreună, diagrama finală va avea un triunghi inversat așezat în triunghiul mai mare.

Etichete noduri începând din stânga jos, mergând din stânga spre dreapta și în sus, ca A, B, C, D, E, F (F în partea de sus).

Presupunem că marginile pot fi traversate în ambele direcții. Fiecare margine are un cost de 1 km.

Ok, așa că dorim să călătorim din stânga jos A spre stația de sus F. Există multe căi posibile, inclusiv cele care se dublează înapoi pe ele însele, de ex. ABCEBDEF.

Avem o rutină de spus, NextNode , care acceptă un nod și un cost și se solicită pentru fiecare nod în care poate călători.

În mod clar, dacă lăsăm această rutină de rulare, în cele din urmă vom descoperi toate căile, inclusiv cele care sunt potențial infinite în lungime (de exemplu, ABABABAB etc.). Oprim acest lucru, verificând valoarea cost . Ori de câte ori vizităm un nod care nu a fost vizitat înainte, am pus atât costul, cât și nodul de la care am venit, împotriva acelui nod. Dacă un nod a fost vizitat înainte de a verifica costul existent și dacă suntem mai ieftini, atunci actualizăm nodul și continuăm (recursul). Dacă suntem mai scumpe, atunci sărim peste nod. Dacă toate nodurile sunt sărite, atunci ieșim din rutină.

Dacă ne atingem nodul țintă, atunci ieșim și din rutină.

În acest fel toate rutele viabile sunt verificate, dar în mod crucial numai cele cu cel mai mic cost. Până la sfârșitul procesului, fiecare nod va avea cel mai mic cost pentru a ajunge la acel nod, inclusiv nodul țintă.

Pentru a obține traseul vom lucra înapoi de la nodul nostru țintă. Din moment ce am stocat nodul de la care am venit, împreună cu costul, noi pur și simplu să ne întoarcem construirea traseului. Pentru exemplul nostru vom ajunge la ceva de genul:

Node A - (Total) Cost 0 - From Node None
Node B - Cost 1 - From Node A
Node C - Cost 2 - From Node B
Node D - Cost 1 - From Node A
Node E - Cost 2 - From Node D / Cost 2 - From Node B (this is an exception as there is equal cost)
Node F - Cost 2 - From Node D

Deci, cel mai scurt traseu este ADF.

0
adăugat
@ jonathan vă rugăm să puteți da detalii despre piatra în algoritmul iazului și cum pot să-l aplic pe un map.let spun eu sunt la un punct și vreau să căutați în jurul valorii de ripple înainte de a trece la următorul ripple exterioare. și tipule știu și 2 ani întârziere la conversație
adăugat autor Spikie

Un alt gând mi se întâmplă în ceea ce privește costul fiecărui traversal, dar ar crește timpul și puterea de procesare necesară pentru a calcula.

Example: There are 3 ways I can take (where I live) to go from point A to B, according to the GoogleMaps. Garmin units offer each of these 3 paths in the Quickest route calculation. After traversing each of these routes many times and averaging (obviously there will be errors depending on the time of day, amount of caffeine etc.), I feel the algorithms could take into account the number of bends in the road for high level of accuracy, e.g. straight road of 1 mile will be quicker than a 1 mile road with sharp bends in it. Not a practical suggestion but certainly one I use to improve the result set of my daily commute.

0
adăugat

Din experiența mea de a lucra în acest domeniu, A * face treaba foarte bine. Este (așa cum am menționat mai sus) mai rapid decât algoritmul lui Dijkstra, dar este încă suficient de simplu pentru ca un programator competent să implementeze și să înțeleagă.

Construirea rețelei de rute este cea mai grea parte, dar care poate fi împărțită într-o serie de pași simpli: obțineți toate drumurile; ordonați punctele în ordine; face grupuri de puncte identice pe drumuri diferite în intersecții (noduri); adăugați arce în ambele direcții unde se conectează nodurile (sau într-o singură direcție pentru un drum cu sens unic).

Algoritmul A * este bine documentat pe Wikipedia . Locul cheie pentru optimizare este selectarea celui mai bun nod din lista deschisă, pentru care aveți nevoie de o coadă de priorități de înaltă performanță. Dacă utilizați C ++, puteți utiliza adaptorul STL priority_queue.

Personalizarea algoritmului pentru deplasarea pe diferite părți ale rețelei (de exemplu, pieton, autoturism, transport public etc.) de viteză favorabilă, distanță sau alte criterii este destul de ușoară. Faceți asta prin scrierea de filtre pentru a controla care segmente de rute sunt disponibile, când se construiește rețeaua și care este atribuită fiecăruia.

0
adăugat