horizon

Horizon v0.11.1

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
  • Docker
• 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.

Demonstration:

Installation

Via go get:

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

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.11.1/windows-horizon.zip
• Linux - https://github.com/LdDl/horizon/releases/download/v0.11.1/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.

1. 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.1
     # for disabling zlib:
     export CGO_ENABLED=0 && go install github.com/LdDl/osm2ch/cmd/osm2ch@v1.5.1
     

   • 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):

     wget -O - http://m.m.i24.cc/osmconvert.c | sudo cc -x c - -lz -O3 -o osmconvert && sudo mv osmconvert /usr/local/bin/
     

   • Check if osmconvert binary was installed properly:

     osmconvert -h
     

     

2. 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
   

   

3. Compress *.osm file via osmconvert.

   osmconvert map.osm --out-pbf -o=map.osm.pbf
   # If you want skip authors/versions
   # osmconvert map.osm --drop-author --drop-version --out-pbf -o=map.osm.pbf
   

   

4. 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 units to meters. 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 wkt --units m --tags motorway,primary,primary_link,road,secondary,secondary_link,residential,tertiary,tertiary_link,unclassified,trunk,trunk_link --contract=true
   

   

5. 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

6. 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
   

   

   5.1. If you need to enable gRPC API use flags grpc, gh, gp and optionally gr, e.g.:

   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 -grpc=true -gh 0.0.0.0 -gp 32801 -gr=true
   

   

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

   • Map matching:

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

     Note: You can specify state_radius field to limit the search area (value should be in meters, float), but this is at your own risk — it may cause matching to fail if no candidates are found within the radius.

     

     Or with gRPC enabled on server-side you call gRPC API via any gRPC client, e.g. grpcurl tool (make sure you've enabled reflection for it):

     grpcurl -plaintext -emit-defaults -d '{
     "max_states": 5,
     "gps": [
         {"tm": "2024-11-30T00:00:00", "lon": 37.601249363208915, "lat": 55.745374309126895},
         {"tm": "2024-11-30T00:00:02", "lon": 37.600552781226014, "lat": 55.7462238201015},
         {"tm": "2024-11-30T00:00:04", "lon": 37.59995939657391, "lat": 55.747450858855984},
         {"tm": "2024-11-30T00:00:06", "lon": 37.60052698189332, "lat": 55.7480171714195},
         {"tm": "2024-11-30T00:00:08", "lon": 37.600655978556816, "lat": 55.748728680680564},
         {"tm": "2024-11-30T00:00:10", "lon": 37.600372185897115, "lat": 55.74945469716283},
         {"tm": "2024-11-30T00:00:12", "lon": 37.600694677555865, "lat": 55.75052191686339},
         {"tm": "2024-11-30T00:00:14", "lon": 37.600965570549214, "lat": 55.751371315759044},
         {"tm": "2024-11-30T00:00:16", "lon": 37.600926871550165, "lat": 55.752634490168425},
         {"tm": "2024-11-30T00:00:18", "lon": 37.60038508556347, "lat": 55.75559625596534}
     ]
     }' localhost:32801 horizon.Service/RunMapMatch | tr -d '\n\t ' ; echo
     

     

   • For shortest path finding:

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

     Note: You can optionally specify state_radius to limit the search area (in meters, float), but this is at your own risk — it may cause routing to fail if no candidates are found within the radius.

     

     Or with gRPC enabled on server-side you call gRPC API via any gRPC client, e.g. grpcurl tool (make sure you've enabled reflection for it):

     grpcurl -plaintext -emit-defaults -d '{
     "gps": [
         {"lon": 37.601249363208915, "lat": 55.745374309126895},
         {"lon": 37.600926871550165, "lat": 55.752634490168425}
     ]
     }' localhost:32801 horizon.Service/GetSP | tr -d '\n\t ' ; echo
     

     

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

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

     Note: You can optionally point field nearest_radius to limit the search area (in meters, float), but this is at your own risk — it may cause the request to fail if no vertex is found within the radius.

     

     Or with gRPC enabled on server-side you call gRPC API via any gRPC client, e.g. grpcurl tool (make sure you've enabled reflection for it):

     grpcurl -plaintext -emit-defaults -d '{
     "max_cost": 2100.0,
     "lon": 37.601249363208915,
     "lat": 55.745374309126895
     }' localhost:32801 horizon.Service/GetIsochrones | tr -d '\n\t ' ; echo
     

     

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

   
   • Blue - observation point (measurement)
   • Purple - represents matched edge
   • Yellow - represents projection of the point onto the matched edge
   • Green - represents picked either source or target vertex of the matched edge
   • Red - represents cuts of excessed geometries (for first and last matched edges)
   • Dark Blue - represents intermediate edges (i.e. there are some edges between two matched edges)

9. 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/index.html#overview for API documentation. It may look like (thanks rapidoc):

   

   If gRPC is enabled you can navigate to http://localhost:32800/api/v0.1.0/grpc/docs/index.html to see gRPC documentation:

10. Each observation in either gRPC or HTTP API response has matcher code assigned. It helps to understand what was the result of matching for each observation. Here is a table of those:

    Code	Constant	Description
    900	CODE_OK	Successfully matched
    901	CODE_NO_CANDIDATES	No candidates found for observation
    902	CODE_ALONE_OBSERVATION	Interrupted segment (no route to previous/next observation), i.e. orphan observation

Docker

If you don't want use binary or can't build it you can use public Docker image:

docker pull dimahkiin/horizon:latest
# Make sure you set up volume correctly. Is this example I've just used the current user directory
docker run -p 32800:32800 -p 32801:32801 \
  -v $(pwd):/app/data \
  dimahkiin/horizon \
  -h 0.0.0.0 -p 32800 -f /app/data/map.csv \
  -sigma 50.0 -beta 30.0 \
  -maplon 37.60011784074581 -maplat 55.7469688386492 -mapzoom 17.0 \
  -grpc=true -gh 0.0.0.0 -gp 32801 -gr=true

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