Routino forrásának megtekintése

A routino egy útvonaltervező, mely OSM adatok alapján képes a legrövidebb, vagy a leggyorsabb utat kiszámítani két pont között.

== Telepítés ==

'''Előfeltételek'''
A program előfeltételeit célszerű telepíteni először

<syntaxhighlight lang="bash">
apt-get install gcc make libc6-dev libz-dev libbz2-dev
apt-get install libwww-perl liburi-perl libjson-pp-perl #These are optional
</syntaxhighlight>

'''Telepítés'''
A telepítéshez ez után le kell töltenünk a [https://www.routino.org/download/ Routino weboldaláról] a forráskódot, majd azt kibontva, le kell fordítanunk, majd be kell másolni az Apache webszerver mappájába.

<syntaxhighlight lang="bash">
make
cp -a web /var/www/routino
chown -R www-data:www-data /var/www/routino
</syntaxhighlight>

Ezek után az OSM adatokat fel kell dolgozni:

<syntaxhighlight lang="bash">
cd /var/www/routino/data
../bin/planetsplitter --errorlog [Tetszőleges OSM fájl neve].osm.bz2
</syntaxhighlight>

Miután megvolt, válasszuk ki, hogy OpenLayers vagy Leaflet felületen szeretnénk-e használni a Routino-t, és futtassuk ezt le:

<syntaxhighlight lang="bash">
cd /var/www/routino/www/[openlayers vagy leaflet]
sh -x install.sh
</syntaxhighlight>

Ezek után még egy lépés hátra van, az apache <code>/etc/apache2/sites-enabled/000-default</code> fájljába ezeket a sorokat hozzá kell adni:
<syntaxhighlight lang="xml">
<Directory /var/www/routino>
    AllowOverride Options=MultiViews,ExecCGI FileInfo Limit
</Directory>
</syntaxhighlight>

'''Konfigurálás'''
Szerkesszük az alábbi fájlt: /var/www/routino/www/routino/mapprops.js
* A <code>library</code> változó értékével tudjuk módosítani, hogy az OpenLayers vagy a Leaflet felületet próbálja-e meg betölteni.
* A <code>westedge</code> <code>eastedge</code> <code>southedge</code> <code>northedge</code> <code>zoomout</code> <code>zoomin</code> változókkal értelemszerűen a térkép mozgásterét tudjuk korlátozni, illetve a minimum és a maximum zoom értékeket.
* A <code>mapdata</code> változóban tudjuk megadni, hogy melyik Tileserver-ről szedje le a térkép Tile-okat. Az alapértelmezett Tileserver jelenleg megfelelő lesz.

== Algoritmusok ==

'''Előfeldolgozás'''

Ahhoz, hogy kellően gyors, és hatékony legyen az útvonalkeresés, az OSM adatokat feldolgozzuk, és eltároljuk egy lokális adatbázisban. A csomópontok közül a legtöbbet töröljük, és az érdekes csomópontokat hagyjuk meg. Ezután az izolált területeket töröljük.

A csomópontok megtartásának szabályai:
* 3 vagy több útvonalszakaszt köt össze.
* 2 útvonalszakaszt köt össze, de a két útvonalszakasznak más tulajdonságai vannak.
* 2 útvonalszakaszt köt össze, de az útvonalszakaszok közt megváltoztak az útvonaltervezési korlátozások.

A fentebbi szabályokat felhasználva a csomópontok törlését annyiszor ismételhetjük, amíg csak a legfontosabb csomópontok maradnak már csak meg. Ezeket a csomópontokat szuper-csomópontnak nevezzük, és a szuper-csomópontokat szuper-utak kötik össze.

'''Útkeresés'''

# A kezdőponttól útvonalat keresünk a legközelebbi szuper-csomóponthoz.
# A végponttól útvonalat keresünk a legközelebbi szuper-csomóponthoz.
# Az 1. és a 2. szuper-csomópont közt megkeressük a szuper-útvonalat.
# A 3. pontban talált szuper-útvonalak mindegyikére megkeresi a legrövidebb utat a szuper-útvonal kezdő és végpontja között.

Az útvonal keresési algoritmust az A* algoritmussal (vagy legalábbis egy ehhez nagyon hasonlító algoritmussal) oldották meg. Ez az algoritmus a kezdő csomóponttól a legkisebb érték (legrövidebb, vagy leggyorsabb út) kiszámítására törekszik minden csomóponthoz.

A 4. pontban lévő útvonalakat viszont a Dijkstra algoritmussal keresi meg.

== Példaprogramok ==