What am I doing wrong on this simple test?

[devleaks]

Pease have a look at this gist.

I create a 4 x 4 square (4 horizontal lines of length 4, 4 vertical lines of length 4, total 16 squares, 16 intersections, very simple and straightforward square network.)

Then I ask the route between let's say point (0,1) and (2,0). I would expect an answer of the type (0,1) to (1,1); (1,1) to (2,1); (2,1) to (2,0).

I keep getting null as a path, for whatever starting and ending point I supply. Am I missing something? Do I need to enter each individual vertices and line segments, or does your algorithm compute the intersections of horizontal and vertical lines?

Also, is there a direction to the vertices or are they automatically bi-directional?

Could you please give some hint on where you found the code or algorithm (preprocessor, compactVertices, etc.) I understand most of their global purpose, but cannot easily guess how they work. I understand it is based on Dijkstra shortest path, but it is a bit theoretical and not practical.

Thanks.

Pierre

[devleaks]

OK, got it. You have to add each individual vertex. 0,0 to 0,1, 0,1 to 0,2, etc. I was confused by

lines that start and end, or cross, at the same coordinate are joined text in the doc. But still, Id love some more explanation on the algorithm. Thanks. P.

[perliedman]

Ok, yes - the lines have to cross with nodes on or really close to each other. Could make this clearer in the docs!

But this is resolved for you, right?

[devleaks]

Yes it does. But still, can you provide more info on these points:

• Did you use an existing algorithm (javascript or any other language)? Which one? (code, not theoretical.)
• What needs changing to use directed graphs rather than bi-directional vertices? Thanks. P.

[perliedman]

• The library uses Dijkstra's algorithm (https://github.com/perliedman/geojson-path-finder/blob/master/dijkstra.js)

• I you check the docs on the library's site (http://www.liedman.net/geojson-path-finder/), it tells you:

  The weight function is passed two coordinate arrays (in GeoJSON axis order), as well as the feature properties that are associated with this feature, and should return either:

  • a numeric value for the cost of travelling between the two coordinates; in this case, the cost is assumed to be the same going from a to b as going from b to a
  • an object with two properties: forward and backward; in this case, forward denotes the cost of going from a to b, and backward the cost of going from b to a; setting either to 0, null or undefined will prevent taking that direction, the segment will be a oneway.

  That is, to make it directed, you need to return an object with forward and backward properties, where each of them could be 0 or falsy to prevent that direction from being used.

Good luck!