Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 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 | 2x 2x 2x 38x 38x 38x 38x 38x 38x 38x 44x 41x 93x 44x 44x 105x 44x 44x 44x 44x 44x 3x 3x 3x 3x 3x 3x 3x 3x 37x 35x 35x 4x 33x 33x 33x 33x 31x 31x 31x 2x 44x | import { KDBush } from "./kdbush/kdbush";
import { around } from "./kdbush/geokdbush";
import {
FeatureCollection,
LineString,
Position,
Feature,
Point,
} from "geojson";
export type RouteFinder = {
getRoute: (positionA: Feature<Point>, positionB: Feature<Point>) => Feature<LineString> | null
setNetwork: (network: FeatureCollection<LineString>) => void
expandNetwork: (additionalNetwork: FeatureCollection<LineString>) => void
}
export interface RoutingInterface {
getRoute: (
startCoord: Position,
endCoord: Position
) => Feature<LineString> | null;
getClosestNetworkCoordinate: (coordinate: Position) => Position | null;
setRouteFinder: (routeFinder: RouteFinder) => void;
setNetwork: (network: FeatureCollection<LineString>) => void
}
/**
* Routing class for finding routes on a network of LineStrings.
* The LineString network must have coordinates that are shared between
* the LineStrings in order to find a route.
*/
export class Routing implements RoutingInterface {
constructor(options: {
network: FeatureCollection<LineString>, useCache?: boolean,
routeFinder: RouteFinder
}) {
this.useCache = options.useCache !== undefined ? options.useCache : true;
this.network = this.clone(options.network);
this.routeFinder = options.routeFinder;
this.initialise();
}
private useCache: boolean = true;
private indexedNetworkPoints!: KDBush;
private points: Position[] = []
private routeFinder: RouteFinder;
private network: FeatureCollection<LineString>;
private routeCache: Record<string, Feature<LineString> | null> = {};
// Initialise the routing instance setting internal data structures
private initialise() {
this.network.features.forEach((feature) => {
feature.geometry.coordinates.forEach((coordinate) => {
this.points.push(coordinate);
});
});
this.indexedNetworkPoints = new KDBush(this.points.length);
this.points.forEach(coordinate => {
this.indexedNetworkPoints.add(coordinate[0], coordinate[1]);
})
this.indexedNetworkPoints.finish();
this.routeCache = {};
}
/**
* Return the closest network coordinate to the input coordinate
* @param inputCoordinate The coordinate to find the closest network coordinate to
* @returns a coordinate on the network or null if no coordinate is found
*/
public getClosestNetworkCoordinate(inputCoordinate: Position) {
const aroundInput: number[] = around(
this.indexedNetworkPoints,
inputCoordinate[0],
inputCoordinate[1],
1
);
const nearest = this.points[aroundInput[0]]
return nearest ? nearest : null;
}
/**
* Set the route finder for the routing instance
* @param routeFinder The route finder to use
*/
public setRouteFinder(routeFinder: RouteFinder) {
this.routeFinder = routeFinder;
}
/**
* Set the network for the routing instance
* @param network The network to use
*/
public setNetwork(network: FeatureCollection<LineString>) {
this.network = this.clone(network);
// Ensure the network is updated correctly for the router finder
this.routeFinder.setNetwork(network);
// Re-initialize all internal data structures for this class
this.initialise();
}
public expandRouteNetwork(additionalNetwork: FeatureCollection<LineString>) {
const clonedNetwork = this.clone(additionalNetwork);
// Ensure the network is updated correctly for the router finder
this.routeFinder.expandNetwork(clonedNetwork);
const mergedNetwork = {
type: "FeatureCollection",
features: [...clonedNetwork.features, ...this.network.features]
} as FeatureCollection<LineString>;
this.network = mergedNetwork;
// Re-initialize all internal data structures for this class
// TODO: Is there a way to avoid re-initialising here?
this.initialise();
}
/**
* Get the route between two coordinates returned as a GeoJSON LineString
* @param startCoord start coordinate
* @param endCoord end coordinate
* @returns The route as a GeoJSON LineString
*/
public getRoute(startCoord: Position, endCoord: Position): Feature<LineString> | null {
// Check if caching is enabled, and if the coordinates are already in the cache
if (this.useCache) {
const routeKey = `${startCoord}-${endCoord}`;
// Use 'in' to account for the route potentially being null
if (routeKey in this.routeCache) {
return this.routeCache[routeKey];
}
}
const start = {
type: "Feature",
geometry: {
type: "Point",
coordinates: startCoord,
},
properties: {},
} as Feature<Point>;
const end = {
type: "Feature",
geometry: {
type: "Point",
coordinates: endCoord,
},
properties: {},
} as Feature<Point>;
const route = this.routeFinder.getRoute(start, end);
// If caching is enabled, store the route in the cache
if (this.useCache) {
const routeKey = `${startCoord}-${endCoord}`
this.routeCache[routeKey] = route;
return route;
}
return route;
}
private clone(network: FeatureCollection<LineString>) {
return JSON.parse(JSON.stringify(network)) as FeatureCollection<LineString>;
}
}
|