horizon

package module
v0.7.0 Latest Latest
Warning

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

 Go to latest Published: Apr 23, 2025 License: Apache-2.0 Imports: 18 Imported by: 0

README

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

Demonstration:

Installation

Via go get:

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

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

    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,"state_radius":7.0,"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

      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,
"state_radius": 7.0,
"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 (note: edge selection based just on "first nearest found" method, so results may make you upset):

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

      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 '{
"state_radius": 10.0,
"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,"nearest_radius": 25.0, "lon_lat":[37.601249363208915,55.745374309126895]}' ; echo

      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,
"max_nearest_radius": 25.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:

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 (
	ViterbiDebug           = false
	ROUTE_LENGTH_THRESHOLD = 9_999_999_999.0
)
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 ExtractCutUpFrom added in v0.7.0 

func ExtractCutUpFrom(polyline s2.Polyline, projected s2.Point, projectedIdx int) (s2.Polyline, s2.Polyline)

ExtractCutUpFrom cuts geometry between neighbor of the projected point index in the polyline and last point

func ExtractCutUpTo added in v0.7.0 

func ExtractCutUpTo(polyline s2.Polyline, projected s2.Point, projectedIdx int) (s2.Polyline, s2.Polyline)

ExtractCutUpTo cuts geometry between very first point and neighbor of the projected point index in the polyline

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

func WithGPSTime added in v0.6.0 

func WithGPSTime(t time.Time) func(*GPSMeasurement)

WithGPSTime sets user defined time for GPS measurement

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 {
	*s2.Polyline
	Weight float64
	ID     int64
	Source int64
	Target int64
}

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 EdgeResult added in v0.6.0 

type EdgeResult struct {
	Geom   s2.Polyline
	Weight float64
	ID     int64
}

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(id int, lon, lat float64, srid int, options ...func(*GPSMeasurement)) *GPSMeasurement

NewGPSMeasurement Returns pointer to created GPSMeasurement 

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

func (*GeoPoint) String added in v0.6.0 

func (gp *GeoPoint) String() string

String Pretty print

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 []*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
}

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
	MatchedVertex      Vertex
	ProjectedPoint     s2.Point
	ProjectionPointIdx int
	NextEdges          []EdgeResult
}

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
MatchedVertex - stands for closest vertex to the observation
ProjectedPoint - projection onto the matched edge
ProjectedPointIdx - index of the point in polyline which follows projection point
NextEdges - set of leading edges up to next observation. Could be an empty array if observations are very close to each other or if it just last observation

type RoadPosition 

type RoadPosition struct {
	Projected *GeoPoint
	GraphEdge *Edge

	PickedGraphVertex  int64
	RoutingGraphVertex int64
	RoadPositionID     int
	// 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, pickedGraphVertex, routingGraphVertex int64, e *Edge, lon, lat float64, srid ...int) *RoadPosition

NewRoadPositionFromLonLat Returns pointer to created State 

stateID - unique identifier for state
pickedGraphVertex - indentifier of vertex which is closest to Observation
routingGraphVertex - indentifier of vertex which will be used in routing (initially it should match pickedGraphVertex in most cases)
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, pickedGraphVertex, routingGraphVertex int64, e *Edge, latLng *s2.LatLng, srid ...int) *RoadPosition

NewRoadPositionFromS2LatLng Returns pointer to created State 

stateID - unique identifier for state
pickedGraphVertex - indentifier of vertex which is closest to Observation
routingGraphVertex - indentifier of vertex which will be used in routing (initially it should match pickedGraphVertex in most cases)
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 {
	*s2.Point
	ID int64
}

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 command
codes
docs
rpc
docs
protos_pb

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.