horizon

package module
v0.5.8 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jun 28, 2024 License: Apache-2.0 Imports: 18 Imported by: 0

README

Horizon v0.5.8 GoDoc Build Status Sourcegraph Go Report Card GitHub tag

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

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

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

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

  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

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

  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

  7. 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]}'

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

  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#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

Documentation

Index

Constants

View Source 
const (
	// EarthRadius Approximate radius of Earth
	EarthRadius = 6370986.884258304
)

Variables

View Source 
var (
	ErrMinumimGPSMeasurements = fmt.Errorf("number of gps measurements need to be 3 atleast")
	ErrCandidatesNotFound     = fmt.Errorf("there is no a single GPS point having candidates")
	ErrTimeDifference         = fmt.Errorf("time difference between subsequent location measurements must be >= 0")
	ErrSourceNotFound         = fmt.Errorf("can't find closest edge for 'source' point")
	ErrSourceHasMoreEdges     = fmt.Errorf("more than 1 edge for 'source' point")
	ErrTargetNotFound         = fmt.Errorf("can't find closest edge for 'target' point")
	ErrTargetHasMoreEdges     = fmt.Errorf("more than 1 edge for 'target' point")
	ErrPathNotFound           = fmt.Errorf("path not found")
	ErrSameVertex             = fmt.Errorf("same vertex")
)

Functions

func ExponentialDistribution 

func ExponentialDistribution(beta, x float64) float64

ExponentialDistribution 1 / (β*exp(-x/β)), beta = 1/λ

func GeoJSONToS2PointFeature added in v0.5.0 

func GeoJSONToS2PointFeature(pts *geojson.Geometry) (s2.Point, error)

GeoJSONToS2PointFeature Returns s2.Point representation of *geojson.Geometry (of Point type)

func GeoJSONToS2PolylineFeature 

func GeoJSONToS2PolylineFeature(pts *geojson.Geometry) (*s2.Polyline, error)

GeoJSONToS2PolylineFeature Returns *s2.Polyline representation of *geojson.Geometry (of LineString type)

func LogExponentialDistribution 

func LogExponentialDistribution(beta, x float64) float64

LogExponentialDistribution ln(1/β) - (x/β), beta = 1/λ

func LogNormalDistribution 

func LogNormalDistribution(sigma, x float64) float64

LogNormalDistribution https://en.wikipedia.org/wiki/Log-normal_distribution

func NormalDistribution 

func NormalDistribution(sigma, x float64) float64

NormalDistribution https://en.wikipedia.org/wiki/Normal_distribution

func S2PointToGeoJSONFeature 

func S2PointToGeoJSONFeature(pt *s2.Point) *geojson.Feature

S2PointToGeoJSONFeature Returns GeoJSON representation of *s2.Point

func S2PolylineToGeoJSONFeature 

func S2PolylineToGeoJSONFeature(pts *s2.Polyline) *geojson.Feature

S2PolylineToGeoJSONFeature Returns GeoJSON representation of *s2.Polyline

Types

type CandidateLayer 

type CandidateLayer struct {
	Observation                *GPSMeasurement
	States                     RoadPositions
	EmissionLogProbabilities   []emission
	TransitionLogProbabilities []transition
}

CandidateLayer Wrapper around Observation 

Observation - observation itself
States - set of projections on road network
EmissionLogProbabilities - emission probabilities between Observation and corresponding States
TransitionLogProbabilities - transition probabilities between States

func NewCandidateLayer 

func NewCandidateLayer(observation *GPSMeasurement, states RoadPositions) *CandidateLayer

NewCandidateLayer Returns pointer to created CandidateLayer

func (*CandidateLayer) AddEmissionProbability 

func (ts *CandidateLayer) AddEmissionProbability(candidate *RoadPosition, emissionLogProbability float64)

AddEmissionProbability Append emission probability to slice of emission probablities

func (*CandidateLayer) AddTransitionProbability 

func (ts *CandidateLayer) AddTransitionProbability(fromPosition, toPosition *RoadPosition, transitionLogProbability float64)

AddTransitionProbability Append transition probability to slice of transition probablities

type Edge 

type Edge struct {
	ID     int64
	Source int64
	Target int64
	Weight float64
	*s2.Polyline
}

Edge Representation of segment of road (edge in graph) 

ID - unique identifier
Source - identifier of source vertex
Target - identifier of target vertex
Weight - cost of moving on edge (usually it is length or time)
Polyline - geometry of edge, pointer to s2.Polyline (wrapper)

type GPSMeasurement 

type GPSMeasurement struct {
	*GeoPoint
	// contains filtered or unexported fields
}

GPSMeasurement Representation of telematic data 

id - unique identifier
dateTime - timestamp
GeoPoint - latitude(Y)/longitude(X), pointer to GeoPoint (wrapper)

func NewGPSMeasurement 

func NewGPSMeasurement(t time.Time, lon, lat float64, srid ...int) *GPSMeasurement

NewGPSMeasurement Returns pointer to created GPSMeasurement 

t - time.Time (will be converted to UnixTimestamp and used for unique identifier)
lon - longitude (X for SRID = 0)
lat - latitude (Y for SRID = 0)
srid - SRID (see https://en.wikipedia.org/wiki/Spatial_reference_system), if not provided then SRID(4326) is used. 0 and 4326 are supported.

func NewGPSMeasurementFromID 

func NewGPSMeasurementFromID(id int, lon, lat float64, srid ...int) *GPSMeasurement

NewGPSMeasurementFromID Returns pointer to created GPSMeasurement 

id - unique identifier (will be converted to time.Time also)
lon - longitude (X for SRID = 0)
lat - latitude (Y for SRID = 0)
srid - SRID (see https://en.wikipedia.org/wiki/Spatial_reference_system), if not provided then SRID(4326) is used. 0 and 4326 are supported.

func (*GPSMeasurement) ID 

func (gps *GPSMeasurement) ID() int

ID Returns generated identifier for GPS-point

func (*GPSMeasurement) TM added in v0.2.4 

func (gps *GPSMeasurement) TM() time.Time

TM Returns generated (or provided) timestamp for GPS-point

type GPSMeasurements 

type GPSMeasurements []*GPSMeasurement

GPSMeasurements Set of telematic data

type GPSTrack 

type GPSTrack []*GPSMeasurement

GPSTrack Set of telematic data

type GeoPoint 

type GeoPoint struct {
	s2.Point
	// contains filtered or unexported fields
}

GeoPoint Wrapper around of s2.Point 

Needs additional field "srid" to determine what algorithm has to be used to calculate distance between objects
SRID = 0, Euclidean distance
SRID = 4326 (WGS84), Distance on sphere

func NewEuclideanPoint 

func NewEuclideanPoint(x, y float64) *GeoPoint

NewEuclideanPoint Returns pointer to created GeoPoint with SRID = 0

func NewWGS84Point 

func NewWGS84Point(lon, lat float64) *GeoPoint

NewWGS84Point Returns pointer to created GeoPoint with SRID = 4326

func (*GeoPoint) DistanceTo 

func (gp *GeoPoint) DistanceTo(gp2 *GeoPoint) float64

DistanceTo Compute distance between two points. 

Algorithm of distance calculation depends on SRID.
SRID = 0, Euclidean distance
SRID = 4326 (WGS84), Distance on sphere

func (*GeoPoint) GeoJSON 

func (gp *GeoPoint) GeoJSON() *geojson.Feature

GeoJSON Returns GeoJSON representation of GeoPoint

func (*GeoPoint) SRID 

func (gp *GeoPoint) SRID() int

SRID Returns SRID of point

func (*GeoPoint) SetSRID 

func (gp *GeoPoint) SetSRID(srid int)

SetSRID Sets SRID for point

type HmmProbabilities 

type HmmProbabilities struct {
	// contains filtered or unexported fields
}

HmmProbabilities Parameters used in evaluating of Normal Distribution and Exponentional Distribution

func HmmProbabilitiesDefault 

func HmmProbabilitiesDefault() *HmmProbabilities

HmmProbabilitiesDefault Constructor for creating HmmProbabilities with default values Sigma - standard deviation of the normal distribution [m] used for modeling the GPS error Beta - beta parameter of the exponential distribution used for modeling transition probabilities

func NewHmmProbabilities 

func NewHmmProbabilities(sigma, beta float64) *HmmProbabilities

NewHmmProbabilities Constructor for creating HmmProbabilities with provided values

func (*HmmProbabilities) EmissionLogProbability 

func (hp *HmmProbabilities) EmissionLogProbability(value float64) float64

EmissionLogProbability Evaluate emission probability (log-normal distribution is used)

func (*HmmProbabilities) EmissionProbability 

func (hp *HmmProbabilities) EmissionProbability(value float64) float64

EmissionProbability Evaluate emission probability (normal distribution is used). Absolute distance [m] between GPS measurement and map matching candidate.

func (*HmmProbabilities) TransitionLogProbability 

func (hp *HmmProbabilities) TransitionLogProbability(routeLength, linearDistance, timeDiff float64) (float64, error)

TransitionLogProbability Evaluate transition probability (log-exponential distribution is used)

func (*HmmProbabilities) TransitionProbability 

func (hp *HmmProbabilities) TransitionProbability(routeLength, linearDistance, timeDiff float64) (float64, error)

TransitionProbability Evaluate transition probability (exponential distribution is used)

type Isochrone added in v0.5.0 

type Isochrone struct {
	Vertex *Vertex
	Cost   float64
}

type IsochronesResult added in v0.5.0 

type IsochronesResult []*Isochrone

IsochronesResult Representation of isochrones algorithm's output

type MapEngine 

type MapEngine struct {
	// contains filtered or unexported fields
}

MapEngine Engine for solving finding shortest path and KNN problems edges - set of edges (map[from_vertex]map[to_vertex]Edge) s2Storage - datastore for B-tree. It is used for solving KNN problem s2StorageVertices - datastore for graph vertices (with geometry property) graph - Graph(E,V). It wraps ch.Graph (see https://github.com/LdDl/ch/blob/master/graph.go#L17). It used for solving finding shortest path problem.

func NewMapEngine 

func NewMapEngine(storageLevel int, degree int) *MapEngine

NewMapEngine Returns pointer to created MapEngine with provided parameters 

storageLevel - level for S2
degree - degree of b-tree

func NewMapEngineDefault 

func NewMapEngineDefault() *MapEngine

NewMapEngineDefault Returns pointer to created MapEngine with default parameters

type MapMatcher 

type MapMatcher struct {
	// contains filtered or unexported fields
}

MapMatcher Engine for solving map matching problem 

hmmParams - parameters of Hidden Markov Model
engine - wrapper around MapEngine (for KNN and finding shortest path problems)

func NewMapMatcher 

func NewMapMatcher(props *HmmProbabilities, edgesFilename string) (*MapMatcher, error)

NewMapMatcher Returns pointer to created MapMatcher with provided parameters 

props - parameters of Hidden Markov Model

func NewMapMatcherDefault 

func NewMapMatcherDefault() *MapMatcher

NewMapMatcherDefault Returns pointer to created MapMatcher with default parameters

func (*MapMatcher) FindIsochrones added in v0.5.0 

func (matcher *MapMatcher) FindIsochrones(source *GPSMeasurement, maxCost float64, maxNearestRadius float64) (IsochronesResult, error)

FindIsochrones Find shortest path between two obserations (not necessary GPS points). 

NOTICE: this function snaps point to only one nearest vertex (without multiple candidates for provided point)
source - source for outcoming isochrones
maxCost - max cost restriction for single isochrone line
maxNearestRadius - max radius of search for nearest vertex

func (*MapMatcher) FindShortestPath added in v0.3.0 

func (matcher *MapMatcher) FindShortestPath(source, target *GPSMeasurement, statesRadiusMeters float64) (MatcherResult, error)

FindShortestPath Find shortest path between two obserations (not necessary GPS points). 

NOTICE: this function snaps point to nearest edges simply (without multiple 'candidates' for each observation)
gpsMeasurements - Two observations
statesRadiusMeters - maximum radius to search nearest polylines

func (*MapMatcher) PrepareViterbi 

func (matcher *MapMatcher) PrepareViterbi(obsStates map[int]*CandidateLayer, routeLengths map[int]map[int]float64, gpsMeasurements []*GPSMeasurement) (*viterbi.Viterbi, error)

PrepareViterbi Prepares engine for doing Viterbi's algorithm (see https://github.com/LdDl/viterbi/blob/master/viterbi.go#L25) 

states - set of States
gpsMeasurements - set of Observations

func (*MapMatcher) Run 

func (matcher *MapMatcher) Run(gpsMeasurements []*GPSMeasurement, statesRadiusMeters float64, maxStates int) (MatcherResult, error)

Run Do magic 

gpsMeasurements - Observations
statesRadiusMeters - maximum radius to search nearest polylines
maxStates - maximum of corresponding states

type MatcherResult 

type MatcherResult struct {
	Observations []*ObservationResult
	Probability  float64
	Path         s2.Polyline
	VerticesPath []int64
}

MatcherResult Representation of map matching algorithm's output 

Observations - set of ObservationResult
Probability - probability got from Viterbi's algotithm
Path - final path as s2.Polyline
VerticesPath - IDs of graph vertices corresponding to traveled path

type NearestObject 

type NearestObject struct {
	// contains filtered or unexported fields
}

NearestObject Nearest object to given point 

edgeID - unique identifier
distanceTo - distance to object

type ObservationResult 

type ObservationResult struct {
	Observation *GPSMeasurement
	MatchedEdge Edge
}

ObservationResult Representation of gps measurement matched to G(v,e) 

Observation - gps measurement itself
MatchedEdge - edge in G(v,e) corresponding to current gps measurement

type RoadPosition 

type RoadPosition struct {
	RoadPositionID int
	GraphEdge      *Edge
	GraphVertex    int64
	Projected      *GeoPoint
	// contains filtered or unexported fields
}

RoadPosition Representation of state (in terms of Hidden Markov Model) 

ID - unique identifier of state
GraphEdge - pointer to closest edge in graph
GraphVertex  - indentifier of closest vertex
Projected - point (Observation) project onto edge, pointer to GeoPoint
beforeProjection - distance from starting point to projected one
afterProjection - distance from projected point to last one
next - index of the next vertex in s2.Polyline after the projected point

func NewRoadPositionFromLonLat 

func NewRoadPositionFromLonLat(stateID int, graphVertex int64, e *Edge, lon, lat float64, srid ...int) *RoadPosition

NewRoadPositionFromLonLat Returns pointer to created State 

stateID - unique identifier for state
graphVertex - indentifier of vertex which is closest to Observation
e - pointer to Edge
lon - longitude (X for SRID = 0)
lat - latitude (Y for SRID = 0)
srid - SRID (see https://en.wikipedia.org/wiki/Spatial_reference_system)

func NewRoadPositionFromS2LatLng 

func NewRoadPositionFromS2LatLng(stateID int, graphVertex int64, e *Edge, latLng *s2.LatLng, srid ...int) *RoadPosition

NewRoadPositionFromS2LatLng Returns pointer to created State 

stateID - unique identifier for state
graphVertex - indentifier of vertex which is closest to Observation
e - pointer to Edge
lon - longitude (X for SRID = 0)
lat - latitude (Y for SRID = 0)
srid - SRID (see https://en.wikipedia.org/wiki/Spatial_reference_system)

func (RoadPosition) ID 

func (state RoadPosition) ID() int

ID Method to fit interface State (see https://github.com/LdDl/viterbi/blob/master/viterbi.go#L9)

func (RoadPosition) String 

func (state RoadPosition) String() string

String Pretty format for State

type RoadPositions 

type RoadPositions []*RoadPosition

RoadPositions Set of states

type S2Storage 

type S2Storage struct {
	*btree.BTree
	// contains filtered or unexported fields
}

S2Storage Spatial datastore 

storageLevel - level for S2
edges - map of edges
BTree - b-tree (wraps)

func NewS2Storage 

func NewS2Storage(storageLevel int, degree int) *S2Storage

NewS2Storage Returns pointer to created S2Storage 

storageLevel - level for S2
degree - degree of b-tree

func (*S2Storage) AddEdge 

func (storage *S2Storage) AddEdge(edgeID uint64, edge *Edge) error

AddEdge Add edge (polyline) to storage 

edgeID - unique identifier
edge - edge

func (*S2Storage) NearestNeighborsInRadius 

func (storage *S2Storage) NearestNeighborsInRadius(pt s2.Point, radius float64, n int) ([]NearestObject, error)

NearestNeighborsInRadius Returns edges in radius with max objects restriction (KNN) 

pt - s2.Point
radius - radius of search
n - first N closest edges

func (*S2Storage) SearchInRadius 

func (storage *S2Storage) SearchInRadius(pt s2.Point, radius float64) (map[uint64]float64, error)

SearchInRadius Returns edges in radius 

pt - s2.Point
radius - radius of search

func (*S2Storage) SearchInRadiusLonLat 

func (storage *S2Storage) SearchInRadiusLonLat(lon, lat float64, radius float64) (map[uint64]float64, error)

SearchInRadiusLonLat Returns edges in radius 

lon - longitude
lat - latitude
radius - radius of search

type Vertex added in v0.5.0 

type Vertex struct {
	ID int64
	*s2.Point
}

Vertex Representation of node on a road (vertex in graph) 

ID - unique identifier (user defined, should be contained in parent graph)
Point - geometry of vertex, pointer to s2.Point (wrapper)

Source Files

View all Source files

Directories

Path Synopsis
cmd
horizon
codes
docs

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.