1use crate::constraints::{ConstraintVerdict, LoopConstraints};
2use crate::geo::LineString;
3use crate::model::{
4 Access, CrossingKind, EdgeAttr, EdgeId, GradeDistribution, Terrain, VertexId, WalkGraph,
5};
6use serde::{Deserialize, Serialize};
7use std::collections::BTreeMap;
8
9pub const LOW_CONFIDENCE_THRESHOLD: f64 = 0.6;
10
11#[derive(
12 Clone, Copy, Debug, Default, Eq, PartialEq, Ord, PartialOrd, Hash, Serialize, Deserialize,
13)]
14#[serde(rename_all = "kebab-case")]
15pub enum RouteShape {
16 #[default]
17 Loop,
18 FigureEight,
19 OutAndBack,
20 Open,
21}
22
23#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
24pub struct Route {
25 pub name: String,
26 pub start: VertexId,
27 pub edges: Vec<EdgeId>,
28 #[serde(default)]
29 pub pareto_rank: u32,
30 pub metrics: RouteMetrics,
31 pub verdict: ConstraintVerdict,
32 #[serde(default)]
33 pub score: f64,
34}
35
36impl Route {
37 #[must_use]
38 pub fn from_edges(
39 name: impl Into<String>,
40 graph: &WalkGraph,
41 start: VertexId,
42 edges: Vec<EdgeId>,
43 constraints: &LoopConstraints,
44 ) -> Self {
45 let metrics = RouteMetrics::measure(graph, start, &edges);
46 let verdict = constraints.judge(&metrics);
47 let score = route_score(&metrics, &verdict);
48 Self {
49 name: name.into(),
50 start,
51 edges,
52 pareto_rank: 0,
53 metrics,
54 verdict,
55 score,
56 }
57 }
58
59 #[must_use]
60 pub fn computed_score(&self) -> f64 {
61 route_score(&self.metrics, &self.verdict)
62 }
63
64 #[must_use]
65 pub fn geometry(&self, graph: &WalkGraph) -> LineString {
66 let mut at = self.start;
67 let mut previous = None;
68 let mut points = Vec::new();
69 for edge_id in &self.edges {
70 assert!(
71 graph.turn_allowed(previous, at, *edge_id),
72 "route turn must be legal"
73 );
74 let edge = &graph.edges[edge_id.0];
75 let line = edge.oriented_geometry(at);
76 if points.is_empty() {
77 points.extend(line.points.iter().copied());
78 } else {
79 points.extend(line.points.iter().skip(1).copied());
80 }
81 at = edge.traverse(at).expect("route edge must be traversable");
82 previous = Some(*edge_id);
83 }
84 LineString::unchecked(points)
85 }
86}
87
88#[must_use]
89pub fn route_score(metrics: &RouteMetrics, verdict: &ConstraintVerdict) -> f64 {
90 (100.0 - metrics.quality).mul_add(0.1, verdict.penalty)
91}
92
93pub fn rank_routes(routes: &mut [Route], constraints: &LoopConstraints) {
94 for route in routes.iter_mut() {
95 route.score = route.computed_score();
96 }
97 let points = routes
98 .iter()
99 .map(|route| ParetoPoint::from_route(route, constraints))
100 .collect::<Vec<_>>();
101 let mut rank = 1u32;
102 for satisfied in [true, false] {
103 let mut unranked = routes
104 .iter()
105 .enumerate()
106 .filter_map(|(i, route)| (route.verdict.satisfied == satisfied).then_some(i))
107 .collect::<Vec<_>>();
108 while !unranked.is_empty() {
109 let front = unranked
110 .iter()
111 .copied()
112 .filter(|&i| {
113 !unranked
114 .iter()
115 .any(|&j| i != j && points[j].dominates(points[i]))
116 })
117 .collect::<Vec<_>>();
118 for i in &front {
119 routes[*i].pareto_rank = rank;
120 }
121 unranked.retain(|i| !front.contains(i));
122 rank += 1;
123 }
124 }
125 routes.sort_by(|a, b| {
126 b.verdict.satisfied.cmp(&a.verdict.satisfied).then_with(|| {
127 a.pareto_rank
128 .cmp(&b.pareto_rank)
129 .then_with(|| a.computed_score().total_cmp(&b.computed_score()))
130 })
131 });
132}
133
134#[derive(Clone, Copy, Debug)]
135struct ParetoPoint {
136 constraint_penalty: f64,
137 distance_deviation_m: f64,
138 ascent_deviation_m: f64,
139 descent_deviation_m: f64,
140 lower_limb_load_deviation_km: f64,
141 moving_time_deviation_s: f64,
142 quality_loss: f64,
143 restricted_access_fraction: f64,
144 repeated_edge_fraction: f64,
145}
146
147impl ParetoPoint {
148 fn from_route(route: &Route, constraints: &LoopConstraints) -> Self {
149 let m = &route.metrics;
150 Self {
151 constraint_penalty: route.verdict.penalty,
152 distance_deviation_m: range_deviation(
153 m.distance_m,
154 constraints.min_distance_m,
155 constraints.max_distance_m,
156 ),
157 ascent_deviation_m: range_deviation(
158 m.ascent_m,
159 constraints.min_ascent_m,
160 constraints.max_ascent_m,
161 ),
162 descent_deviation_m: range_deviation(
163 m.descent_m,
164 constraints.min_descent_m,
165 constraints.max_descent_m,
166 ),
167 lower_limb_load_deviation_km: constraints.target_lower_limb_load_km.map_or_else(
168 || {
169 range_deviation(
170 m.lower_limb_load_km,
171 constraints.min_lower_limb_load_km,
172 constraints.max_lower_limb_load_km,
173 )
174 },
175 |target| (m.lower_limb_load_km - target).abs(),
176 ),
177 moving_time_deviation_s: range_deviation(
178 m.moving_time_s,
179 constraints.min_moving_time_s,
180 constraints.max_moving_time_s,
181 ),
182 quality_loss: 100.0 - m.quality,
183 restricted_access_fraction: m.restricted_access_fraction,
184 repeated_edge_fraction: m.repeated_edge_fraction,
185 }
186 }
187
188 fn dominates(self, rhs: Self) -> bool {
189 self.objectives()
190 .into_iter()
191 .zip(rhs.objectives())
192 .all(|(a, b)| a <= b)
193 && self
194 .objectives()
195 .into_iter()
196 .zip(rhs.objectives())
197 .any(|(a, b)| a < b)
198 }
199
200 const fn objectives(self) -> [f64; 9] {
201 [
202 self.constraint_penalty,
203 self.distance_deviation_m,
204 self.ascent_deviation_m,
205 self.descent_deviation_m,
206 self.lower_limb_load_deviation_km,
207 self.moving_time_deviation_s,
208 self.quality_loss,
209 self.restricted_access_fraction,
210 self.repeated_edge_fraction,
211 ]
212 }
213}
214
215fn range_deviation(value: f64, min: f64, max: f64) -> f64 {
216 if value < min {
217 min - value
218 } else if value > max {
219 value - max
220 } else {
221 0.0
222 }
223}
224
225#[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
226pub struct RouteMetrics {
227 #[serde(default)]
228 pub shape: RouteShape,
229 pub distance_m: f64,
230 pub ascent_m: f64,
231 pub descent_m: f64,
232 #[serde(default)]
233 pub lower_limb_load_km: f64,
234 #[serde(default)]
235 pub moving_time_s: f64,
236 #[serde(default)]
239 pub quality: f64,
240 #[serde(default)]
241 pub sustained_steep_m: f64,
242 #[serde(default)]
243 pub grade_distribution: GradeDistribution,
244 pub road_fraction: f64,
245 pub low_confidence_fraction: f64,
246 #[serde(default)]
247 pub elevation_fraction: f64,
248 #[serde(default)]
249 pub restricted_access_fraction: f64,
250 pub repeated_edge_fraction: f64,
251 #[serde(default)]
252 pub crossings: BTreeMap<CrossingKind, u32>,
253 #[serde(default)]
254 pub access_m: BTreeMap<Access, f64>,
255 pub terrain_m: BTreeMap<Terrain, f64>,
256}
257
258impl RouteMetrics {
259 #[must_use]
260 pub fn measure(graph: &WalkGraph, start: VertexId, edges: &[EdgeId]) -> Self {
261 let mut m = Self::default();
262 let mut seen = BTreeMap::<EdgeId, usize>::new();
263 let mut vertex_visits = BTreeMap::<VertexId, usize>::from([(start, 1)]);
264 let mut at = start;
265 let mut road_m = 0.0;
266 let mut low_conf_m = 0.0;
267 let mut elevation_m = 0.0;
268 let mut quality_m = 0.0;
269 let mut restricted_access_m = 0.0;
270 let mut repeated_edge_m = 0.0;
271 let mut previous = None;
272 for edge_id in edges {
273 assert!(
274 graph.turn_allowed(previous, at, *edge_id),
275 "route turn must be legal"
276 );
277 let edge = &graph.edges[edge_id.0];
278 let from = at;
279 let traversal = edge.traversal_from(from);
280 at = edge.traverse(from).expect("route edge must be traversable");
281 previous = Some(*edge_id);
282 *vertex_visits.entry(at).or_default() += 1;
283 let a = &edge.attr;
284 m.distance_m += a.length_m;
285 let (ascent_m, descent_m) = if from == edge.a {
286 (a.ascent_m, a.descent_m)
287 } else {
288 (a.descent_m, a.ascent_m)
289 };
290 m.ascent_m += ascent_m;
291 m.descent_m += descent_m;
292 m.lower_limb_load_km += traversal.lower_limb_load_km;
293 m.moving_time_s += traversal.moving_time_s;
294 m.sustained_steep_m += a.sustained_steep_m;
295 m.grade_distribution += a.grade_distribution;
296 quality_m = edge_quality(a).mul_add(a.length_m, quality_m);
297 elevation_m += edge
298 .geometry
299 .points
300 .windows(2)
301 .filter(|segment| segment[0].ele.is_some() && segment[1].ele.is_some())
302 .map(|segment| segment[0].haversine_m(segment[1]))
303 .sum::<f64>();
304 road_m = a
305 .length_m
306 .mul_add(road_exposure_fraction(a.terrain, a.road_exposure), road_m);
307 if a.confidence < LOW_CONFIDENCE_THRESHOLD {
308 low_conf_m += a.length_m;
309 }
310 if is_restricted_access(a.access) {
311 restricted_access_m += a.length_m;
312 }
313 for crossing in &a.crossings {
314 *m.crossings.entry(crossing.kind).or_default() += crossing.count;
315 }
316 *m.access_m.entry(a.access).or_default() += a.length_m;
317 *m.terrain_m.entry(a.terrain).or_default() += a.length_m;
318 let n = seen.entry(*edge_id).or_default();
319 if *n > 0 {
320 repeated_edge_m += a.length_m;
321 }
322 *n += 1;
323 }
324 if m.distance_m > 0.0 {
325 m.road_fraction = road_m / m.distance_m;
326 m.low_confidence_fraction = low_conf_m / m.distance_m;
327 m.elevation_fraction = (elevation_m / m.distance_m).clamp(0.0, 1.0);
328 m.quality = (100.0 * quality_m / m.distance_m).clamp(0.0, 100.0);
329 m.restricted_access_fraction = restricted_access_m / m.distance_m;
330 m.repeated_edge_fraction = repeated_edge_m / m.distance_m;
331 }
332 m.shape = classify_shape(start, at, repeated_edge_m, &vertex_visits);
333 m
334 }
335
336 #[must_use]
337 pub fn terrain_percentages(&self) -> BTreeMap<Terrain, f64> {
338 self.terrain_m
339 .iter()
340 .map(|(terrain, meters)| (*terrain, meters / self.distance_m.max(1.0)))
341 .collect()
342 }
343
344 #[must_use]
345 pub fn access_percentages(&self) -> BTreeMap<Access, f64> {
346 self.access_m
347 .iter()
348 .map(|(access, meters)| (*access, meters / self.distance_m.max(1.0)))
349 .collect()
350 }
351}
352
353fn edge_quality(attr: &EdgeAttr) -> f64 {
354 let road = road_exposure_fraction(attr.terrain, attr.road_exposure);
355 let uncertainty = 1.0 - attr.confidence.clamp(0.0, 1.0);
356 let access = match attr.access {
357 Access::Closed | Access::Private => 1.0,
358 Access::Restricted => 0.25,
359 Access::Unknown | Access::Open => 0.0,
360 };
361 1.0 - 0.70_f64
362 .mul_add(road, 0.25_f64.mul_add(uncertainty, 0.50 * access))
363 .clamp(0.0, 1.0)
364}
365
366#[must_use]
367pub const fn is_restricted_access(access: Access) -> bool {
368 matches!(
369 access,
370 Access::Restricted | Access::Closed | Access::Private
371 )
372}
373
374const fn road_exposure_fraction(terrain: Terrain, road_exposure: f64) -> f64 {
375 road_exposure
376 .clamp(0.0, 1.0)
377 .max(if matches!(terrain, Terrain::Road) {
378 1.0
379 } else {
380 0.0
381 })
382}
383
384fn classify_shape(
385 start: VertexId,
386 end: VertexId,
387 repeated_edge_m: f64,
388 vertex_visits: &BTreeMap<VertexId, usize>,
389) -> RouteShape {
390 if start != end {
391 return RouteShape::Open;
392 }
393 if repeated_edge_m > 0.0 {
394 return RouteShape::OutAndBack;
395 }
396 if vertex_visits
397 .iter()
398 .any(|(vertex, visits)| *visits > usize::from(*vertex == start) + 1)
399 {
400 return RouteShape::FigureEight;
401 }
402 RouteShape::Loop
403}