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

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).

• 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.

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

• Based on pyvisgraph and associated blog posts
  • Distance Tables Part 1: Defining the Problem
  • Distance Tables Part 2: Lee's Visibility Graph Algorithm
• Lee's o(n² log n) Visibility Graph Algorithm paper by Dave Coleman
• Intro to path finding
  • And specifically a bit about visibility graphs