Repository navigation
Expand file tree
/
Copy pathrouting.ts
More file actions
356 lines (333 loc) · 19 KB
/
Copy pathrouting.ts
File metadata and controls
356 lines (333 loc) · 19 KB
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
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
import { paceFactor, planPreset, presetProfile, ridingProfiles } from './riding-profiles';
import { orderedRoutePoints, type DrawnCoordinate, type RoutePoint, type Trip } from './editor';
import { cumulative, firstIndex, nearestOnLine, type Coordinate } from './geo';
import { config } from './map-data';
import { releaseFetch } from './release';
import { decodeRoutes } from './route-answer';
import type { LegCache } from './route-legs';
/** The surfaces in the order of `surface_m` (`specs/route-api.md`). */
export const SURFACES = ['Unknown', 'Paved', 'Compacted', 'Gravel', 'Dirt', 'Rough'] as const;
export type Surface = typeof SURFACES[number];
export interface RouteTotals {
distance_m: number;
ascent_m: number;
seconds: number;
surface_m: number[];
unknown_elevation_m: number;
pushing_m: number;
}
/** `start` and `end` are opaque road positions (`specs/route-api.md`). */
export interface RouteLeg {
from_index: number;
to_index: number;
start: string;
end: string;
totals: RouteTotals;
/** The planner's straight line for a leg with no legal path; never in an answer. */
gap?: boolean;
}
/** Why the rider may have no access to an edge that the route uses; `specs/route-api.md` lists the kinds. */
export interface RouteClosure {
kind: 'permit' | 'private' | 'farm' | 'sidepath' | 'discouraged' | 'limited' | 'seasonal' | 'conditional' | 'unclear';
condition: string;
}
/** The facts of each edge, one channel for each fact (`specs/route-api.md`). A missing channel is null on every edge, and
* a manual section, whose facts are not verified, is null in every channel. A channel that the planner does not know
* travels with the others. */
export interface Edges {
surfaces?: (Surface | null)[];
pushing?: (boolean | null)[];
/** The possible closures of each edge. */
closures?: (RouteClosure[] | null)[];
/** The SAC hiking grade of each edge: 0 (`strolling`) or 1 (T1) to 6 (T6). */
sac_scale?: (number | null)[];
}
/** Appends the edges `from` to `to` of `source`, or null edges without a source, to `target`, which holds `length` edges.
* A channel that one side lacks is null there. */
export function appendEdges(target: Edges, length: number, source: Edges | undefined, from: number, to: number): void {
const into = target as Record<string, unknown[]>, values = (source ?? {}) as Record<string, unknown[]>;
for (const channel of new Set([...Object.keys(into), ...Object.keys(values)])) {
const edges = into[channel] ??= Array(length).fill(null);
for (let i = from; i < to; i++) edges.push(values[channel]?.[i] ?? null);
}
}
export interface EngineRoute {
package: string;
profile: string;
geometry: Coordinate[];
elevation: (number | null)[];
elapsed: number[];
edges: Edges;
totals: RouteTotals;
legs: RouteLeg[];
snap_truncated: boolean;
}
/** The calculated line of a plan. It is not part of the plan: the planner calculates it again from the plan's points. */
export interface RoutingLine {
coordinates: Coordinate[];
elevation: (number | null)[];
elapsed: number[];
edges: Edges;
stops: { id: string; distance: number }[];
seconds: number;
profile: string;
unknownSurfaceKm: number;
pushingKm: number;
unroutedKm: number;
/** Ridden kilometres whose ascent is unknown; a transfer is not ridden, so it never counts. */
unknownElevationKm: number;
/** The plan points at which a leg with no legal path ends, as `legEndId`. Such a leg is a straight line with no time and no
* climb, and it counts in no unknown or unrouted figure. */
gapLegs: string[];
/** Routing package of the routed legs. */
package?: string;
}
/** Longer than the deadlines of the route service, so its own error arrives first. A hung call frees its caller. */
const timeoutMs = { '/v1/route': 20_000, '/v1/shape': 40_000 };
/** The fields of a routing error: the service's `code`, and the index of the point or the leg that it names. */
export interface RouteFailure {
code?: string;
point?: number;
leg?: number;
}
/** The answer, or an error with a message for the rider and the fields of the service's error. A caller's abort passes through. */
async function post(path: keyof typeof timeoutMs, body: unknown, signal?: AbortSignal): Promise<unknown> {
const timeout = AbortSignal.timeout(timeoutMs[path]);
let response: Response | undefined, data: RouteFailure & { message?: string } | undefined;
try {
response = await releaseFetch(`${config.routing}${path}`, { method: 'POST', headers: { 'Content-Type': 'application/json' },
signal: signal ? AbortSignal.any([signal, timeout]) : timeout, body: JSON.stringify(body) });
data = await response.json();
} catch (error) {
if (signal?.aborted) throw error;
// A proxy answers with an HTML page while the service restarts.
throw new Error(timeout.aborted ? 'The routing service did not answer in time. Retry shortly.'
: !response ? 'The routing service is unreachable. Check your connection and retry.'
: response.ok ? 'The routing service returned an invalid response.' : 'Routing is unavailable. Retry shortly.');
}
if (!response.ok) throw Object.assign(new Error(data?.message ?? 'Routing is unavailable. Retry shortly.'), { code: data?.code, point: data?.point, leg: data?.leg });
return data;
}
let region: Promise<string[]> | undefined;
/** The profile IDs that the routing region serves (`GET /v1/region`), asked once a page; a failed request is asked again. */
export function regionProfiles(): Promise<string[]> {
return region ??= (async () => {
const response = await releaseFetch(`${config.routing}/v1/region`, { signal: AbortSignal.timeout(timeoutMs['/v1/route']) });
const profiles = (await response.json() as { profiles?: unknown } | null)?.profiles;
if (!response.ok || !Array.isArray(profiles) || !profiles.every(p => typeof p === 'string')) throw new Error('The routing service returned an invalid region.');
return profiles;
})().catch(error => { region = undefined; throw error; });
}
/** The points of one route request (`specs/route-api.md`). */
export const MAX_REQUEST_POINTS = 64;
export async function requestRoute(points: Coordinate[], profile: string, signal: AbortSignal, turnarounds: number[] = [],
pins: { start_position?: string; end_position?: string } = {}): Promise<EngineRoute> {
const [route] = decodeRoutes(await post('/v1/route', { points, profile, turnarounds, ...pins }, signal) as Parameters<typeof decodeRoutes>[0]);
if (!route) throw new Error('The routing service returned no route.');
return route;
}
/** Points that `/v1/route` routes along `line` (`specs/route-api.md`); a turnaround is an index into `points`. */
export interface Shape {
points: Coordinate[];
turnarounds: number[];
}
/** A failed or hung call keeps the file's line. */
export async function requestShape(line: Coordinate[], profile: string): Promise<Shape> {
const data = await post('/v1/shape', { line, profile }) as Partial<Shape>;
const points = data.points, turnarounds = data.turnarounds ?? [];
if (!Array.isArray(points) || points.length < 2 || !points.every(p => Array.isArray(p) && p.length === 2 && p.every(Number.isFinite))
|| !Array.isArray(turnarounds) || !turnarounds.every(i => Number.isInteger(i) && i > 0 && i < points.length - 1))
throw new Error('The routing service returned an invalid response.');
return { points, turnarounds };
}
export function profileId(trip: Trip): string {
return presetProfile(trip.bike, trip.preset);
}
const keys = new WeakMap<Trip, string>();
/** What the line of a trip depends on, so equal keys share one line. Itinerary edits and labels never change it. */
export function routingKey(trip: Trip): string {
let key = keys.get(trip);
if (key === undefined) {
key = JSON.stringify([trip.bike ?? 'touring', planPreset(trip.bike, trip.preset), orderedRoutePoints(trip).map(p => [p.id, p.coordinate, p.leg ?? 'routed', p.drawn ?? [], p.kind === 'detour', p.anchor, p.turnaround])]);
keys.set(trip, key);
}
return key;
}
/** The request points of a run of routed plan points after `origin`, without the points of `leftOut`: a detour goes to its
* place and back to its anchor. A left-out detour at the end of the run keeps its anchor, where the manual leg after it
* starts. `ends` maps each leg that ends at a plan point to the point's id, and `owners` gives the plan point of each
* request point after the origin. */
function expand(origin: Coordinate, run: RoutePoint[], leftOut: Set<string>) {
const coordinates: Coordinate[] = [origin], turnarounds: number[] = [], ends = new Map<number, string>();
const owners: (RoutePoint | undefined)[] = [undefined];
run.forEach((point, n) => {
if (leftOut.has(point.id)) {
if (n < run.length - 1) return;
coordinates.push(point.anchor!);
owners.push(point);
ends.set(coordinates.length - 2, point.id);
} else if (point.kind === 'detour') {
if (!point.anchor) throw new Error('Choose a return point on the route for this visit.');
coordinates.push(point.anchor, point.coordinate, point.anchor);
owners.push(point, point, point);
turnarounds.push(coordinates.length - 2);
ends.set(coordinates.length - 3, point.id);
} else {
coordinates.push(point.coordinate);
owners.push(point);
ends.set(coordinates.length - 2, point.id);
if (point.turnaround && n < run.length - 1) turnarounds.push(coordinates.length - 1);
}
});
return { coordinates, turnarounds, ends, owners };
}
/** Consecutive routed legs form one run, so a shaping point keeps its road direction. A point with no road near it is left
* out, and a leg with no legal path is a gap, so that one bad point or leg never hides the line. */
export async function calculateLine(trip: Trip, signal: AbortSignal, legs: LegCache): Promise<RoutingLine> {
const points = orderedRoutePoints(trip);
if (points.length < 2) throw new Error('Choose a start and finish to calculate a route.');
const result: RoutingLine = { coordinates: [], elevation: [], elapsed: [], edges: {}, stops: [], seconds: 0, profile: profileId(trip), unknownSurfaceKm: 0, pushingKm: 0, unroutedKm: 0, unknownElevationKm: 0, gapLegs: [] };
// Seconds per kilometre on a manual leg or connector.
const pace = 3600 / ridingProfiles[trip.bike ?? 'touring'].engineKmh;
let distance = 0;
let afterTransfer = false;
function append(line: Coordinate[], elevation: (number | null)[], elapsed: number[], edges: Edges, transfer = false) {
const last = result.coordinates.at(-1);
const gap = last ? cumulative([last, line[0]])[1] : 0;
// A join to a manually drawn leg is itself an explicit, unverified connector. A join to a transfer is not ridden.
if (gap > 0 && !transfer && !afterTransfer) {
result.unroutedKm += gap; result.unknownSurfaceKm += gap; result.seconds += gap * pace;
if (result.elevation.at(-1) === null || elevation[0] === null) result.unknownElevationKm += gap;
}
distance += gap;
// After a transfer the next leg repeats its first vertex, so no segment joins the heights at the two ends of the transfer.
const offset = last && gap === 0 && !afterTransfer ? 1 : 0;
const connector = last && !offset ? 1 : 0;
afterTransfer = transfer;
const length = Math.max(result.coordinates.length - 1, 0);
appendEdges(result.edges, length, undefined, 0, connector);
appendEdges(result.edges, length + connector, edges, 0, line.length - 1);
for (let i = offset; i < line.length; i++) {
result.coordinates.push(line[i]);
result.elevation.push(elevation[i]);
result.elapsed.push(elapsed[i] + result.seconds);
}
result.seconds += elapsed.at(-1) ?? 0;
const start = distance;
distance += cumulative(line).at(-1)!;
return start;
}
result.stops.push({ id: points[0].id, distance: 0 });
for (let i = 1; i < points.length;) {
const end = points[i];
const before = points[i - 1];
const origin = before.kind === 'detour' ? before.anchor ?? before.coordinate : before.coordinate;
if (end.leg && end.leg !== 'routed') {
const drawn: DrawnCoordinate[] = [origin, ...(end.leg === 'drawn' ? end.drawn ?? [] : []), end.coordinate];
const line = drawn.map((c): Coordinate => [c[0], c[1]]);
const heights = drawn.map(c => c[2] ?? null);
// A drawn leg repeats its points with their heights; the points themselves have none.
const same = (a: number, b: number) => line[a][0] === line[b][0] && line[a][1] === line[b][1];
if (line.length > 2 && same(0, 1)) heights[0] ??= heights[1];
if (line.length > 2 && same(line.length - 1, line.length - 2)) heights[line.length - 1] ??= heights[line.length - 2];
const lengths = cumulative(line);
const ridden = end.leg !== 'transfer';
append(line, heights, lengths.map(km => ridden ? km * pace : 0), {}, !ridden);
const km = ridden ? lengths.at(-1)! : 0;
result.unknownSurfaceKm += km;
result.unroutedKm += km;
if (ridden) heights.forEach((h, k) => { if (k && (h === null || heights[k - 1] === null)) result.unknownElevationKm += lengths[k] - lengths[k - 1]; });
result.stops.push({ id: end.id, distance });
i++;
continue;
}
let until = i;
while (until + 1 < points.length && (points[until + 1].leg ?? 'routed') === 'routed') until++;
const run = points.slice(i, until + 1), leftOut = new Set<string>();
let request = expand(origin, run, leftOut), route: EngineRoute;
for (;;) {
try {
route = await legs.route(request.coordinates, request.turnarounds, result.profile, signal);
break;
} catch (error) {
const { code, point, leg } = error as RouteFailure, last = request.coordinates.length - 1;
const gap = (k: number) => legs.gap(request.coordinates, request.turnarounds, result.profile, k);
// An index outside the request would send the same request again without end.
if (code === 'no_path' && Number.isInteger(leg) && leg! >= 0 && leg! < last) gap(leg!);
else if (code !== 'no_snap' || !Number.isInteger(point) || point! < 0 || point! > last) throw error;
// The first and the last request point, a start, a finish or a point beside a manual leg, stay, so that the
// manual leg keeps its join: the leg at the point becomes a gap.
else if (point === 0 || point === last) gap(point === 0 ? 0 : last - 1);
// A detour is left out with its anchors.
else leftOut.add(request.owners[point!]!.id);
request = expand(origin, run, leftOut);
}
}
if (route.package) result.package = route.package;
const start = append(route.geometry, route.elevation, route.elapsed, route.edges);
const lengths = cumulative(route.geometry);
result.unknownSurfaceKm += route.totals.surface_m[0] / 1000;
result.pushingKm += route.totals.pushing_m / 1000;
result.unknownElevationKm += route.totals.unknown_elevation_m / 1000;
const stopAt = new Map([...request.ends].map(([leg, id]) => [id, route.legs[leg].to_index]));
// A gap belongs to the stop after it. The way back from a detour at the end of the run has none: it belongs to the detour.
const ends = [...request.ends];
route.legs.forEach((leg, k) => {
const id = leg.gap && (ends.find(([end]) => end >= k) ?? ends.at(-1)!)[1];
if (id && !result.gapLegs.includes(id)) result.gapLegs.push(id);
});
// A point left out stops where the line passes nearest to it, between the points around it.
let from = 0;
run.forEach((point, n) => {
let index = stopAt.get(point.id), share = 0;
if (index === undefined) {
const to = run.slice(n + 1).map(next => stopAt.get(next.id)).find(at => at !== undefined) ?? route.geometry.length - 1;
({ index, t: share } = nearestOnLine(route.geometry.slice(from, to + 1), point.coordinate));
index += from;
}
from = index;
result.stops.push({ id: point.id, distance: start + lengths[index] + (share && (lengths[index + 1] - lengths[index]) * share) });
});
i = until + 1;
}
return result;
}
const pacedLines = new WeakMap<RoutingLine, Map<string, RoutingLine>>();
const pacedSources = new WeakMap<RoutingLine, RoutingLine>();
/** `line` with the time at the activity and pace of `trip` (`paceFactor`). In a bike plan a pushed segment keeps its
* walking time. Each line has one copy for each factor and kind of plan, so a cache by the identity of `elapsed` keeps
* working. A paced copy is paced again from its source line. */
export function pacedLine(line: RoutingLine, trip: Trip): RoutingLine {
const source = pacedSources.get(line) ?? line, factor = paceFactor(trip), pushed = trip.bike !== 'hiking' && source.edges.pushing;
if (factor === 1) return source;
let byFactor = pacedLines.get(source);
if (!byFactor) pacedLines.set(source, byFactor = new Map());
const key = `${factor} ${!!pushed}`;
let paced = byFactor.get(key);
if (!paced) {
const elapsed = [...source.elapsed];
for (let i = 1; i < elapsed.length; i++)
elapsed[i] = elapsed[i - 1] + (source.elapsed[i] - source.elapsed[i - 1]) * (pushed && pushed[i - 1] ? 1 : factor);
byFactor.set(key, paced = { ...source, elapsed, seconds: elapsed.at(-1) ?? 0 });
pacedSources.set(paced, source);
}
return paced;
}
/** The progress at which `seconds` of riding are done: the inverse of `movingSecondsAt`. */
export function progressAtSeconds(line: RoutingLine, seconds: number): number {
const lengths = cumulative(line.coordinates), total = lengths.at(-1) ?? 0;
const i = firstIndex(line.elapsed.length, index => line.elapsed[index] >= seconds);
if (!total || i === 0) return 0;
if (i === line.elapsed.length) return 1;
const share = (seconds - line.elapsed[i - 1]) / (line.elapsed[i] - line.elapsed[i - 1] || 1);
return (lengths[i - 1] + share * (lengths[i] - lengths[i - 1])) / total;
}
export function movingSecondsAt(line: RoutingLine, progress: number): number {
const lengths = cumulative(line.coordinates);
const distance = progress * (lengths.at(-1) ?? 0);
const i = firstIndex(lengths.length, index => lengths[index] >= distance);
if (i === lengths.length) return line.seconds;
if (i === 0) return 0;
const share = (distance - lengths[i - 1]) / (lengths[i] - lengths[i - 1] || 1);
return line.elapsed[i - 1] + share * (line.elapsed[i] - line.elapsed[i - 1]);
}