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

Starting Point from an Edge Vertice Returns NULL Result #62

Closed solutegrate closed 4 years ago

solutegrate commented 4 years ago

My network has over 9,000 lines. Everything works perfectly until I pick a starting point from the furthest edges (ie. The furthest line north, sout, east, west). It always returns NULL. If I go to a vertice on those lines back towards the center of the network and start from there it works just fine, but not when I select the outter vertice.

Any suggestions or solutions?

solutegrate commented 4 years ago

Disregard that issue. It is NOT an issue. It was on my end. After looking at the lines on the outer edges, the line I was testing was NOT snapped to next line. So therefore, the path was not being found past that line. You can DELETE this issue.

solutegrate commented 4 years ago

Now that I think of it, is there any way to show where the line breaks if it doesn't complete the path? Like in the instance above.

perliedman commented 4 years ago

No, there isn't. The algorithm can't really know this, there is nothing particular about this node with a break, it's just not connected to the rest of the network (just like a lot of other nodes).

Given some assumptions about the network, you could certainly figure this out, but it is outside the scope of this module.

perliedman commented 4 years ago

It would probably not be too much work to implement a "reachability graph" or similar, dividing the network into subgraphs that can't reach each other. That could give you information that is at least similar to what you ask for.

solutegrate commented 4 years ago

So what you’re saying is when I pass the featureCollection in, it would check for “reachability “ then? Or would it check when I run the findPath function?

It would be super awesome to have both features. I could then use this to check for “non-snapped” lines in my network. That would be huge to give my clients that detail and know where/what they need to fix. Huge time save on the engineers part.

On Apr 30, 2020, at 7:27 AM, Per Liedman notifications@github.com wrote:

 It would probably not be too much work to implement a "reachability graph" or similar, dividing the network into subgraphs that can't reach each other. That could give you information that is at least similar to what you ask for.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or unsubscribe.

perliedman commented 4 years ago

Making a reachability graph would be a separate function from findPath, it would divide the network into "islands" / subgraphs / subnetworks that can't reach each other. It's a pretty common concept in graph theory and path finding.

As mentioned, this is probably not a lot of work to add, but I'm not actively working on this module now, so don't count on me adding it!