Göm menyn

Vägvisning

Många använder idag en GPS i bilen för att hitta vägen eller något av kartsystemen som du kan hitta på nätet, t.ex. eniro.se eller hitta.se. Det här projektet går ut på att implementera ett litet system som kan användas för att hitta t.ex. den kortaste vägen mellan två platser och man skall kunna få en vägbeskrivning hur man tar sig mellan platserna, som ni kan få fram via de ovan nämnda söktjänsterna.

  • Ge mig en vägbeskrivning hur man åker från X till Y!
  • Hur långt är det mellan X och Y?
  • När beräknas jag vara framme vid Y?
  • Jag är vid X, finns det några bensinmackar i närheten?

Projektet har minst tre svårigheter:

Det första är hur man representerar kartinformation, dvs det nätverk av vägar och korsningar som kartan består utav och avstånden mellan korsningar och orter mm. Hur associeras annan information i kartan, t.ex. gatunamn, gatutyp, hastighet, bensinmackar, hotell m.m.

Den andra är att ha bra algoritmer för att hitta kortaste/snabbaste vägen? Att göra slumpad sökning fungerar inte i stora nätverk. Vilken information i kartan kan ge underlag för att snabba upp sökningen?

Det sista är hur kan man på ett bra sätt kan presentera en vägbeskrivning. Det kan vara olika detaljeringsnivåer, t.ex. gatunätet i en stad eller huvudvägar mellan orter. Beskrivningen skall bli kompakt och man vill inte upprepa sig.

Tyngdpunkten i projektet ligger på att implementera de olika funktionerna, inte i att få ett snyggt användargränssnitt. Det är alltså helt okej om man ställer frågorna genom att direkt anropa Lispfunktioner som i exemplen nedan.


   (hur-långt 'Linköping '(Stockholm slottet))
   (visa-väg ' kortaste '(Linköping universitet) '(Linköping sjukhuset)))
   (visa-väg ' snabbaste '(Linköping universitet) '(Paris Eiffeltornet)))
   (var-finns-närmaste 'bensinmack '(Linköping Flamman))
Det finns data om ett storta antal svenska orter, vilka grannorter de har, avstånd och hastighet och koordinaten för orten. Se mer i ~TDDC67/lab/projekt-vägbeskrivning.

Vill man mer undersöka hur kartdata är repesentera kan man gå till , en fri wiki-karta. Där man kan plocka fram lågnivådata.


Sidansvarig: Peter Dalenius
Senast uppdaterad: 2010-10-25