Kart Routing, a la Google Maps?

stemmer
19

Jeg har alltid vært fascinert av kart Routing, men jeg har aldri funnet noen god innledende (eller avansert!) Nivå tutorials på den. Er det noen som har noen tips, hint, etc?

Oppdatering: Jeg primært ute etter tips til hvordan et kartsystem er implementert (datastrukturer, algoritmer, etc).

Publisert på 05/08/2008 klokken 20:24
kilden bruker
På andre språk...                            


9 svar

stemmer
14

Ta en titt på åpen gate kartet prosjekt for å se hvordan denne typen ting blir håndtert på en virkelig fri programvare-prosjekt ved hjelp av kun bruker levert og lisensiert data og har en wiki som inneholder ting du kan finne interessant .

For noen år tilbake gutta involvert der ganske enkelt gå og besvart mange spørsmål jeg hadde, så jeg ser ingen grunn til at de fortsatt ikke er en hyggelig gjeng.

Svarte 05/08/2008 kl. 20:27
kilden bruker

stemmer
4

A * er faktisk langt nærmere produksjon kartlegging algoritmer. Det krever ganske mye mindre leting i forhold til Dijikstra opprinnelige algoritmen.

Svarte 24/09/2008 kl. 23:19
kilden bruker

stemmer
4

Barry Brumitt, en av ingeniørene i Google maps rute finne funksjonen, skrev et innlegg om temaet som kan være av interesse:

Veien til bedre sti-finding 11.06.2007 15:47:00

Svarte 17/09/2008 kl. 08:44
kilden bruker

stemmer
4

Ved Kart Routing, mener du finne den korteste veien langs en gate nettverk?

Dijkstra korteste-vei algoritmen er den mest kjente. Wikipedia har ikke en dårlig intro: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Det er en Java-applet her hvor du kan se den i aksjon: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html og Google deg lede deg til kildekoden i nesten alle Språk.

Noen reell implementering for å generere kjøreruter vil inneholde ganske mye data på gatenettet som beskriver kostnader forbinder med traversering lenker og noder-veinett hierarki, gjennomsnittlig hastighet, krysset prioritet, trafikk signal linking, utestengt svinger etc.

Svarte 15/08/2008 kl. 04:31
kilden bruker

stemmer
2

Fra en konseptuell synspunkt, tenk å slippe en stein i en dam og ser bølgene. Rutene vil representere dammen og stein utgangspunktet.

Selvfølgelig algoritmen måtte søke en viss andel av n ^ 2 baner som avstanden n øker. Du vil ta deg startposisjonen og sjekke alle tilgjengelige stier fra det punktet. Deretter rekursivt ring for punktene ved slutten av disse baner, og så videre.

Du kan øke ytelsen ved å ikke dobbel-backing på en bane, ved ikke å re-sjekke rutene på et punkt hvis det allerede har blitt dekket og ved å gi opp stier som tar for lang tid.

En alternativ måte er å bruke ANT feromon tilnærming, hvor maur kontinuerlig tilfeldig fra et startpunkt og la et luktsporet, som bygger opp de mer maur krysse over en gitt bane. Hvis du sender (nok) maur både fra startpunktet og endepunktene så til slutt banen med den sterkeste lukten vil være den korteste. Dette er fordi den korteste veien skal ha blitt besøkt flere ganger i en gitt tidsperiode, gitt at maurene gå på en jevn tempo.

EDIT @ Spikie

Som en ytterligere forklaring på hvordan å implementere dammen algoritme - potensielle datastrukturer som trengs er uthevet:

Du må lagre kartet som et nettverk. Dette er rett og slett et sett med nodesog edgesmellom dem. Et sett med nodesutgjøre en route. En kant slutter seg til to noder (muligens begge den samme node), og har en tilknyttet costslik som distanceeller timefor å traversere kant. En kant kan enten begge være toveis eller enveis. Sannsynligvis enkleste å bare ha ensrettede seg og dobbelt opp for toveis reise mellom nodene (dvs. en kant fra A til B, og en annen for B til A).

Som eksempel forestille seg tre jernbanestasjoner arrangert i en likesidet trekant som peker oppover. Det finnes også ytterligere tre stasjoner hver halvveis mellom dem. Kantene delta alle nabosignaler sammen, vil den endelige diagrammet har en omvendt trekant sitter inne i den større trekant.

Etikett noder som starter fra nederst til venstre, går venstre til høyre og opp, som A, B, C, D, E, F (F øverst).

Anta at kantene kan bli krysset i begge retninger. Hver kant har en kostnad på 1 km.

Ok, så vi ønsker å rute fra bunnen venstre A til øvre stasjon F. Det er mange mulige ruter, inkludert de som dobbelt tilbake på seg selv, f.eks ABCEBDEF.

Vi har en rutine sier NextNode, som aksepterer en nodeog en cost, og kaller seg selv for hver node det kan reise til.

Klart hvis vi lar denne rutinen løp vil det etter hvert oppdage alle ruter, inkludert de som er potensielt uendelig i lengde (f.eks ABABABAB etc). Vi hindre at dette skjer ved å sjekke mot cost. Når vi besøker en node som ikke har blitt besøkt før, setter vi både kostnader og noden vi kom fra mot den noden. Hvis en node har blitt besøkt før vi sjekker mot eksisterende kostnader og hvis vi er billigere enn vi oppdaterer noden og bære på (recursing). Hvis vi er dyrere, så vi hopper noden. Hvis alle nodene er hoppet da vi avslutte rutinen.

Hvis vi treffer vår målgruppe node da vi avslutte rutinen også.

Denne måten alle levedyktig rutene er merket, men avgjørende bare de med lavest mulig kostnad. Ved slutten av prosessen hver node vil ha den laveste kostnaden for å få til denne noden, inkludert våre mål node.

For å få ruten vi jobbe bakover fra vårt mål node. Siden vi lagret noden vi kom fra, sammen med prisen, vi bare hoppe bakover bygge opp ruten. For vårt eksempel vil vi ende opp med noe sånt som:

Node A - (Total) Cost 0 - Fra node ikke
Node B - Kostnads 1 - Fra node A
knutepunkt C - Kostnads 2 - Fra B-node
til node D - Kostnads 1 - Fra node A
node E - Kostnads 2 - Fra node D / pris 2 - Fra Node B (dette er et unntak som er lik kostnad)
Node F - kostnads~~POS=TRUNC 2 - fra node D

Så den korteste ruten er ADF.

Svarte 26/09/2008 kl. 14:05
kilden bruker

stemmer
2

Jeg har ennå å finne en god tutorial på ruting, men det er mange koden for å lese:

Det er GPL routing programmer som bruker OpenStreetMap data, f.eks Gosmore som fungerer på Windows (+ mobil) og Linux. Det finnes en rekke interessante [programmer som bruker de samme dataene, men gosmore har noen kule bruker f.eks grensesnitt med nettsteder .

Det største problemet med ruting er dårlige data, og du aldri få gode nok data. Så hvis du ønsker å prøve det holde test veldig lokale slik at du kan kontrollere dataene bedre.

Svarte 17/09/2008 kl. 08:34
kilden bruker

stemmer
2

I stedet for å lære APIer til hvert kart tjenesteleverandøren (som gmaps, Ymaps api) Det er godt å lære Mapstraction

"Mapstraction er et bibliotek som gir en felles API for ulike script kartlegging APIer"

Jeg foreslår at du går til nettadressen og lære en generell API. Det er god mengde tipsene også.

Svarte 06/08/2008 kl. 13:35
kilden bruker

stemmer
1

Fra min erfaring med å jobbe på dette feltet, gjør A * jobben veldig bra. Det er (som nevnt ovenfor) raskere enn Dijkstras algoritme, men er fortsatt enkel nok for en normalt kompetent programmerer å implementere og forstå.

Bygge rutenettet er den vanskeligste delen, men det kan bli brutt ned i en serie enkle trinn: få alle veier; sortere punktene i rekkefølge; lage grupper av identiske punkter på forskjellige veier inn i skjæringspunktene (noder); legge til lysbuer i begge retninger, hvor nodene forbinder (eller i en retning for en enveis veien).

A * algoritmen i seg selv er godt dokumentert på Wikipedia . Nøkkelen sted å optimalisere er utvalget av de beste node fra den åpne listen, som du trenger en høy ytelse prioritet køen. Hvis du bruker C ++ du kan bruke STL priority_queue adapter.

Tilpasse algoritme for å rute over ulike deler av nettet (f.eks fotgjenger, bil, offentlig transport, etc.) av favør hastighet, distanse eller andre kriterier er ganske enkelt. Du gjør det ved å skrive filtre for å kontrollere hvilke deler av ruten er tilgjengelige, ved bygging av nettverk, og som vekt er tildelt hver enkelt.

Svarte 15/07/2012 kl. 21:13
kilden bruker

stemmer
1

En annen tanke slår meg angående kostnaden for hver traversering, men vil øke tiden og prosessorkraft som kreves for å beregne.

Eksempel: Det er 3 måter jeg kan ta (hvor jeg bor) til å gå fra punkt A til B, i henhold til Google. Garmin enhetene har hver av disse 3 veier i Quickestberegningen av ruten. Etter traversering hver av disse rutene mange ganger, og i snitt (selvsagt vil det være feil, avhengig av tid på dagen, mengde koffein etc.), føler jeg algoritmer kunne ta hensyn til antall svinger i veien for høy grad av nøyaktighet , for eksempel rett vei fra en mil vil være raskere enn en 1 mil vei med skarpe bøyer i den . Ikke et praktisk forslag, men absolutt en jeg bruker til å forbedre resultatet sett mitt daglige pendle.

Svarte 18/09/2011 kl. 21:34
kilden bruker

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more