GeoJSON Path Finder

Serverless, offline routing in the browser

GeoJSON Path Finder is a standalone JavaScript library for routing/path finding using GeoJSON as input. It can run offline in the browser without any server, or as a part of a Node.js application. It is ideal for simpler use cases where a more complete routing engine like OSRM or GraphHopper is overkill or not possible.

Given a road network in the form of a GeoJSON FeatureCollection of LineString features, the library builds a routable graph which can perform fast shortest path searches. In the demo above, the road network for a smaller sized city (data from OpenStreetMap) is used:

    As can be seen by dragging the waypoint markers, GeoJSON Path Finder runs fast for interactive feedback with a graph of this size.

    The library comes without any user interface, and can easily be integrated in any routing application. The demo above uses Leaflet and Leaflet Routing Machine for the user interface.

    Using

    GeoJSON Path Finder is distributed through npm:

    npm install --save geojson-path-finder

    The API is exposed through the class PathFinder, which is created with the GeoJSON network used for routing:

    var PathFinder = require('geojson-path-finder'),
        geojson = require('./network.json');
    
    var pathFinder = new PathFinder(geojson);

    The network must be a GeoJSON FeatureCollection, where the features have LineString geometries. The network will be built into a topology, so that lines that start and end, or cross, at the same coordinate are joined so that you can find a path from one feature to the other. By default, coordinates very close to each other will also be snapped together; by default coordinates with less than 0.00001 difference in latitude or longitude will be considered the same, but this precision can be adjusted with the precision option:

    var pathFinder = new PathFinder(geojson, { precision: 1e-3 });

    By default, the cost of going from one node in the network to another is determined simply by the geographic distance between the two nodes. This means that, by default, shortest paths will be found. You can however override this by providing a cost calculation function through the weightFn option:

    var pathFinder = new PathFinder(geojson, {
        weightFn: function(a, b, props) {
            var dx = a[0] - b[0];
            var dy = a[1] - b[1];
            return Math.sqrt(dx * dx + dy * dy);
        }
    });
    The weight function is passed two coordinate arrays (in GeoJSON axis order), as well as the feature properties that are associated with this feature, and should return either:
    • a numeric value for the cost of travelling between the two coordinates; in this case, the cost is assumed to be the same going from a to b as going from b to a
    • an object with two properties: forward and backward; in this case, forward denotes the cost of going from a to b, and backward the cost of going from b to a; setting either to 0, null or undefined will prevent taking that direction, the segment will be a oneway.

      To find the shortest (or lowest cost) route between to points, use the findPath method:

      var path = pathfinder.findPath(start, finish);
      start and finish must be GeoJSON Point features, where the coordinates are within the routing network, or at least possible to snap to the network with the PathFinder's precision.

      If a route can be found, an object with two properties: path and weight, is returned, where path is the coordinates the path runs through, and weight is the total weight (distance) of the path.