Duplication in Path Coordinates

[s9eenk]

Tried to generate a path between two points between [83.31445144513499 , 17.72926803821786] and [83.31453081217354 , 17.72926638959088] using node js which shows the path coordinates as {"coordinates":[[83.314451445135,17.729268760947598],[83.31448887846574,17.72927938499293],[83.3145300894438,17.729266183096673],[83.31453870265632,17.729238156171558],[83.31453870265632,17.729238156171558]]}

Due to this facing an issue as shown in the figure attached .

Moreover , attaching the dataset too for consideration. Dataset.txt

Any help regarding this would be appreciated. Thanks in advance.

[perliedman]

Hi there, and thanks for reporting. I've tried your example and it does indeed give weird results.

One thing I noted is that your coordinates are very close to each other: even on the most zoomed in OpenStreetMap zoom level, this road network is tiny.

I think what is happening is that your network is snapped together since the coordinates are too close, I notice at least some of them are below the default precision of 1e-5, which will cause problems.

I also tried lowering the precision, but got some other error which will have to be investigated closer.

For the record, here's the code I'm using:

var PathFinder = require('geojson-path-finder'),
    point = require('@turf/helpers').point,
    geojson = {
        "type": "FeatureCollection",
        "crs": { "type": "name", "properties": { "name": "urn:ogc:def:crs:OGC:1.3:CRS84" } },
        "features": [
            { "type": "Feature", "properties": { "Direction": "72.8607", "Distance": "7.016", "X": 20.12, "Y": 21.3, "Z": 0.0, "Radius": 3.51, "len": 7.34 }, "geometry": { "type": "LineString", "coordinates": [ [ 83.31452283096985, 17.729289021128807 ], [ 83.314586258062363, 17.729306950185151 ] ] } },
            { "type": "Feature", "properties": { "Direction": "72.8586", "Distance": "3.26", "X": 25.25, "Y": 21.3, "Z": 0.0, "Radius": 1.63, "len": 3.41 }, "geometry": { "type": "LineString", "coordinates": [ [ 83.314586258062363, 17.729306950185151 ], [ 83.314615723941642, 17.729315280465716 ] ] } },
            { "type": "Feature", "properties": { "Direction": "342.3551", "Distance": "2.643", "X": 16.65, "Y": 20.0, "Z": 0.0, "Radius": 1.32, "len": 2.67 }, "geometry": { "type": "LineString", "coordinates": [ [ 83.314530089443807, 17.729266183096673 ], [ 83.31452283096985, 17.729289021128807 ] ] } },
            { "type": "Feature", "properties": { "Direction": "342.8844", "Distance": "3.235", "X": 16.65, "Y": 17.05, "Z": 0.0, "Radius": 1.62, "len": 3.26 }, "geometry": { "type": "LineString", "coordinates": [ [ 83.314538702656321, 17.729238156171558 ], [ 83.314530089443807, 17.729266183096673 ] ] } },
            { "type": "Feature", "properties": { "Direction": "341.7546", "Distance": "1.828", "X": 16.65, "Y": 14.52, "Z": 0.0, "Radius": 0.91, "len": 1.85 }, "geometry": { "type": "LineString", "coordinates": [ [ 83.314543894756326, 17.729222413650419 ], [ 83.314538702656321, 17.729238156171558 ] ] } },
            { "type": "Feature", "properties": { "Direction": "73.0183", "Distance": "3.599", "X": 31.9, "Y": 21.3, "Z": 0.0, "Radius": 1.8, "len": 3.76 }, "geometry": { "type": "LineString", "coordinates": [ [ 83.314644986414436, 17.729323551717595 ], [ 83.314677551310012, 17.72933266364608 ] ] } },
            { "type": "Feature", "properties": { "Direction": "343.0931", "Distance": "13.339", "X": 23.65, "Y": 27.94, "Z": 0.0, "Radius": 6.67, "len": 13.46 }, "geometry": { "type": "LineString", "coordinates": [ [ 83.314586258062363, 17.729306950185151 ], [ 83.314551179554059, 17.729422646899184 ] ] } },
            { "type": "Feature", "properties": { "Direction": "343.4346", "Distance": "13.395", "X": 26.9, "Y": 26.3, "Z": 0.0, "Radius": 6.7, "len": 13.51 }, "geometry": { "type": "LineString", "coordinates": [ [ 83.314615723941642, 17.729315280465716 ], [ 83.314596813960847, 17.72937906638888 ], [ 83.314581221718186, 17.729431661115608 ] ] } },
            { "type": "Feature", "properties": { "Direction": "252.7980", "Distance": "4.142", "X": 10.8, "Y": 21.3, "Z": 0.0, "Radius": 2.07, "len": 4.33 }, "geometry": { "type": "LineString", "coordinates": [ [ 83.314488878465738, 17.729279384992932 ], [ 83.314451445135006, 17.729268760947598 ] ] } },
            { "type": "Feature", "properties": { "Direction": "252.7980", "Distance": "3.757", "X": 14.74, "Y": 21.3, "Z": 0.0, "Radius": 1.88, "len": 3.93 }, "geometry": { "type": "LineString", "coordinates": [ [ 83.31452283096985, 17.729289021128807 ], [ 83.314488878465738, 17.729279384992932 ] ] } },
            { "type": "Feature", "properties": { "Direction": "252.7980", "Distance": "2.436", "X": 7.54, "Y": 21.3, "Z": 0.0, "Radius": 1.22, "len": 2.55 }, "geometry": { "type": "LineString", "coordinates": [ [ 83.314451445135006, 17.729268760947598 ], [ 83.314429429093025, 17.729262512516708 ] ] } },
            { "type": "Feature", "properties": { "Direction": null, "Distance": null, "X": null, "Y": null, "Z": null, "Radius": null, "len": 5.13 }, "geometry": { "type": "LineString", "coordinates": [ [ 83.314631468112822, 17.729367564510756 ], [ 83.314644986414422, 17.729323551717602 ] ] } },
            { "type": "Feature", "properties": { "Direction": null, "Distance": null, "X": null, "Y": null, "Z": null, "Radius": null, "len": 3.39 }, "geometry": { "type": "LineString", "coordinates": [ [ 83.314615723941657, 17.72931528046573 ], [ 83.314644986414422, 17.729323551717602 ] ] } }
        ]
    };

var pathFinder = new PathFinder(geojson, {precision: 1e-6});

var path = pathFinder.findPath(
    point([83.31445144513499 , 17.72926803821786]),
    point([83.31453081217354 , 17.72926638959088]));

var pathGeoJson = {
    type: 'Feature',
    properties: { weight: path.weight },
    geometry: {
        type: 'LineString',
        coordinates: path.path
    }
};

console.log(JSON.stringify(pathGeoJson, null, 2));

This gives the error:

per@linfro:~/Documents/tmp/geojson-path-finder-12$ node index.js 
/home/per/Documents/tmp/geojson-path-finder-12/node_modules/geojson-path-finder/compactor.js:45
    return Object.keys(neighbors).reduce(function compactEdge(result, j) {
                  ^

TypeError: Cannot convert undefined or null to object
    at Object.compactNode (/home/per/Documents/tmp/geojson-path-finder-12/node_modules/geojson-path-finder/compactor.js:45:19)
    at Object._createPhantom (/home/per/Documents/tmp/geojson-path-finder-12/node_modules/geojson-path-finder/index.js:104:33)
    at Object.findPath (/home/per/Documents/tmp/geojson-path-finder-12/node_modules/geojson-path-finder/index.js:69:33)
    at Object.<anonymous> (/home/per/Documents/tmp/geojson-path-finder-12/index.js:25:23)
    at Module._compile (module.js:570:32)
    at Object.Module._extensions..js (module.js:579:10)
    at Module.load (module.js:487:32)
    at tryModuleLoad (module.js:446:12)
    at Function.Module._load (module.js:438:3)
    at Module.runMain (module.js:604:10)

[s9eenk]

Hi , @perliedman . Thanks for your response. Gone through GeoJSON Path Finder Demo Link (WebApp). Used the same replica what you have developed with the same Dataset , it gives perfect path. Here's the Node JS Code:

var PathFinder = require('geojson-path-finder'), geojsonSRKDestiny4FloorReroute = require('./SRK-Floor_4-Reroute/network.json'), explode = require('turf-explode'), nearest = require('turf-nearest');

var pathFinderReroute = new PathFinder(geojsonSRKDestiny4FloorReroute); var pointsReroute = explode(geojsonSRKDestiny4FloorReroute), start = point([83.31445144513499 , 17.72926803821786]), end = point([83.31453081217354 , 17.72926638959088]), startInNetwork = nearest(start, pointsReroute), endInNetwork = nearest(end, pointsReroute), path = pathFinderReroute.findPath(startInNetwork, endInNetwork);

var geometry = "LineString"; var sendData = { "type": geometry, "coordinates": path.path } console.log(sendData);

Output: {"type":"LineString","coordinates":[[83.314451445135,17.729268760947598],[83.31448887846574,17.72927938499293],[83.3145300894438,17.729266183096673],[83.3145300894438,17.729266183096673]]}

I don't know what is making difference in webApp code and Node JS code . Perplexed.

[Resonance1584]

@perliedman I also ran into some of these issues in a fork I'm using to develop a small project. I haven't identified exactly why they occur so I'm not sure if my fixes are useful or if they're just breaking other things.

• TypeError: Cannot convert undefined or null to object I found that this occurs if the start and end coordinates did not exactly match coordinates in the geojson - so I'm tweaking my input data to exactly match.
• I also found that the rounding function will sometimes produce floating point errors - eg. a coordinate will be rounded to -45.12345600000000002. I'm not sure if this also causes the undefined or null object, but I changed the rounding to use .toFixed(6) instead - in case this was causing issues.
• I also found that the final coordinate was repeated, but not duplicated - it's the exact same object causing me to pull my hair out trying to map .reverse across all the coords (it ran twice on the same coordinate object leaving the order unchanged). I removed the call to .concat on https://github.com/perliedman/geojson-path-finder/blob/master/index.js#L46 which fixed this issue for me. I'm wondering if this is a side effect of using the exact same coordinates as start and end calls.

Like I said - not sure if I'm just breaking other features here - the change to rounding suits my data well but would need some additional logic to support user supplied precision. Let me know if you want me to investigate further / open PRs.

[nemosmithasf]

@perliedman Did you ever get a chance to investigate what might be causing this problem? It seems like its caused when two nodes collapsed into a single one, but changing the precision value doesn't seem to help.

See this:

EDIT: Setting compact: false seems to fix the problem. What exactly is the difference between compact and precision? Also, as a heads up, the documentation is missing for compact

[perliedman]

Compacting the graph means removing all nodes that only have one or two edges, which mean there isn't a choice in how to proceed from this node. For common road networks, a large majority of the nodes are of this type, and they don't affect routing, but they take a lot of extra time for the routing algorithm to traverse. So, for a large network you more or less have to use compaction to achieve speed. The original, uncompacted nodes are then only used for display.

Having said that, it appears you have found a bug in the compaction algorithm, since it shouldn't affect routing results, only performance, if you turn it off or on. I can for example imagine that there can be an issue if two nodes are collapsed into one.

Unfortunately, it's been a bit long since I worked on this code and I don't really have the time to dig into it at the moment, any help appreciated!

[perliedman]

Not sure if related, but I merged #70, a fix for #27, which is also related to compaction, just now, so you might want to try with latest version 1.5.3 if you still have this problem.

[nickw1]

@s9eenk @nemosmithasf I think that fix #70, which I contributed, will solve this problem. Like @perliedman I am unlikely to have much time to fix if it doesn't, but from the description here I think it will.

[IPWright83]

Compacting the graph means removing all nodes that only have one or two edges, which mean there isn't a choice in how to proceed from this node. For common road networds, a large majority of the nodes are of this type, and they don't affect routing, but they take a lot of extra time for the routing algorithm to traverse. So, for a large network you more or less have to use compaction to achieve speed. The original, uncompacted nodes are then only used for display.

Having said that, it appears you have found a bug in the compaction algorithm, since it shouldn't affect routing results, only performance, if you turn it off or on. I can for example imagine that there can be an issue if two nodes are collapsed into one.

Unfortunately, it's been a bit long since I worked on this code and I don't really have the time to dig into it at the moment, any help appreciated!

This is really helpful to know - I've forked this rep (partly to make it more es6 like, and partly to add a lot of comments so I can understand what it's doing).

I can tell you that trying to test with a square... is a really bad idea, as everything just compacts to nothing. I couldn't figure out what/why the compact graph function was behaving as it was, but it makes a lot more sense now :)

[perliedman]

Hi again, I have added a test case for a similar problem (that was indeed fixed by #70). I'm going to close this now, feel free to open a new issue if this is still a problem.

@IPWright83 just a heads up that version 2.0.0 is ES6/ESM based now, as well as using TypeScript, if it's any help. At least it helped me understand my old code :)

[IPWright83]

Nice @perliedman!

I left the company where I needed to use it, but was quite a nice library to use! I seem to recall I added a lot of comments to try and understand the code later