Kaart Routing, a la Google Maps?

stemmen
19

Ik heb altijd al geïntrigeerd door Map Routing, maar ik heb nooit gevonden kan elk goed (of zelfs gevorderde!) Niveau tutorials op. Heeft iemand enig pointers, hints, etc?

Update: Ik ben vooral op zoek naar aanwijzingen over hoe een kaart systeem is geïmplementeerd (datastructuren, algoritmen, etc).

De vraag is gesteld op 05/08/2008 om 21:24
bron van user
In andere talen...                            


9 antwoorden

stemmen
14

Neem een kijkje op de open straat kaart project om te zien hoe dit soort dingen wordt aangepakt in een echt vrije software project met behulp van alleen de gebruiker geleverd en gelicentieerd data en hebben een wiki met dingen die je mogelijk interessant vindt .

Een paar jaar terug de jongens die betrokken zijn, waar vrij makkelijk in de omgang en beantwoord veel vragen die ik had, dus ik zie geen reden waarom ze nog steeds niet een mooi stel.

antwoordde op 05/08/2008 om 21:27
bron van user

stemmen
4

A * is eigenlijk veel dichter bij de productie mapping algoritmen. Het vergt heel wat minder exploratie in vergelijking met Dijikstra oorspronkelijke algoritme.

antwoordde op 25/09/2008 om 00:19
bron van user

stemmen
4

Barry Brumitt, één van de ingenieurs van Google maps route bevinding functie, schreef een post op het onderwerp dat van belang kunnen zijn:

De weg naar een betere pad vinden van 11/06/2007 03:47:00

antwoordde op 17/09/2008 om 09:44
bron van user

stemmen
4

Via de kaart Routing, bedoel je het vinden van de kortste weg langs een straat netwerk?

Dijkstra kortste-pad algoritme is de meest bekende. Wikipedia heeft geen slechte intro: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Er is een Java-applet hier, waar je kunt zien in actie: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html en Google u leiden u naar de broncode in vrijwel elke taal.

Elke daadwerkelijke uitvoering voor het genereren van autoroutes zal nogal wat gegevens over de straat netwerk dat de kosten associëren beschrijft met het doorkruisen van verbindingen en knooppunten-wegennet hiërarchie, gemiddelde snelheid, kruising voorrang, verkeerslichten linking, verboden bochten etc.

antwoordde op 15/08/2008 om 05:31
bron van user

stemmen
2

Vanuit een conceptueel oogpunt, stel laten vallen van een steen in een vijver en kijken naar de rimpelingen. De routes zou de vijver en de stenen je uitgangspositie te vertegenwoordigen.

Natuurlijk zou het algoritme moeten bepaalde hoeveelheid n ^ 2 wegen naarmate de afstand toeneemt n zoeken. Je zou je neemt startpositie en laat U alle beschikbare paden vanaf dat punt. Dan recursief bellen met de punten aan het eind van die paden en ga zo maar door.

U kunt de prestaties te verhogen, door niet dubbel-steun op een pad, door niet opnieuw controleren van de routes op een punt als het is al gedekt en door het geven van op paden die te lang duren.

Een alternatieve manier om de mier feromoon benadering, waarbij mieren kruipen willekeurig uit een beginpunt en een geurspoor die opbouwt hoe mieren steek een gegeven pad gebruiken. Als je (genoeg) mieren uit zowel het begin- en eindpunten te sturen dan uiteindelijk het pad met de sterkste geur zal de kortste zijn. Dit komt omdat de kortste weg is meerdere keren zal hebben bezocht in een bepaalde periode, gezien het feit dat de mieren lopen in een uniform tempo.

EDIT @ Spikie

Als een nadere toelichting op hoe de uitvoering van de vijver algoritme - potentiële datastructuren nodig zijn gemarkeerd:

Je moet de kaart als een netwerk op te slaan. Dit is gewoon een set van nodesen edgestussen hen. Een reeks nodesvormen een route. Een rand verbindt twee knooppunten (eventueel beide hetzelfde knooppunt) en een bijbehorende costzoals distanceof timeaan de rand doorlopen. Een rand kan ofwel ofwel bi-directionele of uni-directioneel. Waarschijnlijk eenvoudigste om gewoon uni-directional enen en verdubbelen voor twee enkele reis tussen knooppunten (dat wil zeggen één rand van A naar B en een andere voor B naar A).

Als voorbeeld stel drie stations opgesteld in een gelijkzijdige driehoek wijst. Er zijn ook nog drie stations elk halverwege tussen hen. Randen sluiten alle aangrenzende stations elkaar, zal de uiteindelijke diagram een ​​driehoek zit in de grotere driehoek.

Label knooppunten vanaf linksonder naar links naar rechts en omhoog, zoals A, B, C, D, E, F (F boven).

Neem aan de randen kan in beide richtingen worden verplaatst. Elke rand een kostprijs van 1 km.

Ok, dus we willen de route van de bodem links A naar boven station F. Er zijn veel mogelijke routes, met inbegrip van die terug te verdubbelen aan zichzelf, bijvoorbeeld ABCEBDEF.

We hebben een routine zeggen, NextNodedat een aanvaardt nodeen een costen noemt zichzelf voor elk knooppunt kan reizen.

Het is duidelijk dat als we deze routine te laten lopen zal het uiteindelijk ontdekken alle routes, met inbegrip van degenen die potentieel oneindige lengte zijn (bijv ABABABAB etc). We dit voorkomen door het controleren tegen cost. Wanneer we een bezoek aan een knooppunt dat niet eerder heeft bezocht, hebben we zowel de kosten als het knooppunt we uit tegen dat knooppunt kwam. Als een knooppunt is bezocht voordat we toetsen aan de bestaande kosten en als we goedkoper dan werken we het knooppunt en ga verder (recursief). Als we duurder, dan slaan we het knooppunt. Als alle knooppunten worden overgeslagen dan verlaten we de routine.

Als we onze doelstelling knoop raken dan ook verlaten we de routine.

Op deze manier alle levensvatbare routes worden gecontroleerd, maar cruciaal alleen degenen met de laagste kosten. Tegen het einde van het proces zal elk knooppunt de laagste kosten voor het bereiken van dat knooppunt, met inbegrip van onze doelstelling knooppunt hebben.

Om de route we terug te werken vanuit onze doelstelling knooppunt te krijgen. Aangezien we het knooppunt we, samen met de kosten kwamen opgeslagen, stappen we gewoon achteruit de opbouw van de route. Voor ons voorbeeld zouden we eindigen met iets als:

Knooppunt A - (Total) Cost 0 - Van knooppunt geen
knooppunt B - Cost 1 - Van knooppunt A
knooppunt C - Kosten 2 - Van knooppunt B
knooppunt D - Kosten 1 - Van knooppunt A
knooppunt E - Kosten 2 - Van knooppunt D / kosten 2 - van knooppunt B (dit is een uitzondering omdat er gelijke kosten)
Knooppunt F - kosten 2 - Uit Node D

Dus de kortste route is ADF.

antwoordde op 26/09/2008 om 15:05
bron van user

stemmen
2

Ik heb nog een goede tutorial over routing te vinden, maar er zijn veel van de code te lezen:

Er zijn GPL routing toepassingen die Openstreetmap gegevens gebruiken, bijvoorbeeld Gosmore die werkt op Windows (+ mobiel) en Linux. Er zijn een aantal interessante [toepassingen dat dezelfde gegevens, maar gosmore heeft een aantal coole gebruikt bv koppeling met websites .

Het grootste probleem met routing is slechte data, en je nooit goed genoeg data. Dus als je wilt proberen uw test zeer lokaal te houden, zodat u kunt controleren de gegevens beter.

antwoordde op 17/09/2008 om 09:34
bron van user

stemmen
2

In plaats van het leren van API's om elke kaart service provider (zoals Gmaps, Ymaps api) Het is goed om te leren Mapstraction

"Mapstraction is een bibliotheek die een gemeenschappelijke API biedt diverse Javascript API mapping"

Ik stel voor dat je naar de URL en te leren een algemene API. Er is een goede hoeveelheid How-Tos ook.

antwoordde op 06/08/2008 om 14:35
bron van user

stemmen
1

Vanuit mijn ervaring met het werken op dit gebied, A * doet het werk heel goed. Het is (zoals hierboven vermeld) sneller dan de Dijkstra's algoritme, maar is nog steeds eenvoudig genoeg voor een normaal bevoegde programmeur te implementeren en te begrijpen.

Het bouwen van de route-netwerk is het moeilijkste deel, maar dat kan worden opgesplitst in een aantal stappen: je krijgt alle wegen; sorteert de punten in orde; maak groepen van identieke punten op verschillende wegen naar kruispunten (nodes); voeg bogen in beide richtingen wanneer knooppunten verbinden (of in één richting voor een éénrichtingsweg).

De A * algoritme zelf is goed gedocumenteerd op Wikipedia . De belangrijkste plek om te optimaliseren is de selectie van de beste knooppunt uit de open lijst, waarvoor u een high-performance prioriteit wachtrij nodig. Als je met behulp van C ++ kunt u de STL priority_queue adapter te gebruiken.

Aanpassen van het algoritme om de route over verschillende delen van het netwerk (bijvoorbeeld, voetganger, auto, openbaar vervoer, enz.) Van gunst snelheid, afstand of andere criteria is vrij eenvoudig. Dat doe je door het schrijven van filters om te bepalen welke route segmenten beschikbaar zijn, bij de bouw van het netwerk en welk gewicht wordt toegekend aan een ieder.

antwoordde op 15/07/2012 om 22:13
bron van user

stemmen
1

Een andere gedachte komt me voor met betrekking tot de kosten van elke traversal, maar zou de tijd en rekenkracht die nodig is om te berekenen te verhogen.

Voorbeeld: Er zijn 3 manieren waarop ik kan nemen (waar ik woon) te gaan van punt A naar B, volgens de GoogleMaps. Garmin units bieden elk van deze 3 paden in de Quickestrouteberekening. Na het doorlopen van elk van deze routes vele malen en het gemiddelde (uiteraard zullen er fouten afhankelijk van het tijdstip van de dag, de hoeveelheid cafeïne enz.), Ik voel de algoritmes kan rekening houden met het aantal bochten in de weg voor hoge niveau van nauwkeurigheid , bijv rechte weg 1 mijl zal sneller dan 1 mijl weg met scherpe bochten inzitten . Niet een praktische suggestie maar zeker degene die ik gebruik om het resultaat set van mijn dagelijkse woon-werkverkeer te verbeteren.

antwoordde op 18/09/2011 om 22:34
bron van user

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