Terra Route

Terra Route aims to be a fast library for routing on GeoJSON LineStrings networks, where LineStrings share identical coordinates. Terra Routes main aim is currently performance - it uses A* to help achieve this.

Install

npm install terra-route

Docs

API Docs can be found here

Example

Here is a short example of how to use the TerraRoute class:

import { FeatureCollection, LineString, Point, Feature } from "geojson";
import { TerraRoute } from "terra-route"; 

// Sample GeoJSON network (a simple "L" shape)
const network: FeatureCollection<LineString> = {
  type: "FeatureCollection",
  features: [
    {
      type: "Feature",
      geometry: {
        type: "LineString",
        coordinates: [
          [0, 0],   // A
          [0, 1],   // B
          [0, 2],   // C
        ],
      },
      properties: {},
    },
    {
      type: "Feature",
      geometry: {
        type: "LineString",
        coordinates: [
          [0, 1],   // B
          [1, 1],   // D
        ],
      },
      properties: {},
    },
  ],
};

// Define start and end points (A and D)
const startPoint: Feature<Point> = {
  type: "Feature",
  geometry: {
    type: "Point",
    coordinates: [0, 0], // Point A
  },
  properties: {},
};

const endPoint: Feature<Point> = {
  type: "Feature",
  geometry: {
    type: "Point",
    coordinates: [1, 1], // Point D
  },
  properties: {},
};

// Initialize TerraRoute instance
const router = new TerraRoute();

// We must build the route graph first before calling getRoute
router.buildRouteGraph(network);

// Get shortest route
const route = router.getRoute(startPoint, endPoint);

console.log("Shortest route:", JSON.stringify(route, null, 2));

Additional Functionality

Terra Route also exposes functionality for understanding GeoJSON route networks better called LineStringGraph. This can be useful for debugging as this class has a series of methods for determining things like unique nodes, edges, connected components as well as all their counts. With this class you can understand your graph better programmatically, for example determining it's size and if it is correctly connected.

const graph = new LineStringGraph(network);

// Return all nodes in the graph as FeatureCollection<Point>, where each unique node is a Feature<Point>
const graphPoints = graph.getNodes();

// Return all the unique edges as FeatureCollection<LineString>, where each unique edge is a Feature<LineString>
const graphEdges = graph.getEdges(); 

// The longest possible shortest path in the graph between two nodes (i.e. graph diameter)
const longestShortestPath = graph.getMaxLengthShortestPath()

Benchmarks

The benchmarks make use of a series out route example route networks from OSM in a moderate sized section of East London. It runs against the GeoJSON Path Finder library and also the ngraph.graph library. You can run the benchmarks yourself using:

npm run benchmark

Here is an example output of a benchmark run for routing:

Terra Route         | ███████████ 270ms
GeoJSON Path Finder | █████████████████████████ 591ms
ngraph.graph        | ██████████████████████████████████████████████████ 1177ms

Using default Haversine distance, Terra Route is approximately 2x faster than GeoJSON Path Finder with Haversine distance for A -> B path finding. If you pass in the CheapRuler distance metric (you can use the exposed createCheapRuler function), it is approximately x5 faster than GeoJSON Path Finder with Haversine distance.

For initialisation of the network, Terra Route is approximately 10x faster with Haversine than GeoJSON Path Finder. Terra Draw splits out instantiating the Class of the library from the actual graph building, which is done via buildRouteGraph. This allows you to defer graph creation to an appropriate time.

Limitations

• Terra Route does not currently support weighting functions.
• Coordinates must be identical to be considered connected

Acknowledgements

Terra Route is inspired by the the prior art of geojson-path-finder and we use this library to help benchmark Terra Routes performance.

License

MIT