@turf/shortest-path is not giving the shortest path & minDistance option is not working

[bulutkartal]

Algorithm creates extra waypoints and makes the route/path longer than it supposed to be. Also minimum distance option is not working.

Example Fiddle based on documentation test.

Until the first wp under the polygon it created 6 unnecessary waypoints. Also did the same thing when clear from polygon as well.

Also if you zoom in, you will see the path is going over polygon as well.

[rowanwins]

Gday @bulutkartal

Yeah unfortunantly the shortest-path module is still very days. @stebogit might be able to provide more comment as to what he's struggling with...

[bulutkartal]

It is a great start :) Just needs some improvements.

[stebogit]

Hi @bulutkartal, I agree with you this module should perform better. Currently it uses the A* algorithm (see here for some more details), which was a quick (because already implemented) first solution, but it actually operate on a gridded plane so that's why introduces unnecessary points to the path. In https://github.com/Turfjs/turf/issues/788 @rowanwins and @dhivehi reported a couple of much better alternatives, for which though I haven't found a javascript implementation yet.

I believe the minDistance feature could/should be implemented just applying a buffer to each obstacle and run the shortest path with them.

Unfortunately right now I don't have enough time to dedicate to this project. 😞

[rowanwins]

I started looking at a visibility graph to power our astar algorithm, this will do away with the need for the gridded approach, still a little while away though, I'll try and post a link to a public repo tomorrow

[rowanwins]

Here is my WIP repo for constructing a visibility graph from geojson. It's surprising but I can't find any js implementations for constructing visibility graphs. My work is based porting this python lib. I'm still getting my head around the algorithm so it's not working yet but hopefully it's not too far off

[bulutkartal]

Pyvisgraph is a great example. I wish he would do it in c# :(

[rowanwins]

https://github.com/atil/visibilitygraph is c#

[bulutkartal]

I found this research about Deriving an Obstacle-Avoiding Shortest Path in Continuous Space

Vector-based approach looks a lot better than raster-based approach :)

[rowanwins]

Hi @bulutkartal

Thanks for that link, looks like a very helpful paper in understanding shortest path considerations.

I've made reasonable progress on porting pyvisgraph to js - see this demo, there are just some structure things in the API that I want to tidy up to make it more useful.

For example once you have a graph of countries you should be able to reuse that (rather than having to recalcuate it everytime), but you also need the flexibility to add new points (your start and end points) and calculate their visibility.

So my intent is to convert the graph into the ngraph.graph lib which has support for saving graphs, and then use the associated path library for calcuating the shortest path.

So still got some work to do but making progress

[bulutkartal]

Hi @rowanwins , Just found this repository on Github. Could be very helpful for you.

[dhivehi]

Hi, hope this sample will reduce your work on this. https://fribbels.github.io/shortestpath/visgraph.html

[ineeve]

An implementation of the shortest path using the visgraph approach described above would be much appreciated. The current approach has weird behaviours, i.e. fiddle - if you look closely at the end of the red path, it overshoots and then comes back.