1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
use crate::ResolutionMethod;
use crate::transition::candidate::{Candidate, CandidateId};
use crate::transition::{RoutingContext, Strategy, Trip, VirtualTail};
use geo::{Distance, Haversine};
use routers_network::{Entry, Metadata, Network};
pub trait TransitionStrategy<E, M, N>: for<'a> Strategy<TransitionContext<'a, E, M, N>> {}
impl<T, N, E, M> TransitionStrategy<E, M, N> for T where
T: for<'a> Strategy<TransitionContext<'a, E, M, N>>
{
}
#[derive(Clone, Debug)]
pub struct TransitionContext<'a, E, M, N>
where
M: Metadata + 'a,
E: Entry + 'a,
N: Network<E, M>,
{
/// The optimal path travelled between the
/// source candidate and target candidate, used
/// to determine trip complexity (and therefore
/// cost) often through heuristics such as
/// immediate and summative angular rotation.
pub optimal_path: Trip<E>,
/// A list of all OSM nodes pertaining to the optimal trip path.
pub map_path: &'a [E],
/// The source candidate indicating the edge and
/// position for which the path begins at.
pub source_candidate: &'a CandidateId,
/// The target candidate indicating the edge and
/// position for which the path ends at.
pub target_candidate: &'a CandidateId,
/// Further context to provide access to determine routing information,
/// such as node positions upon the map, and referencing other candidates.
pub routing_context: &'a RoutingContext<'a, E, M, N>,
/// The length between the layer nodes
pub layer_width: f64,
/// The requested [resolution method](ResolutionMethod) by which the transition costing function
/// should attempt to cost (resolve) the two candidates.
pub requested_resolution_method: ResolutionMethod,
}
pub struct TransitionLengths {
/// The great circle distance between source and target
pub straightline_distance: f64,
/// The path of the optimal route between candidates
pub route_length: f64,
}
impl TransitionLengths {
/// Calculates the deviance in straightline distance to the length
/// of the entire route. Returns values between 0 and 1. Where values
/// closer to 1 represent more optimal distances, whilst those closer
/// to 0 represent less optimal distances.
///
/// The route length is defined as the cumulative distance between
/// nodes in the optimal transition path, plus the offsets into the
/// edges by which the candidates live.
///
/// The straightline distance is defined as the haversine (great circle)
/// distance between the two candidates.
///
/// Therefore, our deviance is defined as the ratio of straightline
/// distance to the route length, which measures how much farther
/// the actual route was than a virtual path directly between the candidates.
///
/// For example:
/// - If two candidates were `100m` apart, but had a most optimal route
/// between them of `130m`, the deviance would be `~0.77`.
/// - If two alternate candidates were `100m` apart but instead had an
/// optimal route between them of `250m`, the deviance is `0.4`.
///
/// Note that a lower deviance score means the values are less aligned.
#[inline]
pub fn deviance(&self) -> f64 {
let numer = self.straightline_distance / 4.0;
let demon = self.route_length - self.straightline_distance;
(numer / demon).abs().clamp(0.0, 1.0)
}
}
impl<E, M, N> TransitionContext<'_, E, M, N>
where
E: Entry,
M: Metadata,
N: Network<E, M>,
{
/// Obtains the source [candidate](Candidate) from the context.
pub fn source_candidate(&self) -> Candidate<E> {
self.routing_context
.candidate(self.source_candidate)
.expect("source candidate not found in routing context")
}
/// Obtains the target [candidate](Candidate) from the context.
pub fn target_candidate(&self) -> Candidate<E> {
self.routing_context
.candidate(self.target_candidate)
.expect("target candidate not found in routing context")
}
/// Returns a [candidate](Candidate) pair of (source, target)
pub fn candidates(&self) -> (Candidate<E>, Candidate<E>) {
(self.source_candidate(), self.target_candidate())
}
/// Calculates the total offset, of both source and target positions within the context,
/// considering the resolution method requested
pub fn total_offset(&self, source: &Candidate<E>, target: &Candidate<E>) -> Option<f64> {
match self.requested_resolution_method {
ResolutionMethod::Standard => {
// Also validate that this isn't the only way we need to calculate the distances,
// since its perfectly possible to need the other way around (virt. tail) depending on which
// invariants are upheld upstream
let inner_offset = source.offset(self.routing_context, VirtualTail::ToTarget)?;
let outer_offset = target.offset(self.routing_context, VirtualTail::ToSource)?;
Some(inner_offset + outer_offset)
}
ResolutionMethod::DistanceOnly => {
Some(Haversine.distance(source.position, target.position))
}
}
}
/// Returns the [`TransitionLengths`] of the context.
pub fn lengths(&self) -> Option<TransitionLengths> {
let (source, target) = self.candidates();
let offset = self.total_offset(&source, &target)?;
let route_length = self.optimal_path.length() + offset;
let straightline_distance = Haversine.distance(source.position, target.position);
Some(TransitionLengths {
straightline_distance,
route_length,
})
}
}