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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
pub mod emission {
use std::ops::{Div, Neg};
use crate::transition::*;
/// 5 meters (85th% GPS error)
const DEFAULT_EMISSION_ERROR: f64 = 25.0;
/// Calculates the emission cost of a candidate relative
/// to its source node.
///
/// ## Calculation
///
/// The emission cost is defined by the relative distance
/// from the source position, given some "free" zone, known
/// as the [`emission_error`](#field.emission_error). Within this error, any
/// candidate is considered a no-cost transition as the likelihood
/// the position is within the boundary is equal within this radius.
///
/// The relative calculation is given simply below, where `distance`
/// defines the haversine distancing function between two Lat/Lng positions.
///
/// ```math
/// relative(source, candidate) = err / distance(source, candidate)
/// ```
///
/// The cost derived is given as the square root of the reciprocal of
/// the relative distance.
///
/// ```math
/// cost(source, candidate) = sqrt(1 / relative(source, candidate))
/// ```
///
/// There exist values within the strategy
/// implementation which define how "aggressive" the falloff is.
/// These hyperparameters may need to be tuned in order to calculate for nodes
/// which have large error. Alternatively, providing your own emission error
/// is possible too.
pub struct DefaultEmissionCost {
/// The free radius around which emissions cost the same, to provide
/// equal opportunity to nodes within the expected GPS error.
///
/// Default: [`DEFAULT_EMISSION_ERROR`]
pub emission_error: f64,
}
impl Default for DefaultEmissionCost {
fn default() -> Self {
DefaultEmissionCost {
emission_error: DEFAULT_EMISSION_ERROR,
}
}
}
impl<'a> Strategy<EmissionContext<'a>> for DefaultEmissionCost {
type Cost = f64;
const ZETA: f64 = 1.;
const BETA: f64 = 1.;
#[inline(always)]
fn calculate(&self, context: EmissionContext<'a>) -> Option<Self::Cost> {
Some(context.distance.div(self.emission_error).sqrt().neg().exp())
}
}
}
pub mod transition {
use crate::transition::*;
use routers_network::{Edge, Entry, Metadata, Network};
/// Calculates the transition cost between two candidates.
///
/// Involves the following "sub-heuristics" used to quantify
/// the trip "complexity" and travel "likelihood".
///
/// # Calculation
///
/// Using turn-costing, we calculate immediate and summative
/// angular rotation, and with deviance we determine a travel likelihood.
///
/// ## Turn Cost
/// We describe the summative angle, seen in the [`Trip::total_angle`]
/// function, as the total angular rotation exhibited by a trip.
/// We assume a high degree of rotation is not preferable, and trips
/// are assumed to take the most optimal path with the most reasonable
/// changes in trajectory, meaning many turns where few are possible
/// is discouraged.
///
/// We may then [amortize] this cost to calculate the immediately
/// exhibited angle. Or, alternatively expressed as the average angle
/// experienced
///
/// ```math
/// sum_angle(trip) = ∑(angles(trip))
/// imm_angle(trip) = sum_angle(trip) / len(trip)
///
/// turn_cost(trip) = imm_angle(trip)
/// ```
///
/// ## Deviance
/// Defines the variability between the trip length (in meters)
/// and the shortest great-circle distance between the two candidates.
///
/// This cost is low in segments which follow an optimal path, i.e. in
/// a highway, as it discourages alternate paths which may appear quicker
/// to traverse.
///
/// ```math
/// length(trip) = ∑(distance(segment))
/// deviance(trip, source, target) = length(trip) - distance(source, target)
/// ```
///
/// ### Total Cost
/// The total cost is combined as such.
///
/// ```math
/// cost(trip, s, t) = deviance(trip, s, t) + turn_cost(trip)
/// ```
///
/// [amortize]: https://en.wikipedia.org/wiki/Amortized_analysis
pub struct DefaultTransitionCost;
impl<'a, E, M, N> Strategy<TransitionContext<'a, E, M, N>> for DefaultTransitionCost
where
E: Entry,
M: Metadata,
N: Network<E, M>,
{
type Cost = f64;
const ZETA: f64 = 1.;
const BETA: f64 = 1.;
#[inline]
fn calculate(&self, context: TransitionContext<'a, E, M, N>) -> Option<Self::Cost> {
const EPSILON: f64 = 1e-6;
// Find the transition lengths (shortest path, trip length)
let lengths = context.lengths()?;
// Value in range [0, 1] (1=Low Cost, 0=High Cost)
let deviance = lengths.deviance().clamp(EPSILON, 1.0);
// Value in range [0, 1] (1=Low Cost, 0=High Cost)
let turn_cost = context.angular_complexity().clamp(EPSILON, 1.0);
// Value in range [0, 1] (1=Low Cost, 0=High Cost)
let class_continuity = {
let (
Candidate {
edge:
Edge {
weight: src_weight, ..
},
..
},
Candidate {
edge:
Edge {
weight: tgt_weight, ..
},
..
},
) = context.candidates();
src_weight as f64 / tgt_weight as f64
}
.clamp(EPSILON, 1.0);
Some((deviance * turn_cost * class_continuity).sqrt())
}
}
}
pub mod costing {
use super::{DefaultEmissionCost, DefaultTransitionCost};
use crate::costing::{
Costing, EmissionContext, EmissionStrategy, TransitionContext, TransitionStrategy,
};
use core::marker::PhantomData;
use routers_network::{Entry, Metadata, Network};
pub struct CostingStrategies<Emmis, Trans, E, M, N>
where
E: Entry,
M: Metadata,
N: Network<E, M>,
Emmis: EmissionStrategy,
Trans: TransitionStrategy<E, M, N>,
{
pub emission: Emmis,
pub transition: Trans,
_phantom: core::marker::PhantomData<E>,
_phantom2: core::marker::PhantomData<M>,
_phantom3: core::marker::PhantomData<N>,
}
impl<Emmis, Trans, E, M, N> CostingStrategies<Emmis, Trans, E, M, N>
where
E: Entry,
M: Metadata,
N: Network<E, M>,
Emmis: EmissionStrategy,
Trans: TransitionStrategy<E, M, N>,
{
pub fn new(emission: Emmis, transition: Trans) -> Self {
Self {
emission,
transition,
_phantom: PhantomData,
_phantom2: PhantomData,
_phantom3: PhantomData,
}
}
}
impl<E, M, N> Default for CostingStrategies<DefaultEmissionCost, DefaultTransitionCost, E, M, N>
where
E: Entry,
M: Metadata,
N: Network<E, M>,
{
fn default() -> Self {
CostingStrategies::new(DefaultEmissionCost::default(), DefaultTransitionCost)
}
}
impl<Emmis, Trans, E, M, N> Costing<Emmis, Trans, E, M, N>
for CostingStrategies<Emmis, Trans, E, M, N>
where
E: Entry,
M: Metadata,
N: Network<E, M>,
Trans: TransitionStrategy<E, M, N>,
Emmis: EmissionStrategy,
{
#[inline(always)]
fn emission(&self, context: EmissionContext) -> u32 {
self.emission.cost(context)
}
#[inline(always)]
fn transition(&self, context: TransitionContext<E, M, N>) -> u32 {
self.transition.cost(context)
}
}
}
pub use costing::*;
pub use emission::*;
pub use transition::*;