common

package
v1.1.0 Latest Latest
Warning

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

 Go to latest Published: Nov 27, 2022 License: MIT Imports: 17 Imported by: 0

Documentation

Index

Constants

View Source 
const OSM_INDEX_SCALE = 2
View Source 
const VITERBI2_GRANULARITY = 50
View Source 
const VITERBI2_MODE = "new"
View Source 
const VITERBI2_SIGMA = 30
View Source 
const VITERBI2_START_TOLERANCE = 100
View Source 
const VITERBI2_THREADS = 36
View Source 
const VITERBI_NORMALIZE_DELTA time.Duration = time.Second
View Source 
const VITERBI_SIGMA = 25

Variables

View Source 
var HIGHWAY_BLACKLIST []string = []string{
	"pedestrian",
	"footway",
	"bridleway",
	"steps",
	"path",
	"sidewalk",
	"cycleway",
	"proposed",
	"construction",
	"bus_stop",
	"crossing",
	"elevator",
	"emergency_access_point",
	"escape",
	"give_way",
}

Functions

func CreateSVG 

func CreateSVG(fname string, elements [][]Boundable, options SVGOptions) error

func DecodeOSM 

func DecodeOSM(path string, options OSMOptions, f func(v interface{})) error

func DrawLineOnCells 

func DrawLineOnCells(startX int, startY int, endX int, endY int, maxX int, maxY int) [][2]int

Use Bresenham's algorithm to get indices of cells to draw a line.

func IsOSMBlacklisted 

func IsOSMBlacklisted(highway string) bool

func IsOSMBlacklistedWithList 

func IsOSMBlacklistedWithList(highway string, blacklist []string) bool

func KDE 

func KDE(traces Traces, cellSize float64, sigma float64) [][]float64

func NormalizeTraces 

func NormalizeTraces(traces []*Trace)

func RtreegoRect 

func RtreegoRect(r Rectangle) *rtreego.Rect

func SaveChicagoTraces 

func SaveChicagoTraces(tracePath string, traces Traces) error

func SaveKharitaTraces 

func SaveKharitaTraces(fname string, traces Traces) error

func SaveTraces 

func SaveTraces(tracePath string, traces Traces) error

func VisualizeGraphs 

func VisualizeGraphs(scale float64, fname string, graphs []*Graph, traces []*Trace) error

func Viterbi 

func Viterbi(graph *Graph, traces []*Trace, tolerance float64)

func Viterbi2 

func Viterbi2(traces []*Trace, graph *Graph, opts Viterbi2Options) (edgeHits map[int]int)

Map match each trace in traces to the road network specified by graph. Returns edgeHits, a map from edge ID to the number of times the edge is passed by a trace.

Types

type AstarParams 

type AstarParams struct {
	// maximum distance to travel from src
	MaxDistance float64
}

type Boundable 

type Boundable interface {
	Bounds() Rectangle
}

type CMTOptions 

type CMTOptions struct {
	SetMetadata bool
	Limit       int
	CheckFunc   func(tripID int, t time.Time, p Point, speed float64, heading float64) bool
	TimeBreak   time.Duration
}

type ColoredBoundable 

type ColoredBoundable struct {
	Boundable Boundable
	Color     string
}

func (ColoredBoundable) Bounds 

func (b ColoredBoundable) Bounds() Rectangle

type Edge 

type Edge struct {
	ID  int
	Src *Node
	Dst *Node
}

func (*Edge) AngleTo 

func (edge *Edge) AngleTo(other *Edge) float64

func (*Edge) ClosestPos 

func (edge *Edge) ClosestPos(point Point) EdgePos

func (*Edge) GetOpposite 

func (edge *Edge) GetOpposite() *Edge

func (*Edge) IsAdjacent 

func (edge *Edge) IsAdjacent(other *Edge) bool

func (*Edge) Segment 

func (edge *Edge) Segment() Segment

func (*Edge) String 

func (edge *Edge) String() string

func (*Edge) Vector 

func (edge *Edge) Vector() Point

type EdgePos 

type EdgePos struct {
	Edge     *Edge
	Position float64
}

func (EdgePos) Point 

func (ep EdgePos) Point() Point

type EmbeddedImage 

type EmbeddedImage struct {
	Src   Point
	Dst   Point
	Image string
}

func (EmbeddedImage) Bounds 

func (img EmbeddedImage) Bounds() Rectangle

type FollowParams 

type FollowParams struct {
	// Source, only one should be specified.
	SourceNodes []*Node
	SourcePos   EdgePos

	// Distance to travel along graph from source.
	Distance float64

	// If true, don't search forwards.
	NoForwards bool

	// If true, search backwards (in addition to searching forwards).
	Backwards bool

	// If set, will be populated with nodes that we pass during following.
	SeenNodes map[int]bool

	// If set, we will stop immediately before these nodes rather than passing them.
	StopNodes map[int]bool
}

type Graph 

type Graph struct {
	Nodes []*Node
	Edges []*Edge
}

func GraphFromEdges 

func GraphFromEdges(edges []*Edge) *Graph

func LoadOSM 

func LoadOSM(path string, bounds Rectangle) (*Graph, error)

func LoadOSMMultiple 

func LoadOSMMultiple(path string, regions []Rectangle, options OSMOptions) ([]*Graph, error)

func LoadOSMMultiple2 

func LoadOSMMultiple2(path string, regions []Rectangle, options OSMOptions) ([]*Graph, error)

New version improves performance when there are many bounding boxes.

func ReadAhmedMap 

func ReadAhmedMap(verticesFname string, edgesFname string) (*Graph, error)

func ReadChicagoMap 

func ReadChicagoMap(fname string) (*Graph, error)

func ReadDaviesMap 

func ReadDaviesMap(verticesFname string, edgesFname string) (*Graph, error)

func ReadEdelkampMap 

func ReadEdelkampMap(fname string) (*Graph, error)

func ReadGraph 

func ReadGraph(fname string) (*Graph, error)

func ReadKharitaMap 

func ReadKharitaMap(fname string) (*Graph, error)

func (*Graph) AddBidirectionalEdge 

func (graph *Graph) AddBidirectionalEdge(v1 *Node, v2 *Node) [2]*Edge

func (*Graph) AddEdge 

func (graph *Graph) AddEdge(src *Node, dst *Node) *Edge

func (*Graph) AddNode 

func (graph *Graph) AddNode(point Point) *Node

func (*Graph) Astar 

func (graph *Graph) Astar(src *Node, dst *Node, params AstarParams) ShortestPathResult

func (*Graph) Bounds 

func (graph *Graph) Bounds() Rectangle

func (*Graph) Clone 

func (graph *Graph) Clone() *Graph

func (*Graph) FilterEdges 

func (graph *Graph) FilterEdges(badEdges map[int]bool) *Graph

func (*Graph) FilterEdgesWithMaps 

func (graph *Graph) FilterEdgesWithMaps(badEdges map[int]bool) (*Graph, map[int]*Node, map[int]*Edge)

func (*Graph) FindEdge 

func (graph *Graph) FindEdge(src *Node, dst *Node) *Edge

func (*Graph) Follow 

func (graph *Graph) Follow(params FollowParams) []EdgePos

Find locations after traveling along the graph from pos for distance.

func (*Graph) GetRoadSegmentGraph 

func (graph *Graph) GetRoadSegmentGraph() (*Graph, map[int]RoadSegment, map[int]*Node)

func (*Graph) GetRoadSegments 

func (graph *Graph) GetRoadSegments() []RoadSegment

Get road segments, i.e., sequences of edges between junctions. Junctions are vertices where the number of incident edges != 2. This function only works for bidirectional graphs.

func (*Graph) GetSubgraphInRect 

func (graph *Graph) GetSubgraphInRect(r Rectangle) *Graph

func (*Graph) GridIndex 

func (graph *Graph) GridIndex(gridSize float64) GraphGridIndex

func (*Graph) LonLatToMeters 

func (graph *Graph) LonLatToMeters(origin Point)

func (*Graph) MakeBidirectional 

func (graph *Graph) MakeBidirectional()

func (*Graph) MetersToLonLat 

func (graph *Graph) MetersToLonLat(origin Point)

func (*Graph) Rtree 

func (graph *Graph) Rtree() Rtree

func (*Graph) ShortestDistancesFromSource 

func (graph *Graph) ShortestDistancesFromSource(src *Node) map[int]float64

returns shortest distances from the given source node to all vertices in the graph

func (*Graph) ShortestPath 

func (graph *Graph) ShortestPath(src *Node, params ShortestPathParams) ShortestPathResult

func (*Graph) SplitEdge 

func (graph *Graph) SplitEdge(edge *Edge, length float64) *Edge

func (*Graph) Write 

func (graph *Graph) Write(fname string) error

type GraphGridIndex 

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

func (GraphGridIndex) Search 

func (idx GraphGridIndex) Search(rect Rectangle) []*Edge

type GridIndex 

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

func NewGridIndex 

func NewGridIndex(gridSize float64) *GridIndex

func (GridIndex) Insert 

func (idx GridIndex) Insert(id int, rect Rectangle)

func (GridIndex) Search 

func (idx GridIndex) Search(rect Rectangle) []int

type Line 

type Line struct {
	A Point
	B Point
}

func (Line) ProjectPoint 

func (line Line) ProjectPoint(point Point) Point

type Node 

type Node struct {
	ID    int
	Point Point
	In    []*Edge
	Out   []*Edge
}

func (*Node) RemoveEdge 

func (node *Node) RemoveEdge(edge *Edge)

func (*Node) String 

func (node *Node) String() string

type OSMOptions 

type OSMOptions struct {
	Verbose         bool
	EdgeWidths      []map[int]float64
	NoParking       bool
	NoTunnels       bool
	LayerEdges      []map[int]bool
	EdgeTags        []map[int]map[string]string
	NodeTags        []map[int]map[string]string
	OneWay          bool
	OnlyMotorways   bool
	MotorwayEdges   []map[int]bool
	TunnelEdges     []map[int]bool
	Bytes           []byte
	CustomBlacklist []string
	CustomWhitelist []string
	IncludeRailway  bool
}

type Observation 

type Observation struct {
	Time     time.Time
	Point    Point
	Metadata map[string]interface{}
}

func (*Observation) GetMetadata 

func (obs *Observation) GetMetadata(k string) interface{}

func (*Observation) SetMetadata 

func (obs *Observation) SetMetadata(k string, val interface{})

type Point 

type Point struct {
	X float64
	Y float64
}

func RDP 

func RDP(points []Point, epsilon float64) []Point

func (Point) Add 

func (point Point) Add(other Point) Point

func (Point) AngleTo 

func (point Point) AngleTo(other Point) float64

func (Point) Bounds 

func (point Point) Bounds() Rectangle

func (Point) Cross 

func (point Point) Cross(other Point) float64

computes the z-coordinate of the cross product, assuming that both points are on the z=0 plane

func (Point) Distance 

func (point Point) Distance(other Point) float64

func (Point) Dot 

func (point Point) Dot(other Point) float64

func (Point) LonLatToMeters 

func (point Point) LonLatToMeters(origin Point) Point

func (Point) Magnitude 

func (point Point) Magnitude() float64

func (Point) MetersToLonLat 

func (point Point) MetersToLonLat(origin Point) Point

Converts from meters back to longitude/latitude origin should be the same point passed to LonLatToMeters (origin should be longitude/latitude)

func (Point) MulPairwise 

func (point Point) MulPairwise(other Point) Point

func (Point) Rectangle 

func (point Point) Rectangle() Rectangle

func (Point) RectangleTol 

func (point Point) RectangleTol(tol float64) Rectangle

func (Point) Scale 

func (point Point) Scale(f float64) Point

func (Point) SignedAngle 

func (point Point) SignedAngle(other Point) float64

func (Point) Sub 

func (point Point) Sub(other Point) Point

type Polygon 

type Polygon []Point

func GetConvexHull 

func GetConvexHull(points []Point) Polygon

from https://github.com/Ch3ck/algo/blob/master/convexHull/convexHull.go

func (Polygon) Bounds 

func (poly Polygon) Bounds() Rectangle

func (Polygon) Contains 

func (poly Polygon) Contains(p Point) bool

Ray casting algorithm (https://stackoverflow.com/questions/217578/how-can-i-determine-whether-a-2d-point-is-within-a-polygon). We count the number of polygon segments that a ray from outside the polygon to p intersects. even -> p is outside, odd -> p is inside

func (Polygon) Distance 

func (poly Polygon) Distance(p Point) float64

func (Polygon) SegmentIntersections 

func (poly Polygon) SegmentIntersections(segment Segment) []Point

func (Polygon) Segments 

func (poly Polygon) Segments() []Segment

type Rectangle 

type Rectangle struct {
	Min Point
	Max Point
}
var EmptyRectangle Rectangle = Rectangle{
	Min: Point{math.Inf(1), math.Inf(1)},
	Max: Point{math.Inf(-1), math.Inf(-1)},
}

func Rect 

func Rect(sx, sy, ex, ey float64) Rectangle

func (Rectangle) AddTol 

func (rect Rectangle) AddTol(tol float64) Rectangle

func (Rectangle) Area 

func (rect Rectangle) Area() float64

func (Rectangle) Bounds 

func (rect Rectangle) Bounds() Rectangle

func (Rectangle) Center 

func (rect Rectangle) Center() Point

func (Rectangle) Contains 

func (rect Rectangle) Contains(point Point) bool

func (Rectangle) ContainsRect 

func (rect Rectangle) ContainsRect(other Rectangle) bool

func (Rectangle) Diagonal 

func (rect Rectangle) Diagonal() float64

func (Rectangle) Extend 

func (rect Rectangle) Extend(point Point) Rectangle

func (Rectangle) ExtendRect 

func (rect Rectangle) ExtendRect(other Rectangle) Rectangle

func (Rectangle) IOU 

func (rect Rectangle) IOU(other Rectangle) float64

func (Rectangle) Intersection 

func (rect Rectangle) Intersection(other Rectangle) Rectangle

func (Rectangle) Intersects 

func (rect Rectangle) Intersects(other Rectangle) bool

func (Rectangle) Lengths 

func (rect Rectangle) Lengths() Point

func (Rectangle) ToPolygon 

func (rect Rectangle) ToPolygon() Polygon

type RoadSegment 

type RoadSegment struct {
	ID            int
	Edges         []*Edge
	EdgeDistances []float64
}

func NewRoadSegment 

func NewRoadSegment(edges []*Edge) (RoadSegment, error)

func (RoadSegment) Bounds 

func (rs RoadSegment) Bounds() Rectangle

func (RoadSegment) ClosestPos 

func (rs RoadSegment) ClosestPos(p Point) EdgePos

func (RoadSegment) DistanceOfEdge 

func (rs RoadSegment) DistanceOfEdge(edge *Edge) float64

func (RoadSegment) DistanceToEdge 

func (rs RoadSegment) DistanceToEdge(t float64) *Edge

func (RoadSegment) DistanceToIndex 

func (rs RoadSegment) DistanceToIndex(t float64) int

func (RoadSegment) Dst 

func (rs RoadSegment) Dst() *Node

func (RoadSegment) Length 

func (rs RoadSegment) Length() float64

func (RoadSegment) PosAtFactor 

func (rs RoadSegment) PosAtFactor(t float64) EdgePos

func (RoadSegment) Src 

func (rs RoadSegment) Src() *Node

type Rtree 

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

func (Rtree) Search 

func (rtree Rtree) Search(rect Rectangle) []*Edge

type SVGOptions 

type SVGOptions struct {
	Scale       float64
	Zoom        float64
	ScaleX      float64
	ScaleY      float64
	Sparse      float64
	Bounds      Rectangle
	Blur        float64
	StrokeWidth float64
	Color       string
	Unflip      bool
}

type Segment 

type Segment struct {
	Start Point
	End   Point
}

func (Segment) AngleTo 

func (segment Segment) AngleTo(other Segment) float64

func (Segment) Bounds 

func (segment Segment) Bounds() Rectangle

func (Segment) Distance 

func (segment Segment) Distance(point Point) float64

func (Segment) DistanceToSegment 

func (segment Segment) DistanceToSegment(other Segment) float64

2D implementation of "On fast computation of distance between line segments" (V. Lumelsky)

func (Segment) Intersection 

func (segment Segment) Intersection(other Segment) *Point

from https://github.com/paulmach/go.geo/blob/master/line.go

func (Segment) Length 

func (segment Segment) Length() float64

func (Segment) Line 

func (segment Segment) Line() Line

func (Segment) PointAtFactor 

func (segment Segment) PointAtFactor(factor float64, normalized bool) Point

func (Segment) Project 

func (segment Segment) Project(point Point, normalized bool) float64

func (Segment) ProjectPoint 

func (segment Segment) ProjectPoint(point Point) Point

func (Segment) ProjectWithWidth 

func (segment Segment) ProjectWithWidth(point Point, width float64) Point

func (Segment) Sample 

func (segment Segment) Sample(d float64) []Point

sample the segment discretely at some frequency (in terms of distance between points)

func (Segment) Vector 

func (segment Segment) Vector() Point

type ShortestPathParams 

type ShortestPathParams struct {
	// maximum distance to travel from src
	MaxDistance float64

	// terminate search once we reach any of these nodes
	StopNodes []*Node

	// override edge length
	EdgeLengths map[int]float64
}

func (ShortestPathParams) IsStopNode 

func (params ShortestPathParams) IsStopNode(node *Node) bool

type ShortestPathResult 

type ShortestPathResult struct {
	Distances    map[int]float64
	Remaining    map[int]bool
	Backpointers map[int]int
	// contains filtered or unexported fields
}

func (ShortestPathResult) GetFullPathTo 

func (result ShortestPathResult) GetFullPathTo(node *Node) []*Node

func (ShortestPathResult) GetPathTo 

func (result ShortestPathResult) GetPathTo(node *Node) []*Node

type SvgLabel 

type SvgLabel struct {
	Point Point
	Text  string
}

func (SvgLabel) Bounds 

func (b SvgLabel) Bounds() Rectangle

type Trace 

type Trace struct {
	Name         string
	Observations []*Observation
}

func (*Trace) LastObservation 

func (trace *Trace) LastObservation() *Observation

func (*Trace) LonLatToMeters 

func (trace *Trace) LonLatToMeters(origin Point)

type Traces 

type Traces []*Trace

func LoadCMTTraces 

func LoadCMTTraces(tracePath string, rect *Rectangle, options CMTOptions) (Traces, error)

func LoadCartelTraces 

func LoadCartelTraces(tracePath string) (Traces, error)

func LoadChicagoTraces 

func LoadChicagoTraces(tracePath string) (Traces, error)

func LoadTraces 

func LoadTraces(tracePath string) (Traces, error)

func (Traces) Bounds 

func (traces Traces) Bounds() Rectangle

func (Traces) LonLatToMeters 

func (traces Traces) LonLatToMeters(origin Point)

Convert coordinate system from longitude/latitude to Cartesian meters. This assumes that the GPS sequences cover a small region so that curvature can be ignored.

type Viterbi2Options 

type Viterbi2Options struct {
	Granularity    float64
	Sigma          float64
	StartTolerance float64
	Threads        int

	// only compute edgeHits, do not store the map-matched data
	HitsOnly bool

	// a map from edge IDs to weight of the ID. If nil, the transition probabilities
	// are weighted based on the angle difference between the source and destination edges.
	EdgeWeights map[int]float64

	// use constant 0.5 weight if not at junction, and 0.05 if at junction
	// and also don't allow u-turn
	NewMode bool

	Output map[int][]EdgePos
}

func (Viterbi2Options) GetGranularity 

func (opts Viterbi2Options) GetGranularity() float64

func (Viterbi2Options) GetSigma 

func (opts Viterbi2Options) GetSigma() float64

func (Viterbi2Options) GetStartTolerance 

func (opts Viterbi2Options) GetStartTolerance() float64

func (Viterbi2Options) GetThreads 

func (opts Viterbi2Options) GetThreads() int

type WeightedBoundable 

type WeightedBoundable struct {
	Boundable Boundable
	Weight    float64
}

func (WeightedBoundable) Bounds 

func (wb WeightedBoundable) Bounds() Rectangle

type WidthBoundable 

type WidthBoundable struct {
	Boundable Boundable
	Width     float64
}

func (WidthBoundable) Bounds 

func (b WidthBoundable) Bounds() Rectangle

type WrappingBoundable 

type WrappingBoundable interface {
	Unwrap() Boundable
}

Source Files

View all Source files

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.