Geo.res
1type point = (float, float)
2type lngLat = {lng: float, lat: float}
3let lngLatToPoint = (a: lngLat): point => (a.lng, a.lat)
4
5module GeoJSON = {
6 // opaque type for GeoJSON, referred to as Geo.GeoJSON.t elsewhere
7 type t
8}
9
10// return value from nearestPointOnLine, all values in km
11// Turf.js v7.4+ returns a GeoJSON Feature with these properties:
12// lineStringIndex = closest point was found on the nth LineString (MultiLineString only)
13// segmentIndex = closest point was found on nth segment of the LineString
14// totalDistance = distance from start of overall MultiLineString
15// lineDistance = distance from start of the relevant LineString
16// segmentDistance = distance from start of the relevant segment
17// pointDistance = distance to the input point
18type nearest = {
19 lineStringIndex: int,
20 lineDistance: float,
21 pointDistance: float,
22}
23
24// Turf.js nearestPointOnLine returns a GeoJSON Feature with properties nested inside
25// We wrap it to expose the properties directly as our `nearest` type
26type nearestFeature = {
27 properties: nearest,
28}
29
30@module("@turf/nearest-point-on-line")
31external nearestPointOnLineRaw: (GeoJSON.t, point) => nearestFeature = "nearestPointOnLine"
32
33let nearestPointOnLine = (geojson: GeoJSON.t, point: point): nearest => {
34 let feature = nearestPointOnLineRaw(geojson, point)
35 feature.properties
36}
37
38// Result type for getDistance and getTime
39type result = {
40 previousID: option<string>,
41 nextID: option<string>,
42 fromPreviousWaypoint: float,
43 toNextWaypoint: float,
44 fromStart: Map.t<array<string>, float>,
45}
46
47// GeoJSON Feature properties from routing engine
48// These are stored in the GeoJSON feature's properties field
49type routeProperties = {
50 distance: float,
51 time: float,
52}
53
54// Extract route properties (distance and time) from GeoJSON Feature
55// GeoJSON structure: { type: "Feature", geometry: {...}, properties: {distance, time, ...} }
56let extractRouteProperties = (geojson: GeoJSON.t): option<routeProperties> => {
57 // Convert Geo.GeoJSON.t to global JSON.t for decoding
58 let json = geojson->Obj.magic
59 switch JSON.Decode.object(json) {
60 | Some(dict) => switch dict->Dict.get("properties")->Option.flatMap(JSON.Decode.object) {
61 | Some(props) => {
62 let distance = props->Dict.get("distance")->Option.flatMap(JSON.Decode.float)
63 let time = props->Dict.get("time")->Option.flatMap(JSON.Decode.float)
64 switch (distance, time) {
65 | (Some(distance), Some(time)) => Some({distance, time})
66 | _ => None
67 }
68 }
69 | None => None
70 }
71 | None => None
72 }
73}
74
75// Helper to convert Map entries to array (must be at module level for use in relativeDistances)
76let mapEntries: Map.t<'k, 'v> => array<('k, 'v)> = %raw(`(map) => Array.from(map.entries())`)
77
78// Extract source waypoint ID from route key
79// Route keys can have constraint suffixes like "wp1:saa" or "wp1:adv(80):max(100)"
80// Returns the base waypoint ID (e.g., "wp1")
81let parseRouteKey = (key: string): string => {
82 switch key->String.split(":")->Array.get(0) {
83 | Some(id) => id
84 | None => key
85 }
86}
87
88// Find a waypoint by its ID
89let findWaypointById = (waypoints: array<Waypoint.attributes>, id: string): option<
90 Waypoint.attributes,
91> => {
92 waypoints->Array.find(wp => wp.id == id)
93}
94
95// Find the destination waypoint and source waypoint ID for a given route hash.
96// Returns Some((destWaypoint, sourceWaypointId)) where destWaypoint.from[sourceKey].id == layer
97// Note: sourceKey may include constraint suffixes (e.g., "wp1:saa"), but sourceWaypointId is just "wp1"
98let findRouteEndpoints = (waypoints: array<Waypoint.attributes>, layer: string): option<(
99 Waypoint.attributes,
100 string,
101)> => {
102 waypoints->Array.findMap((wp: Waypoint.attributes) => {
103 switch wp.from {
104 | Some(routeDict) =>
105 routeDict
106 ->Dict.toArray
107 ->Array.findMap(((sourceKey, route)) => {
108 switch route.id {
109 | Some(id) if id == layer => {
110 // Extract base waypoint ID from route key (e.g., "wp1:saa" -> "wp1")
111 let sourceWaypointId = parseRouteKey(sourceKey)
112 Some((wp, sourceWaypointId))
113 }
114 | _ => None
115 }
116 })
117 | None => None
118 }
119 })
120}
121
122// Check if a waypoint is the trip origin (first waypoint with empty from dict)
123let isOrigin = (wp: Waypoint.attributes): bool => {
124 if wp.nonroutable {
125 false
126 } else {
127 switch wp.from {
128 | Some(dict) => Dict.toArray(dict)->Array.length == 0
129 | None => true
130 }
131 }
132}
133
134/**
135 * Calculate distance along the route at any point.
136 *
137 * @param point The hover point (lon, lat)
138 * @param layer The route hash (ID field of the Route in the waypoint's from dict)
139 * @param waypoints Array of all waypoints in the trip
140 * @param geojson GeoJSON of the current route segment (caller fetches from service worker cache)
141 * @returns {fromPreviousWaypoint: distance from start of current segment, fromStart: Map of paths to total distances}
142 */
143let getDistance = (
144 point: point,
145 layer: string,
146 waypoints: array<Waypoint.attributes>,
147 geojson: GeoJSON.t,
148): result => {
149 switch findRouteEndpoints(waypoints, layer) {
150 | None => {
151 previousID: None,
152 nextID: None,
153 fromPreviousWaypoint: 0.0,
154 toNextWaypoint: 0.0,
155 fromStart: Map.make(),
156 }
157 | Some((destWp, sourceId)) => {
158 // Calculate distance along the current segment from its start
159 let nearest = nearestPointOnLine(geojson, point)
160 let fromPreviousWaypoint = nearest.lineDistance
161
162 // Calculate remaining distance to next waypoint
163 let segmentTotalDistance = switch extractRouteProperties(geojson) {
164 | Some(props) => props.distance
165 | None => 0.0
166 }
167 let toNextWaypoint = segmentTotalDistance -. fromPreviousWaypoint
168
169 // Build O(1) waypoint lookup map to avoid linear search in DFS
170 let waypointMap = waypoints->Array.map(wp => (wp.id, wp))->Dict.fromArray
171 let findWaypoint = (id: string): option<Waypoint.attributes> => {
172 waypointMap->Dict.get(id)
173 }
174
175 let fromStart = Map.make()
176
177 // Recursive DFS backward through the waypoint DAG.
178 // accumulatedPath: forward-order array of waypoint IDs from origin to currentId
179 // accumulatedDistance: sum of segment distances from origin to currentId
180 // visited: set of waypoint IDs in the current branch (for cycle detection)
181 let rec traverse = (
182 currentId: string,
183 accumulatedPath: array<string>,
184 accumulatedDistance: float,
185 visited: Set.t<string>,
186 ) => {
187 switch findWaypoint(currentId) {
188 | None => ()
189 | Some(wp) => {
190 let newPath = [currentId]->Array.concat(accumulatedPath)
191
192 if isOrigin(wp) {
193 // Reached the origin — store the complete path
194 let totalDistance = accumulatedDistance +. fromPreviousWaypoint
195 fromStart->Map.set(newPath, totalDistance)
196 } else {
197 // Continue to all predecessors, sorted by segment distance (shortest first)
198 switch wp.from {
199 | Some(routeDict) => {
200 let predecessors =
201 routeDict
202 ->Dict.toArray
203 ->Array.filter(((prevId, _)) => !(visited->Set.has(prevId)))
204 ->Array.toSorted((a, b) => {
205 let (_, routeA) = a
206 let (_, routeB) = b
207 let distA = routeA.d->Option.getOr(0.0)
208 let distB = routeB.d->Option.getOr(0.0)
209 if distA < distB {
210 -1.0
211 } else if distA > distB {
212 1.0
213 } else {
214 0.0
215 }
216 })
217
218 predecessors->Array.forEach(((prevKey, route)) => {
219 // Extract base waypoint ID from route key (e.g., "wp1:saa" -> "wp1")
220 let prevId = parseRouteKey(prevKey)
221 let segmentDist = route.d->Option.getOr(0.0)
222 let newVisited = Set.fromArray(visited->Set.toArray)
223 newVisited->Set.add(currentId)
224 traverse(prevId, newPath, accumulatedDistance +. segmentDist, newVisited)
225 })
226 }
227 | None => ()
228 }
229 }
230 }
231 }
232 }
233
234 // Seed traversal from the source of the current route segment
235 let visited = Set.make()
236 visited->Set.add(destWp.id)
237 traverse(sourceId, [], 0.0, visited)
238
239 {
240 previousID: Some(sourceId),
241 nextID: Some(destWp.id),
242 fromPreviousWaypoint,
243 toNextWaypoint,
244 fromStart,
245 }
246 }
247 }
248}
249
250/**
251 * Calculate time along the route at any point.
252 *
253 * @param point The hover point (lon, lat)
254 * @param layer The route hash (ID field of the Route in the waypoint's from dict)
255 * @param waypoints Array of all waypoints in the trip
256 * @param geojson GeoJSON of the current route segment (caller fetches from service worker cache)
257 * @returns {fromPreviousWaypoint: estimated time from start of current segment, fromStart: Map of paths to total times}
258 */
259let getTime = (
260 point: point,
261 layer: string,
262 waypoints: array<Waypoint.attributes>,
263 geojson: GeoJSON.t,
264): result => {
265 // Extract route properties from GeoJSON
266 let (routeTotalDistance, routeTotalTime) = switch extractRouteProperties(geojson) {
267 | Some(props) => (props.distance, props.time)
268 | None => (0.0, 0.0)
269 }
270
271 switch findRouteEndpoints(waypoints, layer) {
272 | None => {
273 previousID: None,
274 nextID: None,
275 fromPreviousWaypoint: 0.0,
276 toNextWaypoint: 0.0,
277 fromStart: Map.make(),
278 }
279 | Some((destWp, sourceId)) => {
280 // Calculate distance along the current segment from its start
281 let nearest = nearestPointOnLine(geojson, point)
282 let lineDistance = nearest.lineDistance
283
284 // Linear interpolation: estimate time based on percentage of distance traveled
285 // Avoid division by zero
286 let fromPreviousWaypoint = if routeTotalDistance > 0.0 {
287 lineDistance /. routeTotalDistance *. routeTotalTime
288 } else {
289 0.0
290 }
291
292 // Calculate remaining time to next waypoint
293 let toNextWaypoint = routeTotalTime -. fromPreviousWaypoint
294
295 // Build O(1) waypoint lookup map to avoid linear search in DFS
296 let waypointMap = waypoints->Array.map(wp => (wp.id, wp))->Dict.fromArray
297 let findWaypoint = (id: string): option<Waypoint.attributes> => {
298 waypointMap->Dict.get(id)
299 }
300
301 let fromStart = Map.make()
302
303 // Recursive DFS backward through the waypoint DAG.
304 // accumulatedPath: forward-order array of waypoint IDs from origin to currentId
305 // accumulatedTime: sum of segment times from origin to currentId
306 // visited: set of waypoint IDs in the current branch (for cycle detection)
307 let rec traverse = (
308 currentId: string,
309 accumulatedPath: array<string>,
310 accumulatedTime: float,
311 visited: Set.t<string>,
312 ) => {
313 switch findWaypoint(currentId) {
314 | None => ()
315 | Some(wp) => {
316 let newPath = [currentId]->Array.concat(accumulatedPath)
317
318 if isOrigin(wp) {
319 // Reached the origin — store the complete path
320 let totalTime = accumulatedTime +. fromPreviousWaypoint
321 fromStart->Map.set(newPath, totalTime)
322 } else {
323 // Continue to all predecessors, sorted by segment time (shortest first)
324 switch wp.from {
325 | Some(routeDict) => {
326 let predecessors =
327 routeDict
328 ->Dict.toArray
329 ->Array.filter(((prevId, _)) => !(visited->Set.has(prevId)))
330 ->Array.toSorted((a, b) => {
331 let (_, routeA) = a
332 let (_, routeB) = b
333 let timeA = routeA.t->Option.getOr(0.0)
334 let timeB = routeB.t->Option.getOr(0.0)
335 if timeA < timeB {
336 -1.0
337 } else if timeA > timeB {
338 1.0
339 } else {
340 0.0
341 }
342 })
343
344 predecessors->Array.forEach(((prevKey, route)) => {
345 // Extract base waypoint ID from route key (e.g., "wp1:saa" -> "wp1")
346 let prevId = parseRouteKey(prevKey)
347 let segmentTime = route.t->Option.getOr(0.0)
348 let newVisited = Set.fromArray(visited->Set.toArray)
349 newVisited->Set.add(currentId)
350 traverse(prevId, newPath, accumulatedTime +. segmentTime, newVisited)
351 })
352 }
353 | None => ()
354 }
355 }
356 }
357 }
358 }
359
360 // Seed traversal from the source of the current route segment
361 let visited = Set.make()
362 visited->Set.add(destWp.id)
363 traverse(sourceId, [], 0.0, visited)
364
365 {
366 previousID: Some(sourceId),
367 nextID: Some(destWp.id),
368 fromPreviousWaypoint,
369 toNextWaypoint,
370 fromStart,
371 }
372 }
373 }
374}
375
376// Stats result type containing both distance and time
377type stats = {
378 dist: result,
379 time: result,
380}
381
382/**
383 * Calculate both distance and time stats along the route at any point.
384 *
385 * @param point The hover point (lon, lat)
386 * @param layer The route hash (ID field of the Route in the waypoint's from dict)
387 * @param waypoints Array of all waypoints in the trip
388 * @param geojson GeoJSON of the current route segment (caller fetches from service worker cache)
389 * @returns {dist: distance result, time: time result}
390 */
391let getStats = (
392 point: point,
393 layer: string,
394 waypoints: array<Waypoint.attributes>,
395 geojson: GeoJSON.t,
396): stats => {
397 {
398 dist: getDistance(point, layer, waypoints, geojson),
399 time: getTime(point, layer, waypoints, geojson),
400 }
401}
402
403/**
404 * Build a distance matrix from origin to all reachable waypoints.
405 *
406 * Traverses forward from the origin through the waypoint DAG, accumulating
407 * distances along all possible paths. Non-routable waypoints are excluded.
408 * When multiple paths exist to the same waypoint, all are included in the matrix.
409 *
410 * @param waypoints Array of all waypoints in the trip
411 * @returns Map of path arrays (waypoint IDs from origin to destination) to cumulative distance
412 */
413let getDistanceMatrix = (waypoints: array<Waypoint.attributes>): Map.t<array<string>, float> => {
414 // Build O(1) waypoint lookup map
415 let waypointMap = waypoints->Array.map(wp => (wp.id, wp))->Dict.fromArray
416 let findWaypoint = (id: string): option<Waypoint.attributes> => {
417 waypointMap->Dict.get(id)
418 }
419
420 // Find the origin waypoint (nonroutable=false and empty from dict)
421 let origin = waypoints->Array.find(wp => isOrigin(wp))
422
423 switch origin {
424 | None => Map.make()
425 | Some(originWp) => {
426 // Build forward adjacency list: from a waypoint, where can we go?
427 // Invert the 'from' relationships: if B.from has {"A": route}, then A can reach B
428 let adjacencyList = Map.make()
429
430 waypoints->Array.forEach((wp: Waypoint.attributes) => {
431 // Skip non-routable waypoints - they can't be reached or traversed
432 if !wp.nonroutable {
433 switch wp.from {
434 | Some(routeDict) => {
435 routeDict
436 ->Dict.toArray
437 ->Array.forEach(((sourceKey, route)) => {
438 // Extract base waypoint ID from route key (e.g., "A:saa" -> "A")
439 let sourceId = parseRouteKey(sourceKey)
440 let distance = route.d->Option.getOr(0.0)
441
442 // Add this waypoint as a destination from the source
443 switch adjacencyList->Map.get(sourceId) {
444 | Some(existing) => {
445 adjacencyList->Map.set(sourceId, Array.concat(existing, [(wp.id, distance)]))
446 }
447 | None => {
448 adjacencyList->Map.set(sourceId, [(wp.id, distance)])
449 }
450 }
451 })
452 }
453 | None => ()
454 }
455 }
456 })
457
458 // Result map: path -> cumulative distance
459 let result = Map.make()
460
461 // DFS forward from origin, accumulating paths and distances
462 // currentId: current waypoint being visited
463 // currentPath: array of waypoint IDs from origin to current (excluding current)
464 // accumulatedDistance: sum of distances from origin to start of current waypoint
465 // visited: set of waypoint IDs in current path (for cycle detection)
466 let rec traverse = (
467 currentId: string,
468 currentPath: array<string>,
469 accumulatedDistance: float,
470 visited: Set.t<string>,
471 ) => {
472 // Check if this waypoint exists and is routable
473 switch findWaypoint(currentId) {
474 | None => ()
475 | Some(wp) => {
476 if wp.nonroutable {
477 ()
478 } else {
479 // Build the complete path including current waypoint
480 let completePath = Array.concat(currentPath, [currentId])
481
482 // Store this path with its cumulative distance
483 // Don't store the origin-only path (just ["A"])
484 if Array.length(completePath) > 1 {
485 result->Map.set(completePath, accumulatedDistance)
486 }
487
488 // Continue to all destinations from this waypoint
489 switch adjacencyList->Map.get(currentId) {
490 | Some(destinations) => {
491 destinations->Array.forEach(((destId, segmentDist)) => {
492 // Check for cycles - don't visit if already in path
493 if !(visited->Set.has(destId)) {
494 let newVisited = Set.fromArray(visited->Set.toArray)
495 newVisited->Set.add(currentId)
496 traverse(destId, completePath, accumulatedDistance +. segmentDist, newVisited)
497 }
498 })
499 }
500 | None => ()
501 }
502 }
503 }
504 }
505 }
506
507 // Start traversal from origin with empty path and zero distance
508 let visited = Set.make()
509 traverse(originWp.id, [], 0.0, visited)
510
511 result
512 }
513 }
514}
515
516/**
517 * Extract prefix of a path up to (and including) a specific waypoint.
518 * Returns the array of waypoint IDs from start up to and including targetId.
519 */
520let extractPrefix = (path: array<string>, targetId: string): option<array<string>> => {
521 let rec findIndex = (idx: int) => {
522 if idx >= Array.length(path) {
523 None
524 } else if path->Array.getUnsafe(idx) == targetId {
525 Some(idx)
526 } else {
527 findIndex(idx + 1)
528 }
529 }
530
531 switch findIndex(0) {
532 | Some(endIdx) => Some(path->Array.slice(~start=0, ~end=endIdx + 1))
533 | None => None
534 }
535}
536
537/**
538 * Calculate relative distances from a reference waypoint to all reachable waypoints.
539 *
540 * Given a distance matrix from getDistanceMatrix, computes distances relative to
541 * the specified waypoint. Waypoints before the reference have negative distances,
542 * waypoints after have positive distances, and the reference itself is 0.
543 *
544 * When multiple paths exist to reach a waypoint, the shortest absolute distance is used.
545 *
546 * @param id The reference waypoint ID
547 * @param matrix Distance matrix from getDistanceMatrix
548 * @returns Map of waypoint ID to relative distance from reference
549 */
550let relativeDistances = (id: string, matrix: Map.t<array<string>, float>): Map.t<string, float> => {
551 // Collect all matrix entries using raw JS
552 let entries = %raw(`
553 (function(matrix) {
554 const result = [];
555 matrix.forEach((value, key) => {
556 result.push([key, value]);
557 });
558 return result;
559 })
560 `)(matrix)
561
562 // Find all paths containing the reference waypoint
563 let pathsWithReference = entries->Array.filter(((path, _)) => {
564 path->Array.some(wpId => wpId == id)
565 })
566
567 if pathsWithReference->Array.length == 0 {
568 Map.make()
569 } else {
570 // Result map: waypoint ID -> relative distance
571 let result = Map.make()
572
573 // For each path containing the reference, calculate relative distances
574 pathsWithReference->Array.forEach(((fullPath, _fullPathDistance)) => {
575 // Find the index of the reference waypoint in this path
576 let refIndex = fullPath->Array.findIndex(wpId => wpId == id)
577
578 if refIndex >= 0 {
579 // Get the reference distance
580 // If refIndex is 0, the reference is the origin, so distance is 0
581 // Otherwise, look it up in the matrix
582 let refDistance = if refIndex == 0 {
583 0.0
584 } else {
585 // Find the matrix entry for the prefix ending at the reference
586 let refPathFromMatrix = entries->Array.find(((path, _)) => {
587 // Check if this path matches the prefix of fullPath up to refIndex
588 if Array.length(path) != refIndex + 1 {
589 false
590 } else {
591 path->Array.everyWithIndex((wpId, idx) => {
592 fullPath->Array.getUnsafe(idx) == wpId
593 })
594 }
595 })
596
597 switch refPathFromMatrix {
598 | None => 0.0
599 | Some((_, dist)) => dist
600 }
601 }
602
603 // Calculate relative distance for each waypoint in the full path
604 fullPath->Array.forEachWithIndex((wpId, idx) => {
605 // Find the matrix entry for this waypoint's prefix
606 let wpPathFromMatrix = entries->Array.find(((path, _)) => {
607 if Array.length(path) != idx + 1 {
608 false
609 } else {
610 path->Array.everyWithIndex((pId, pIdx) => {
611 fullPath->Array.getUnsafe(pIdx) == pId
612 })
613 }
614 })
615
616 // Get the distance for this waypoint
617 // If idx is 0, it's the origin, so distance is 0
618 // Otherwise, look it up in the matrix
619 let wpDistance = if idx == 0 {
620 0.0
621 } else {
622 switch wpPathFromMatrix {
623 | None => 0.0
624 | Some((_, dist)) => dist
625 }
626 }
627
628 // Calculate relative distance: waypoint dist - reference dist
629 let relativeDist = wpDistance -. refDistance
630
631 // Store if this is the first time seeing this waypoint,
632 // or if this path gives a shorter absolute distance
633 switch result->Map.get(wpId) {
634 | None => {
635 result->Map.set(wpId, relativeDist)
636 }
637 | Some(existingDist) => {
638 if Math.abs(relativeDist) < Math.abs(existingDist) {
639 result->Map.set(wpId, relativeDist)
640 }
641 }
642 }
643 })
644 }
645 })
646
647 result
648 }
649}
