/visibility-graph

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

Primary LanguageJavaScriptMIT LicenseMIT

visibility-graph.js

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

Demo

Documentation

Valid inputs: A polygon or multi-polygon feature or geometry.

  var out = createGraphFromGeoJson(MultiPolygon)

Output is a graph from the ngraph library.

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

  • Once you've created your visibililty graph it is possible to save it, and then load it late, this can be achieved with ngraph.tojson and ngraph.fromjson packages.
  • Path finding can be achieved with the ngraph.path package.

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 50 seconds

References & Credits