horizon

package module
v0.3.6-0...-c2dce21 Latest Latest
Warning

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

 Go to latest Published: Oct 25, 2020 License: Apache-2.0 Imports: 17 Imported by: 0

README

Horizon v0.3.5 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

notice: targeted for Linux users (no Windows/OSX instructions currenlty)
go get -u github.com/LdDl/horizon/...
go install github.com/LdDl/horizon/...

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 get github.com/LdDl/ch
go install github.com/LdDl/ch/...

    • 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

  3. Compress *.osm file via osmconvert. Drop author and version tags also (those not necessary for map matching).

    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 those default values. We are going to extract only edges adapted for cars also .

    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

  5. Start horizon server. Provide bind address, port, filename for road graph, σ 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 '{"maxStates":5,"stateRadius":7.0,"gps":[{"tm":"2020-03-11T00:00:00","lonLat":[37.601249363208915,55.745374309126895]},{"tm":"2020-03-11T00:00:02","lonLat":[37.600552781226014,55.7462238201015]},{"tm":"2020-03-11T00:00:04","lonLat":[37.59995939657391,55.747450858855984]},{"tm":"2020-03-11T00:00:06","lonLat":[37.60052698189332,55.7480171714195]},{"tm":"2020-03-11T00:00:08","lonLat":[37.600655978556816,55.748728680680564]},{"tm":"2020-03-11T00:00:10","lonLat":[37.600372185897115,55.74945469716283]},{"tm":"2020-03-11T00:00:12","lonLat":[37.600694677555865,55.75052191686339]},{"tm":"2020-03-11T00:00:14","lonLat":[37.600965570549214,55.751371315759044]},{"tm":"2020-03-11T00:00:16","lonLat":[37.600926871550165,55.752634490168425]},{"tm":"2020-03-11T00:00:18","lonLat":[37.60038508556347,55.75559625596534]}]}'

    For shortest path finding (notice: 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 '{"stateRadius":10.0,"gps":[{"lonLat":[37.601249363208915,55.745374309126895]},{"lonLat":[37.600926871550165,55.752634490168425]}]}'

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

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
  • moments.js for Front-end - moment.js. License is MIT

License

You can check it here

Documentation

Index

Constants

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

Variables

This section is empty.

Functions

func ExponentialDistribution 

func ExponentialDistribution(beta, x float64) float64

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

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 

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 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 graph - Graph(E,V). It wraps ch.Graph (see https://github.com/chentoz/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, graphFileName 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) FindShortestPath 

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/chentoz/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
}

MatcherResult Representation of map mathicng algorithm's output 

Observations - set of ObservationResult
Probability - probability got from Viterbi's algotithm
Path - final path as s2.Polyline

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
}

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

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

Source Files

View all Source files

Directories

Path Synopsis
cmd
horizon

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.