visibility-graph

visibility-graph.js

Visibility graph implementation to support shortest path calculations such as dijkstra or a-star.

Demo

Documentation

This library exposes a VisibilityGraph class

API

new VisibilityGraph(geojson, ?existingGraph) - creates a new instance using a Polygon or MultiPolygon feature or geometry. Optionally, if you have an existing graph that you’ve previously generated using the .saveGraphToJson() you can pass it in as a argument.

.saveGraphToJson() - Returns a json representation of the visibility graph which can be saved to disk and then restored by passing a second argument to the class constructor.

.addStartAndEndPointsToGraph(origin, destination) - Takes 2 geojson point features, one for the origin, and one for the destination, and returns the newly added nodes in an object {startNode: ngraphNode, endNode: ngraphNode}. Each time this is called any previously added start and end points are removed from the graph.

.getNodeIdByLatLon([lat, lon]) - Returns a graph node ID that matches the lat lon.

Example

  import VisibilityGraph from 'visibility-graph.js'
  import path from 'ngraph.path'

  // Create the visibility graph from the geojson data
  const vg = new VisibilityGraph(geojson)

  // Use the 'ngraph.path' library to find a way 
  //through the newly created visibility graph
  const pathFinder = path.nba(vg.graph, {
    distance (fromNode, toNode) {
      const dx = fromNode.data.x - toNode.data.x
      const dy = fromNode.data.y - toNode.data.y
      return Math.sqrt(dx * dx + dy * dy)
    }
  })

  // Add the start and endpoints to the graph  
  const startEndNodes = vg.addStartAndEndPointsToGraph(
    {type: 'Feature', geometry: {type: 'Point', coordinates: [0, 0]}},
    {type: 'Feature', geometry: {type: 'Point', coordinates: [10, 10]}}
  )
  
  // And finally retrive the optimal path 
  const optimalPath = pathFinder.find(
    startEndNodes.startNode.nodeId,
    startEndNodes.endNode.nodeId
  )

NOTE: If you get occassional issues with how your edges are being linked try reducing the precision of your coordinates (eg 8 decimal places).

Using with other packages

Performance

The process of creating a visibility graph can be slow depending on the number of vertices in your input geometry.

Scenario Nodes/Vertices Create Graph Time Reload Graph / Graph Size
Australia 250 1 second 300kb
Asia 1400 4 seconds 100ms / 5.2MB
World 4400 20 seconds  

Depending on your requirements you may also be able to convert your input data if it has concave polygons, to only having convex polygons, this may reduce redundant nodes in the graph.

References & Credits