route

Documentation

Overview

Package route finds the shortest route between two points along a geometrical network (e.g., a road network). For now, all network links are assumed to be bi-directional (e.g., all roads are two-way).

Example

link1 := geom.LineString{
	geom.Point{X: 0, Y: 0},
	geom.Point{X: 0, Y: 1},
	geom.Point{X: 1, Y: 1},
	geom.Point{X: 8, Y: 1},
	geom.Point{X: 8, Y: 4},
} // Distance = 12
link2 := geom.LineString{
	geom.Point{X: 8, Y: 4}, // link2 beginning == link1 end
	geom.Point{X: 8, Y: -6},
} // Distance = 10
startingPoint := geom.Point{X: 0, Y: -1}
endingPoint := geom.Point{X: 6, Y: -6}
net := NewNetwork(Time)
net.AddLink(link1, 6)
net.AddLink(link2, 2)
route, distance, time, startDistance, endDistance :=
	net.ShortestRoute(startingPoint, endingPoint)
fmt.Println(route, distance, time, startDistance, endDistance)

Output:

[[{0 0} {0 1} {1 1} {8 1} {8 4}] [{8 4} {8 -6}]] 22 7 1 2

Index

• type MinimizeOption
• type Network
  • func NewNetwork(m MinimizeOption) *Network
  • func (net *Network) AddLink(l geom.LineString, speed float64)
  • func (net Network) Edge(u, v int64) graph.Edge
  • func (net Network) From(n int64) graph.Nodes
  • func (net Network) Has(n int64) bool
  • func (net Network) HasEdge(x, y int64) bool
  • func (net Network) HasEdgeBetween(xid, yid int64) bool
  • func (net Network) Node(id int64) graph.Node
  • func (net Network) Nodes() graph.Nodes
  • func (net Network) ShortestRoute(from, to geom.Point) (route geom.MultiLineString, distance, time, startDistance, endDistance float64)
  • func (net *Network) Weight(e graph.Edge) float64

Examples

• Package

Types

type MinimizeOption

type MinimizeOption float64

MinimizeOption specifies how the shortest route should be chosen.

const (
	// Distance specifies that we are looking to travel the minimum distance.
	Distance MinimizeOption = iota
	// Time specifies that we are looking to travel the minimum time.
	Time
)

type Network

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

A Network is a holder for network data (e.g., a road network)

func NewNetwork

func NewNetwork(m MinimizeOption) *Network

NewNetwork initializes a new Network where m determines how to choose the shortest route (either by Distance or Time).

func (*Network) AddLink

func (net *Network) AddLink(l geom.LineString, speed float64)

AddLink adds a new link l (which is a line string) to the Network, where speed is the speed traveled along the link and should have units that are compatible with the units of l (for instance, if l is in units of meters, and speed is in units of m/s, the time results will be in units of seconds).

func (Network) Edge

func (net Network) Edge(u, v int64) graph.Edge

Edge returns the edge from u to v if such an edge exists and nil otherwise. The node v must be directly reachable from u as defined by the From method. It is not intended for direct use in this package.

func (Network) From

func (net Network) From(n int64) graph.Nodes

From returns all nodes that can be reached directly from the given node. It is not intended for direct use in this package.

func (Network) Has

func (net Network) Has(n int64) bool

Has returns whether the node exists within the graph. It is not intended for direct use in this package.

func (Network) HasEdge

func (net Network) HasEdge(x, y int64) bool

HasEdge returns whether an edge exists between nodes x and y without considering direction. It is not intended for direct use in this package.

func (Network) HasEdgeBetween

func (net Network) HasEdgeBetween(xid, yid int64) bool

HasEdgeBetween returns whether an edge exists between nodes x and y without considering direction.

func (Network) Node

func (net Network) Node(id int64) graph.Node

func (Network) Nodes

func (net Network) Nodes() graph.Nodes

Nodes returns all the nodes in the graph. It is not intended for direct use in this package.

func (Network) ShortestRoute

func (net Network) ShortestRoute(from, to geom.Point) (
	route geom.MultiLineString, distance, time, startDistance, endDistance float64)

ShortestRoute calculates the shortest route along the network between the from and to points. It returns the route ("path"), the distance traveled along the route ("distance"), the time it would take travel along the route ("time"; this does not count time spent getting to and from the network), the distance traveled from the starting point to get to the nearest node (e.g., intersection) along the route ("startDistance") and the distance traveled to the ending point from the nearest node along the route ("endDistance"). This function does not change the Network, so multiple function calls can be run concurrently.

func (*Network) Weight

func (net *Network) Weight(e graph.Edge) float64

Weight returns the weight associated with this edge. It is not intended for direct use in this package.