Horizon v0.5.9

Work in progress

Horizon is project aimed to do map matching (snap GPS data to map) and routing (find shortest path between two points)

Table of Contents

• About
• Installation
• Usage
• Benchmark
• Support
• ToDo
• Theory
• Dependencies
• License

About

Horizon is targeted to make map matching as OSRM / Graphopper or Valhala have done, but in Go ecosystem.

Installation

Via go get:

go get github.com/LdDl/horizon
go install github.com/LdDl/horizon/cmd/horizon@v0.5.9

Via downloading prebuilt binary and making updates in yours PATH environment varibale (both Linux and Windows):

• Windows - https://github.com/LdDl/horizon/releases/download/v0.5.9/windows-horizon.zip
• Linux - https://github.com/LdDl/horizon/releases/download/v0.5.9/linux-amd64-horizon.tar.gz

Check if horizon binary was installed properly:

horizon -h

Usage

notice: targeted for Linux users (no Windows/OSX instructions currenlty)

Instruction has been made for Linux mainly. For Windows or OSX the way may vary.

0. Installing Prerequisites

   • Install osm2ch tool. It's needed for converting *.osm.pbf file to CSV for proper usage in contraction hierarchies (ch) library

     go install github.com/LdDl/osm2ch/cmd/osm2ch@v1.5.0
     # for disabling zlib:
     export CGO_ENABLED=0 && go install github.com/LdDl/osm2ch/cmd/osm2ch@v1.5.0

   • Check if osm2ch binary was installed properly:

     osm2ch -h

     

   • Install osmconvert tool. It's needed for removing excess data from road graph and compressing *.osm file. You can follow the link for theirs instruction. We advice to use this method (described in Source paragraph):

     sudo apt install osmctools && wget -O - http://m.m.i24.cc/osmconvert.c | sudo cc -x c - -lz -O3 -o osmconvert

   • Check if osmconvert binary was installed properly:

     osmconvert -h

     

1. First of all (except previous step), you need to download road graph (OSM is most popular format, we guess). Notice: you must change bbox for your region (in this example we using central district of Moscow).

   wget 'https://overpass-api.de/api/map?bbox=37.5453,55.7237,37.7252,55.7837' -O map.osm
   # or curl 'https://overpass-api.de/api/map?bbox=37.5453,55.7237,37.7252,55.7837' --output map.osm

   

2. Compress *.osm file via osmconvert.

   osmconvert map.osm --out-pbf -o=map.osm.pbf

   

3. Convert *.osm.pbf to CSV via osm2ch.

   Notice:

   • osm2ch's default output geometry format is WKT and units is 'km' (kilometers). We are going to change those default values. We are going to extract only edges adapted for cars also.
   • Don't forget to prepare contraction hierarchies via flag 'contract=true'

   osm2ch --file map.osm.pbf --out map.csv --geomf geojson --units m --tags motorway,primary,primary_link,road,secondary,secondary_link,residential,tertiary,tertiary_link,unclassified,trunk,trunk_link --contract=true

   

4. After step above there must be 3 files:

   • map.csv - Information about edges and its geometries
   • map_vertices.csv - Information about vertices and its geometries
   • map_shortcuts.csv - Information about shortcuts which are obtained by contraction process

5. Start horizon server. Provide bind address, port, filename for edges file, σ and β parameters, initial longitude/latitude (in example Moscow coordinates are provided) and zoom for web page of your needs.

   horizon -h 0.0.0.0 -p 32800 -f map.csv -sigma 50.0 -beta 30.0 -maplon 37.60011784074581 -maplat 55.74694688386492 -mapzoom 17.0

   

6. Check if server works fine via POST-request (we are using cURL). Notice: order of provided GPS-points matters.

   curl -X POST -H 'accept: application/json' -H  'Content-Type: application/json' 'http://localhost:32800/api/v0.1.0/mapmatch' -d '{"max_states":5,"state_radius":7.0,"gps":[{"tm":"2020-03-11T00:00:00","lon_lat":[37.601249363208915,55.745374309126895]},{"tm":"2020-03-11T00:00:02","lon_lat":[37.600552781226014,55.7462238201015]},{"tm":"2020-03-11T00:00:04","lon_lat":[37.59995939657391,55.747450858855984]},{"tm":"2020-03-11T00:00:06","lon_lat":[37.60052698189332,55.7480171714195]},{"tm":"2020-03-11T00:00:08","lon_lat":[37.600655978556816,55.748728680680564]},{"tm":"2020-03-11T00:00:10","lon_lat":[37.600372185897115,55.74945469716283]},{"tm":"2020-03-11T00:00:12","lon_lat":[37.600694677555865,55.75052191686339]},{"tm":"2020-03-11T00:00:14","lon_lat":[37.600965570549214,55.751371315759044]},{"tm":"2020-03-11T00:00:16","lon_lat":[37.600926871550165,55.752634490168425]},{"tm":"2020-03-11T00:00:18","lon_lat":[37.60038508556347,55.75559625596534]}]}'

   For shortest path finding (note: edge selection based just on "first nearest found" method, so results may make you upset):

   curl -X POST -H 'accept: application/json' -H  'Content-Type: application/json' 'http://localhost:32800/api/v0.1.0/shortest' -d '{"state_radius":10.0,"gps":[{"lon_lat":[37.601249363208915,55.745374309126895]},{"lon_lat":[37.600926871550165,55.752634490168425]}]}'

   

   For isochrones estimation (note: maxCost => it represents meters in current example):

   curl -X POST -H 'accept: application/json' -H  'Content-Type: application/json' 'http://localhost:32800/api/v0.1.0/isochrones' -d '{"max_cost":2100.0,"nearest_radius": 25.0, "lon_lat":[37.601249363208915,55.745374309126895]}'

   

7. Open Front-end on link http://localhost:32800/

   

8. There is also Swagger documentation for inialized REST API.

   If you use http://localhost:32800/ then you can navigate to http://localhost:32800/api/v0.1.0/docs#overview for API documentation. It may look like (thanks rapidoc):

   

Benchmark

Please follow link

Support

If you have troubles or questions please open an issue. Feel free to make PR's (we do not have contributing guidelines currently, but we will someday)

ToDo

Please see ROADMAP.md

Theory

Thanks for approach described in this paper: Newson, Paul, and John Krumm. "Hidden Markov map matching through noise and sparseness." Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2009

Hidden Markov model is used as backbone for preparing probabities for Viterbi algorithm. Notice that we do not use 'classical' Normal distribution for evaluating emission probabilty or Exponential distribution for evaluatuin transition probabilties in HMM. Instead of it we use Log-normal distribution for emissions and Log-exponential distribution for transitions. Why is that? Because we do not want to get underflow (arithmetic) for small probabilities

Viterbi algorithm is used to evaluate the most suitable trace of GPS track.

Dependencies

• Contraction hierarchies library with bidirectional Dijkstra's algorithm - ch. License is Apache-2.0
• Viterbi's algorithm implementation - viterbi. License is Apache-2.0
• S2 (spherical geometry) library - s2. License is Apache-2.0
• Btree implementation - btree. License is Apache-2.0
• GeoJSON stuff - go.geojson. License is MIT
• Fiber framework (used for server app) - Fiber. License is MIT
• MapboxGL for Front-end - mapboxgl. License is 3-Clause BSD license Replaced with Maplibre due Mapbox changed license. License is modified 3-Clause BSD license, please see ref. link
• moments.js for Front-end - moment.js. License is MIT
• rapidoc for swagger visualization - rapidoc. License is MIT

License

You can check it here