search

perliedman / geojson-path-finder

Find shortest path through a network of GeoJSON
https://www.liedman.net/geojson-path-finder/
ISC License
300 stars 86 forks source link

Returning null, tried multiple tolerances #82

Closed rbsam176 closed 1 year ago

rbsam176 commented 1 year ago

Hey all, I'm really hoping I can get this working as it'll be so much easier than figuring out how to deploy pgRouting. It looks as though if I set the start/end coordinates to match existing coordinates from the network, then it will work, but if the start/end coordinates are nearby then it returns null. From what I've understood from other issues raised this is because some snapping needs to be introduced so that the nearby coordinate start/end points are linked to the closest point in the network. I've tried using different tolerance values but nothing seems to get it to return a value. Even if changing the tolerance worked, I'm not sure how best to handle this if the users start/end point is entered by them either by their real live location or by tapping a map, how will the app know which tolerance to use?

I've set up a jsfiddle which displays the map start/end points and has a demo network in there, you'll see if you open the console that it returns "Best path: null".

What am I missing here? Thanks for the help!

https://jsfiddle.net/rbsam176/ztx5ewdv/39/

EDIT: I should point out, even when I place the start/end points matching coordinates that the network is using (eg. the point sits directly on the line) then it still doesn't seem to work: https://jsfiddle.net/rbsam176/ztx5ewdv/43/ (to see what I mean, copy any of the start/end point coordinates and you'll find it in the geoJson object containing the network data)

pbvahlst commented 1 year ago

It seems that you are using the old version (1.5.3) where tolerance was called precision, try renaming tolerance to precision and then set it to 1e-2, then it will work for your example. 1e-2 as precision is a little to diffuse in my opinion though as it will cause a lot of false positive when the graph is being created. A better approach is to take the user input and then from that find the closest actual point in your geoJSON data, you can use turf.js for that and then use the actual point as input. Furthermore make sure that the different LineString features actual connect (or at least the points where they should connect is within the set tolerance) otherwise they will not be connected in the graph.

rbsam176 commented 1 year ago

Hi @pbvahlst, thanks for that! I'll take a look at turf.js to find the closest point. With the LineString features connecting, I've been using geojson.io and it can quite difficult to ensure the points are connected - can you recommend an alternative that will purposely connect the dots?

pbvahlst commented 1 year ago

Apps like qgis https://www.qgis.org/en/site/forusers/download.html has a snapping option, otherwise you can edit the point data manually to identical positions where there should be a connection.

rbsam176 commented 1 year ago

Really appreciate the help @pbvahlst, I will try your suggestions (probably tomorrow) and return to close if successful. EDIT: didn't get time to try today, but I will come back and close once I'm able to

rbsam176 commented 1 year ago

@pbvahlst Thanks for the QGIS suggestion, it works a lot better! So I've got GeoJSON-path-finder reliably returning a GeoJSON line (using turf.js to find the closest snapping point), but the returning line seems to not start/end from the starting/ending coordinates.

Take a look at this screenshot.

It's not super clear, but the blue line represents what GeoJSON-path-finder returned, the 2 marker icons represent the starting/ending coordinates (after being snapped by turf.js) and the orange dots represent the network.

It looks like the line being returned from GeoJSON-path-finder is snapping to the nearest point from the network, rather than at the points I specified. Is this expected behaviour?

EDIT: looking at the demo on the homepage it has similar behaviour, with the only difference being the map displays a separate dashed grey line that links the marker position to the start of the route. Is there not a way to make it always show the route from the starting/ending coordinate position like Google Maps? The only solution I can think of is to set QGIS to add points every interval distance (as explained in this post), or splitting the lines into equal segment, but I'm not sure if this is the best way or not.

pbvahlst commented 1 year ago

Yes that is expected, so you need to add the last part yourself. You could use turf to find closest calculated point on the line, it will also return the closest index of an actual point which you can use to get a point to use as input to the path finder, then after the path has been calculated add the calculated point to the result so you extend the result with the calculated point. If you also accept off road positions then further add the off road point to the calculated path.