-
Notifications
You must be signed in to change notification settings - Fork 1
/
closestfinder.ts
78 lines (69 loc) · 3.07 KB
/
closestfinder.ts
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
import {distance as fakeDistance, closestOnSegment} from 'ol/coordinate.js';
import type {Coordinate} from 'ol/coordinate.js';
export interface ClosestPoint {
distanceFromStart: number;
distanceFromSearched: number;
coordinates: Coordinate;
fullLength?: number;
}
export interface ClosestLinesOptions {
tolerance: number;
interpolate: boolean;
}
export function findClosestPointInLine(coordinatess: Coordinate[], searched: Coordinate, previousLineLength: number, interpolate: boolean): ClosestPoint {
let currentLineLength = 0; // from XYZM data
let previous = coordinatess[0];
const best: ClosestPoint = {
distanceFromStart: 0,
distanceFromSearched: Number.POSITIVE_INFINITY,
coordinates: coordinatess[0],
};
for (let i = 0; i < coordinatess.length; ++i) {
let coordinates = coordinatess[i];
const segmentLength = coordinates[3] - previous[3];
console.assert(Number.isFinite(segmentLength) && segmentLength >= 0);
currentLineLength += segmentLength;
const originalCoordinates = coordinates;
let distanceFromStart = currentLineLength;
if (interpolate && i > 0 && segmentLength > 0) {
const newCoordinates = closestOnSegment(searched, [previous, coordinates]);
// FakeDistance is accurate for local projections in meters (like EPSG:2056)
// but not for mercator, because the distances between coordinates on the map
// depends on the latitude.
// Since we compare coordinates close to each other (at same latitude), the ratio of
// distances can be considered accurate with mercator.
// So, to avoid reprojecting our coordinates and use great circle formulas,
// we compute euclidian distances and use their ratio to get the interpolated (accurate) distance.
const fakeD1 = fakeDistance(previous, newCoordinates);
const fakeD2 = fakeDistance(newCoordinates, coordinates);
const estimatedMDistanceToEnd = segmentLength * fakeD2 / (fakeD1 + fakeD2);
distanceFromStart = currentLineLength - estimatedMDistanceToEnd;
coordinates = newCoordinates;
}
const distanceFromSearched = fakeDistance(searched, coordinates);
if (distanceFromSearched < best.distanceFromSearched) {
best.distanceFromSearched = distanceFromSearched;
best.coordinates = coordinates;
best.distanceFromStart = previousLineLength + distanceFromStart;
}
previous = originalCoordinates;
}
best.fullLength = previousLineLength + currentLineLength;
return best;
}
export function findClosestPointInLines(lines: Coordinate[][], searched: Coordinate, options: ClosestLinesOptions): ClosestPoint {
const {tolerance, interpolate} = options;
const bests = [];
let previousDistance = 0;
for (const line of lines) {
const best = findClosestPointInLine(line, searched, previousDistance, interpolate);
bests.push(best);
if (best.distanceFromSearched <= tolerance) {
return best;
}
console.assert(best.fullLength !== undefined);
previousDistance = best.fullLength;
}
bests.sort((a, b) => a.distanceFromSearched - b.distanceFromSearched);
return bests[0];
}