rowanwins / visibility-graph Goto Github PK

View Code? Open in Web Editor NEW

49.0 7.0 7.0 3.66 MB

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

Home Page: https://rowanwins.github.io/visibility-graph/debug/dist

License: MIT License

JavaScript 95.73% Vue 3.27% HTML 1.00%

visibility-graph javascript

visibility-graph's Introduction

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

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

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

visibility-graph's People

Contributors

Stargazers

Watchers

Forkers

poojakashyap121 msand barkaboss abentkamp myausweis tspoke studio501

visibility-graph's Issues

Visibility graph calculation is very slow for large polygon set

Visibility graph can be optimized by removing unneeded lines.
If both ends of a line is tangent to a polygon, then it's needed. Else it is not needed.
Please make a way to check if p1 and p2 are tangent to a polygon before adding to visibility graph as it would make visibility graph generation multiple times faster.

Visibility in spherical geometry

Another addition that would be amazing is if the visibility between vertices could be configured to run on spherical geometry rather than Euclidean. Currently the solution works better for smaller distances, especially closer to the equator where the effects of Euclidean geometry make less of a difference, which I guess is just part of its design, and makes this suitable for use in some applications and not others depending on how long the routes are and how accurate the answer needs to be.

As an example, there is a great circle between points [10, 80], [-140, 70] on an earth sphere that does not intersect any land boundaries, however in Euclidean geometry the line between the 2 points intersects Greenland and the shortest path generated hugs its coastline. In reality this represents a detour from the actual direct path of about 100km.

Similarly 2 points that are visible in Euclidean geometry may not actually be on a sphere.

I appreciate that this change may be considered out of scope for this library, especially since I haven't found any other library that implements it, or many google hits on the topic at all, but thought worth raising for documentation for other users coming across this! I would have a go at forking this library and trying to implement a spherical visibility solution if my current geometry skills were up to the challenge! Worth noting on a similar discussion on an issue for the pyvisgraph library, where a solution (complicated sounding) does seem to be proposed. I expect any spherical based graph would take more time to generate, but the existing ability to write the graph to file could help with that.

Path finding chooses strange path because links have no weight

This issue is more for the benefit of future users than a request to change anything.

I was banging my head about why my pathfinding was not picking the shortest path, and instead chose to make a giant detour along a graph edge that was going away from my target position.
Incomprehensible...
Then after many hours of debugging, I realized that links do not have any weight. Therefore the pathfinding just picks the shortest number of edges, regardless of the length of these edges.

Adding weights to the links magically solved it.

    const pathFinder = nGraphPath.aStar(collisionGraph, {
      distance: (fromNode: Node, toNode: Node, link: Link) => (link as any).weight,
    });
    collisionGraph.forEachLink((link) => {
      const [fromNodeX, fromNodeY] = (link.fromId as string).split(',');
      const [toNodeX, toNodeY] = (link.toId as string).split(',');
      (link as any).weight = distanceBetweenCoordinates(+fromNodeX, +fromNodeY, +toNodeX, +toNodeY);
    });

I can understand why this package does not automatically add link distances/weight to the graph. One may not need them, and it takes extra time to compute. Or we may want a different distance metric. Many reason not to have them by default.

Suggestion: I could see it as an option:

const graph = createGraphFromGeoJson(MultiPolygon, { linkWeight: (fromNode, toNode) => euclidianDistance(fromNode, toNode) })

Touch screen on mobile demo

Hi, Rowan!

Thank you for the implementation and very nice demo! When I was on mobile phone (iPhone) I couldn't tell what this library is doing because I was trying to drag the "pin-point" icons.

It would be awesome to have the demo mobile friendly :).

Think about how to pass in a point to add it to the graph

Back in pyvisgraph a user can pass in a start or an end point and effectively get it to become part of the graph.

Currently on my demo I'm cheating and just finding the nearest point...

The challenge is that my createGraphFromGeoJson() returns the ngraph and you loose all the other info required to add a new point to the graph...

Shortest Path with no obstacles

Enjoying using this library so thanks very much! I arrived here as am using turf.js in a project where we are calculating marine isochrones and the results from this library better suit our use case than turf.shortestPath as we can get multiple results much quicker.

However one case where turf.shortestPath currently works better is when there are no obstacles in between the 2 points thus a direct path between the 2 points can be found. visibility-graph.js appears to do a detour via a point on the obstacles polygon (see image below). Not sure if this is an issue with visibility-graph.js or one of the underlying ngraph libraries - any idea if it might be a simple fix or an inherent behaviour of the method? Or if there's a simple workaround? Haven't delved too far into the source code (certainly not into the graph library source code) so not in a position to submit a PR at this moment!

Does not work on extremely concave shapes or "tunnels"

See the given examples below

GeoJSON of barriers:

{
	type: 'FeatureCollection',
	features: [
		{
			type: 'Feature',
			properties: {},
			geometry: {
				type: 'Polygon',
				coordinates: [
					[
						[-80.135651, 43.543073],
						[-80.112991, 43.546806],
						[-80.112648, 43.542825],
						[-80.129128, 43.534363],
						[-80.135651, 43.543073],
					],
				],
			},
		},
		{
			type: 'Feature',
			properties: {},
			geometry: {
				type: 'Polygon',
				coordinates: [
					[
						[-80.102348, 43.533865],
						[-80.102348, 43.54382],
						[-80.080376, 43.54382],
						[-80.084839, 43.536603],
						[-80.102348, 43.533865],
					],
				],
			},
		},
		{
			type: 'Feature',
			properties: {},
			geometry: {
				type: 'Polygon',
				coordinates: [
					[
						[-80.078316, 43.527642],
						[-80.054283, 43.532123],
						[-80.0457, 43.518431],
						[-80.075226, 43.520672],
						[-80.078316, 43.527642],
					],
				],
			},
		},
		{
			type: 'Feature',
			properties: {},
			geometry: {
				type: 'Polygon',
				coordinates: [
					[
						[-80.110931, 43.565467],
						[-80.075226, 43.569944],
						[-80.091019, 43.557754],
						[-80.110931, 43.565467],
					],
				],
			},
		},
		{
			type: 'Feature',
			properties: {},
			geometry: {
				type: 'Polygon',
				coordinates: [
					[
						[-80.056686, 43.553773],
						[-80.0354, 43.555515],
						[-80.0354, 43.543322],
						[-80.069046, 43.549046],
						[-80.056686, 43.553773],
					],
				],
			},
		},
		{
			type: 'Feature',
			properties: {},
			geometry: {
				type: 'Polygon',
				coordinates: [
					[
						[-80.131531, 43.558501],
						[-80.141487, 43.573178],
						[-80.16346, 43.573178],
						[-80.161057, 43.568203],
						[-80.178223, 43.558501],
						[-80.178223, 43.548299],
						[-80.158997, 43.545562],
						[-80.158653, 43.557008],
						[-80.151443, 43.557754],
						[-80.131531, 43.558501],
					],
				],
			},
		},
		{
			type: 'Feature',
			properties: {},
			geometry: {
				type: 'Polygon',
				coordinates: [
					[
						[-80.124664, 43.587603],
						[-80.096512, 43.589841],
						[-80.095825, 43.585365],
						[-80.108185, 43.576909],
						[-80.123634, 43.575417],
						[-80.120888, 43.570193],
						[-80.129128, 43.568701],
						[-80.138054, 43.593571],
						[-80.124664, 43.587603],
					],
				],
			},
		},
		{
			type: 'Feature',
			properties: {},
			geometry: {
				type: 'Polygon',
				coordinates: [
					[
						[-80.053253, 43.571437],
						[-80.026474, 43.580142],
						[-80.03746, 43.5881],
						[-80.043983, 43.585862],
						[-80.063553, 43.595311],
						[-80.063553, 43.590836],
						[-80.048447, 43.584867],
						[-80.038834, 43.583624],
						[-80.035057, 43.580391],
						[-80.04055, 43.580391],
						[-80.056, 43.581883],
						[-80.064583, 43.58437],
						[-80.068359, 43.586608],
						[-80.070419, 43.592328],
						[-80.074883, 43.590587],
						[-80.065269, 43.578899],
						[-80.052223, 43.578899],
						[-80.042953, 43.578152],
						[-80.053253, 43.571437],
					],
				],
			},
		},
		{
			type: 'Feature',
			properties: {},
			geometry: {
				type: 'Polygon',
				coordinates: [
					[
						[-80.136166, 43.529385],
						[-80.178566, 43.543322],
						[-80.20483, 43.509842],
						[-80.20277, 43.50897],
						[-80.177879, 43.539838],
						[-80.142002, 43.528638],
						[-80.143547, 43.527144],
						[-80.156765, 43.530754],
						[-80.163803, 43.520547],
						[-80.149899, 43.517186],
						[-80.163631, 43.501624],
						[-80.167751, 43.502496],
						[-80.156422, 43.515942],
						[-80.161743, 43.517809],
						[-80.172386, 43.50511],
						[-80.178223, 43.506231],
						[-80.167751, 43.518805],
						[-80.177536, 43.520921],
						[-80.182171, 43.507974],
						[-80.190239, 43.510215],
						[-80.179253, 43.526024],
						[-80.16861, 43.522166],
						[-80.16037, 43.531625],
						[-80.176163, 43.535856],
						[-80.19659, 43.507351],
						[-80.161057, 43.497017],
						[-80.136166, 43.529385],
					],
				],
			},
		},
	],
};

a labyrinth demo

I've heard about visibility graph a few times now. I'm curious would it be possible to achieve something like https://www.redblobgames.com/articles/visibility/ with this library?

On a surface it does seem like this is possible. Would it also be possible to apply visibility graph in higher dimensions?

I hope this does not sound like a silly or lazy question. Just curious about your thoughts, as you clearly worked with this quite a bit!