perliedman / geojson-path-finder Goto Github PK

Hello, let me start of by applauding this lovely package. I'm a noob when it comes to npm and node.js. What I am trying to achieve is to use your package in bootleaf (http://bmcbride.github.io/bootleaf/) or more precisely - https://github.com/bmcbride/bootleaf. : The folder structure is:

Project1
----Data (has my geojson files)
----Assetts
-----js (where my app.js resides)
* all other folders as can be seen in Brian's repository

I have done the following:

1. Correctly installed both Node and npm.
2. Ran the installation line of code provided in the Readme file; it creates a directory in the folder (node-modules) in my js folder.

npm install --save geojson-path-finder

1. Added the 'require' lines and picked two default co-ordinates

var PathFinder = require('geojson-path-finder'),
geojson = require('./network.json');
var pathFinder = new PathFinder(geojson);

var path = pathfinder.findPath(c1, c2);

alert(path);

1. attempted to bundle the script with browserify.....although I do not know whether this is what I should do; it raised an error on the ./network.json' part..
   :) first time i'm using node or npm or browserify.

I'm trying to do this for a school project, please guide me on the steps I should take.

Thanks in advance.

Version 1.2.0 of tinyqueue just got published.

This version is covered by your current version range and after updating it in your project the build failed.

As tinyqueue is a direct dependency of this project this is very likely breaking your project right now. If other packages depend on you it’s very likely also breaking them.
I recommend you give this issue a very high priority. I’m sure you can resolve this 💪

Your Greenkeeper Bot 🌴

Hi !

I've a strange issue, and I need to shortcut the compactor to resolve it.

this is my network, and displayed points are nodes who are removed by compactor: (here)

this is my expected path result:

this is what I get:

I've checked some relations :

Do you think it's an issue ? or it is simply impossible to access these compacted/removed nodes ?

EDIT : access to compacted/removed node seems to be purpose of _createPhantom() method, so we have an issue

thanks for your support and your library !

Bertrand

Have you thought about supporting topojson? It would mean using pre-specified topology from topojson. I use topojson a lot, and I'd prefer to calculate the shortest paths based on the topology building algo there.

Nevermind... was using the wrong geojson file!

Hi, I've found your package and it's really awesome! But, is possible to apply pathFinder function on featureCollection of miltiplne lineStrings ? Because it seems that's not working. I'm working on Indoor Navigation based on QRcodes and I want to create big graph, where can I search shortest way.

First off, I really like this library, it works well and fast. Thanks for maintaining.

I am using it to calculate paths in a self-recorded network. After some adjustments to the network, it does what we need.

However, when I add one-way features, I cannot get a path if the destination is on that one-way feature. The start can be placed on it and it works. Also, the one-way feature is included for "through" paths that have a working destination.

I am using this weightFunction:

weightFunction = (a, b, props) => {
    const distance = turf.distance(turf.point(a), turf.point(b)) * 1000;
    let forward = distance;
    let backward = distance;
    if (props.oneway && props.oneway === true) {
      backward = 0;
    } else if (props.oneway && props.oneway === 'backward') {
      forward = 0;
    }
    return {
      forward: forward,
      backward: backward,
    };
  };

My features can have a "oneway" property that is set to true if the feature should be one-way. I do not use the "backward" value at the moment. If I remove the "oneway" property, I can place the destination on the feature with no issue.

Any guidance would be dearly appreciated.

hello,i create a geojson map file,and i want get the a->b shortest path,

but i always get the result like this.

my test code:

var PathFinder = require('../'),
    //geojson = require('./network.json'),
    geojson = require('./shenyang1.json'),
    test = require('tap').test,
    point = require('turf-point');
    //distance = require('@turf/distance').default;

let fs = require('fs');
let options = { 
    flags: 'a',     // append模式
    encoding: 'utf8',  // utf8编码
};
let stdout = fs.createWriteStream('./stdout.log', options);
let stderr = fs.createWriteStream('./stderr.log', options);
let logger = new console.Console(stdout, stderr);

test('can find path (complex)', function(t) {
    var pathfinder = new PathFinder(geojson, 
        //path = pathfinder.findPath(point([8.44460166, 59.48947469]), point([8.44651, 59.513920000000006]));
        //path = pathfinder.findPath(point([8.45163096, 59.49259688]), point([8.47169688, 59.50405761]));
        //path = pathfinder.findPath(point([8.45163096, 59.49259688]), point([8.46983216, 59.49492301]));
        //path = pathfinder.findPath(point([123.42682600021364, 41.79379242995082]), point([123.43067765235901, 41.790744790121266]));
        {   
            weightFn: function(a, b) {
                var dx = a[0] - b[0];
                var dy = a[1] - b[1];
                return Math.sqrt(dx * dx + dy * dy);
            },  
            precision:1
        }), 
        //path = pathfinder.findPath(point([11, 13]), point([0, 0]));
        path = pathfinder.findPath(point([0, 0]), point([15, 12]));

        /*  
    var arr = new Array();
    for (var i = 0; i < path.path.length; i++)
        arr.push(path.path[i]);
    console.log(arr.join('], ['));
    */
    console.log(path.path)
    logger.log(path.path);
    console.log(path.weight)
    t.ok(path, 'has path');
    t.ok(path.path, 'path has vertices');
    t.ok(path.weight, 'path has a weight');
    //t.equal(path.path.length, 220, 'path has expected length');
    //t.ok(Math.abs(path.weight - 6.3751) < 5e-5, 'path has expected weight');
    t.end();
});

my geojson file :

{
  "type": "FeatureCollection",
  "features": [
    {
      "type": "Feature",
      "id": 1,
      "properties": {},
      "geometry": {
        "type": "LineString",
        "coordinates": [
          [0, 0], [12, 0]
        ]
      }
    },
    {
      "type": "Feature",
      "id": 2,
      "properties": {},
      "geometry": {
        "type": "LineString",
        "coordinates": [
          [12, 0], [12, 3]
        ]
      }
    },
    {
      "type": "Feature",
      "id": 3,
      "properties": {},
      "geometry": {
        "type": "LineString",
        "coordinates": [
          [12, 3], [3, 3]
        ]
      }
    },
        {
      "type": "Feature",
          "id": 4,
      "properties": {},
      "geometry": {
        "type": "LineString",
        "coordinates": [
          [3, 3], [3, 6]
        ]
      }
    },
        {
      "type": "Feature",
          "id": 5,
      "properties": {},
      "geometry": {
        "type": "LineString",
        "coordinates": [
          [3, 6], [7, 6]
        ]
      }
    },
        {
      "type": "Feature",
          "id": 6,
      "properties": {},
      "geometry": {
        "type": "LineString",
        "coordinates": [
          [7, 6], [7, 12]
        ]
      }
    },
    {
      "type": "Feature",
      "id": 7,
      "properties": {},
      "geometry": {
        "type": "LineString",
        "coordinates": [
          [7, 12], [3, 14]
        ]
      }
    },
        {
      "type": "Feature",
"id": 8,
      "properties": {},
      "geometry": {
        "type": "LineString",
        "coordinates": [
          [0, 0], [1, 2]
        ]
      }
    },
        {
      "type": "Feature",
          "id": 9,
      "properties": {},
      "geometry": {
        "type": "LineString",
        "coordinates": [
          [1, 2], [3, 3]
        ]
      }
    },
        {
      "type": "Feature",
          "id": 10,
      "properties": {},
      "geometry": {
        "type": "LineString",
        "coordinates": [
          [9, 6], [12, 3]
        ]
      }
    },
    {
      "type": "Feature",
      "id": 13,
      "properties": {},
      "geometry": {
        "type": "LineString",
        "coordinates": [
          [7, 12], [15, 12]
        ]
      }
    },
        {
      "type": "Feature",
          "id": 11,
      "properties": {},
      "geometry": {
        "type": "LineString",
        "coordinates": [
           [7, 6], [9, 6]
        ]

      }
    },
        {
      "type": "Feature",
          "id": 12,
      "properties": {},
      "geometry": {
        "type": "LineString",
        "coordinates": [
          [9, 6], [15, 12]
        ]
      }
    }
  ]
}

i want to know where i am wrong.
thank you.

Can I using your lib with openlayers and my geojson data

Hello,

Thank you for building this library, I'm trying to find the shortest path between 2 points, but I'm facing this error
throw new Error('Compacted graph contains no forks (topology has no intersections).');

although my network.json segments are closed and I have points everywhere, so I don't why it cant finds intersection!

Thank you

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.

I had a linestring layer and a point layer on the same map area. I replace my linestring to your demo, it work with any position of marker. Then I build node js server. I find path between two points in my point layer. Its not working at all
Simply: my points 111.01234567891011, 11.01234567891011 - 222.01234567891011, 22.01234567891011
if change any number after 5 or 6 it work, before not.
I try change _precision e-5 to e-2. it work but points of path result aren't serial

Does the API support intermediate waypoints as shown in the demo ?. How to achieve ?. Imported the (leaflet-headless) and (leaflet-routing-machine) modules , done something but in vain.
Any help is appreciated. Thanks in advance :)

Hi,
very impressive by your work !

I'm working on it, and I don't understand how use 'phantom' ?

In my mind this represent a new point in the network to add in graph. But it doesnt work. (maybe you change anything in the code ?)

thks for the reply

Hello,

I just wanted to know if this library works with MultiLineString features ? It should be the same as LineString but with extra brackets like so:

MultiLineString
[ [ [5.783246085057053,43.12920992982103],[5.78323152868196,43.129224336755215] ] ]

LineString
[ [5.783246085057053,43.12920992982103],[5.78323152868196,43.129224336755215] ]

If not maybe there is a way to alter the code and make it compatible ?

Thank you in advance :)
Lessad

Edit: Corrected "MultipleLineString" to "MultiLineString"

Im a bit new to node, and it took me while to work out with your library that though not stated i (think) i had to use browserify to 'compile' the basics of your library to get it to work in the browser ?

Is there any way to use the library without this, eg just <script> tags includes ?

Hi. Would it be okay to integrate ES6 standards for client-side-server browsers that can't recognize the require() function? Also, I can't seem to fix the issue 'Could not find declaration file for module geojson-path-finder'. I'm a beginner at javascript language, I tried to look for solutions but I can't make it work. Hope you can help me on this one. Godspeed!

I am new to javascript
First I was getting this error
Uncaught reference error: require is not defined
After downloading https://requirejs.org/docs/download.html file from this website
I got following error
Uncaught Error: Module name "geojson-path-finder" has not been loaded yet for context: _. Use require([])

please help

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

Hi @perliedman
I copied a part of your network.json file for my geoJson object and my points in this file.
Here is the code

var geojson = require('./network.json');
var PathFinder = require('geojson-path-finder');
var start = {
    "type": "Feature",
    "properties": {},
    "geometry": {
      "type": "Point",
      "coordinates": [
            8.44846912,
            59.49097094
        ]
    }
}
var finish = {
    "type": "Feature",
    "properties": {},
    "geometry": {
      "type": "Point",
      "coordinates": [
            8.43052838,
            59.48310541
        ]
    }
}
var pathFinder = new PathFinder(geojson);
var path = pathFinder.findPath(start, finish)

But findPath method returning null. What am i doing wrong, can you help me ?

In a closer reading of the API it looks like barriers/ impediments haven't been included here . As, i want the shortest route to be calculated by excluding paths which have barriers .

Any help is appreciated. Thankx for advance :)

Currently, the route network is stored with all coordinates snapped to the current precision. This works bad for presentation, and if possible the original coordinates should be returned in response to routing requests.

I'm working on a project where I'm creating routes based on the city's geoJSON bike lane data. So far it works pretty well, except sometimes small loops are created. I'd assumed this was because of the distance between each of the points in the data set. I've been experimenting with ways that I can improve results by modifying the data set, but have begun to question my understanding of the pathfinding algorithm because that has produced even stranger results.

I'm working on the assumption that the denser the coordinates the better. Is this a misconception? I iterated through my dataset and added a midpoint between each coordinate using the Turf midpoint helper function, but the results actually seem worse. I also seem to get a different path each time for the same destination. I think the primary issue is that the bike lane system is pretty sparse, so I'm trying to strategize ways to modify the dataset to optimize results.
Thanks!

Could you share an example on how to use edgeDataReduceFn. I have street names and other properties on my geojson but I cannot seem to get the edgeDataReduceFn function to work properly. I would appreciate any working example. Thanks!

How can i calculate real distance from weight ?

Version 10 of Node.js (code name Dubnium) has been released! 🎊

To see what happens to your code in Node.js 10, Greenkeeper has created a branch with the following changes:

• Added the new Node.js version to your .travis.yml

If you’re interested in upgrading this repo to Node.js 10, you can open a PR with these changes. Please note that this issue is just intended as a friendly reminder and the PR as a possible starting point for getting your code running on Node.js 10.

Your Greenkeeper Bot 🌴

ty for creating pathFinder!

Version: 1.5.3
Demo: https://jsfiddle.net/6qugy0rm/

I made a simple GeoJSON and i tried to apply the pathFinder but i never get a path :s

(a red path would be painted between those markers if pathFinder had any result)

What i'm missing out?

for instance I would have

• ground level:0
• bridge:1
• Underground:-1

At this stage I got small issues with some path going from under the bridge straight to the bridge, as lines are crossing...

I am trying to eliminate common/near vertexes on these locations as a way to solve it, however was wondering if it would be possible another way.

Thanks

Hello, I learned to use Node.js and npm efficiently now. I have the following comments and observations about your repository:

1. I noticed that this link does NOT use geojson-path-finder library, it uses leaflet-routing-machine. Why did you use it as an example?
2. I cannot find any geojson-path-finder example anywhere online. Can you zip up one simple example for me - like the example you provide
3. path = pathFinder.findPath(start, finish); //this was the most confusing section. please give a sample geojson line for start and finish.
   I tried a couple of geojson point scripts e.g.

var finish = { "type": "Point",
                     "crs": { "type": "name", "properties": { "name": "urn:ogc:def:crs:OGC:1.3:CRS84" } },      "features": [ "geometry":{ "type": "Point", "coordinates": [36.97194311, -1.455614833] } ] }; 

var start = { "type": "Point", 
                    "crs": { "type": "name", "properties": { "name": "urn:ogc:def:crs:OGC:1.3:CRS84" } }, "features": [ "geometry":{ "type": "Point", "coordinates": [36.9775,-1.4508] }] }; 

but these did not work. Please try the solution first

Regards,

Steve

Really a cool stuff. Wanna implement the same thing for an ios Device. Can this be migrated to Objective - C or Swift language ?. The reason behind is to create a native app. If not , is there any alternative as myself a newbie .

If I bundle using Webpack and I import this library, when I call findPath on an instance of PathFinder I get the following error:

Queue is not a constructor

in the dijkstra.js file

Can you help with resolving this? Not sure what the issue is.

TypeError: distance is not a function9 | module.exports = function preprocess(graph, options) { 10 | options = options || {}; 11 | var weightFn = options.weightFn || function defaultWeightFn(a, b) { 12 | return distance(point(a), point(b)); 13 | }, 14 | topo; 15 |

The dependency tap was updated from 12.4.1 to 12.5.0.

🚨 View failing branch.

This version is covered by your current version range and after updating it in your project the build failed.

tap is a direct dependency of this project, and it is very likely causing it to break. If other packages depend on yours, this update is probably also breaking those in turn.

Your Greenkeeper Bot 🌴

Hi @perliedman!

I've been using your library for one-level pathfinding but would like to add a third dimension. Generally GeoJSON supports values of x,y,z and your Pathfinder is taking a FeatureCollection of lineStrings with xyz-coordinates just fine. The resulting path consists of one point only, although I gave a featureCollection of connected lineStrings. Same issue whatever path I want to take or whatever weight I manually assign. It seems like the Pathfinder cannot handle 3 dimensions.

Or maybe I am doing something wrong? Or is it possible to easily extend your Pathfinder for 3 dimensions?

Thank you for your help!

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?

Hi,

We have implemented your API and all is working well so thank you! We have a question. We are showing a closed road network we mapped with real time GPS coordinates and are unclear on how to designate a certain path as a one way road so that in the calculation it does not pick this road if coming from the other direction? Is there a specific feature ID we need to add to the geojson to enable this?

Also we are trying to find the proper way to have the API disregard paths that require the moving object to turn around on the one way road they are on? We have read your weighted value explanation on the readme and tried to implement but I assume we are missing something in the geojson that causes this calculation to not work.

Any help would be appreciated!

Hi,
i found your great tool to create a Router on existing geoJSON-Paths.
It worked most of the time, but sometimes I get the Error "Cant't find route". I checked the lines for spaces and other errors but i can't find any. Are there any size limits for processing?

I have uploaded my file for testing,:
test.zip

Version 5.0.4 of @turf/distance was just published.

This version is covered by your current version range and after updating it in your project the build failed.

@turf/distance is a direct dependency of this project, and it is very likely causing it to break. If other packages depend on yours, this update is probably also breaking those in turn.

Your Greenkeeper Bot 🌴

There seems to be an issue with the npm package, basically the require of tinyqueue in dijkstra.js isn't working properly for me. When running the code I get the following error:

dijkstra.js:8 Uncaught TypeError: Queue is not a constructor
at module.exports (dijkstra.js:8)
at PathFinder.findPath (index.js:43)
at route (index.js:76)
at eval (index.js:107)

If input GeoJSON is a closed loop, I get the following error on initialization:

const pathFinder = new PathFinder(geojson);

Uncaught Error: Compacted graph contains no forks (topology has no intersections).
    at new PathFinder (index.js:formatted:1)
    at calculate (RoutingPage.js:375)
    at HTMLUnknownElement.callCallback (react-dom.development.js:3945)
    at Object.invokeGuardedCallbackDev (react-dom.development.js:3994)
    at invokeGuardedCallback (react-dom.development.js:4056)
    at invokeGuardedCallbackAndCatchFirstError (react-dom.development.js:4070)
    at executeDispatch (react-dom.development.js:8243)
    at processDispatchQueueItemsInOrder (react-dom.development.js:8275)
    at processDispatchQueue (react-dom.development.js:8288)
    at dispatchEventsForPlugins (react-dom.development.js:8299)
    at react-dom.development.js:8508
    at batchedEventUpdates$1 (react-dom.development.js:22396)
    at batchedEventUpdates (react-dom.development.js:3745)
    at dispatchEventForPluginEventSystem (react-dom.development.js:8507)
    at attemptToDispatchEvent (react-dom.development.js:6005)
    at dispatchEvent (react-dom.development.js:5924)
    at unstable_runWithPriority (scheduler.development.js:468)
    at runWithPriority$1 (react-dom.development.js:11276)
    at discreteUpdates$1 (react-dom.development.js:22413)
    at discreteUpdates (react-dom.development.js:3756)
    at dispatchDiscreteEvent (react-dom.development.js:5889)

Removing a single LinePath from GeoJSON makes the error go away.

GeoJSON used:
https://pastebin.com/2mfrUxYU

Hi,

when trying to use your geojson-path-finder Lib in Typescript / Vue application I get following error.
It seems like the turf/explode Lib exports it's function in another way than expected.

My code:
var PathFinder = require("geojson-path-finder");
const network = { /** GeoJSON data **/};
const pathfinder = new PathFinder(network);

and this error is thrown:

Uncaught TypeError: explode is not a function at topology (topology.js?2816:42) at preprocess (preprocessor.js?48bf:18) at new PathFinder (index.js?0ea7:14) at eval (network.ts?7260:1) at Module../src/network.ts (app.js:1815) at __webpack_require__ (app.js:791) at fn (app.js:151) at eval (cjs.js?!./node_modules/babel-loader/lib/index.js!./node_modules/ts-loader/index.js?!./node_modules/cache-loader/dist/cjs.js?!./node_modules/vue-loader/lib/index.js?!./src/views/Map.vue?vue&type=script&lang=ts&:6) at Module../node_modules/cache-loader/dist/cjs.js?!./node_modules/babel-loader/lib/index.js!./node_modules/ts-loader/index.js?!./node_modules/cache-loader/dist/cjs.js?!./node_modules/vue-loader/lib/index.js?!./src/views/Map.vue?vue&type=script&lang=ts& (app.js:1064) at __webpack_require__ (app.js:791)

how exactly the geojson is required for this to work. it wasnt explained in the readme section. i am Getting error saying Queue is not constructor.from dijkstra.js file. if you can help me with this, how exactly i have to proceed with the paathfinder.

Hi,
I've been trying to extract usable GeoJSON from OSM extracts for road path finding but I'm having a hell of a time getting a usable file, it's either got disconnected linestrings or is way to big to load.

similar to #33,
Im having problem with using multiple Linetring, If i use just one line string in my feature collection, it will show me the path, but if i have more than one, it will show me nothing, with no error.

As mentioned by @s9eenk in #16, it would be a nice addition to find at least one alternative route, when possible.

Hi @perliedman !
Do you have any idea if it's possible to create/extract navigation data from a geojson ?
It could be amazing to add this to geojson-path-finder response !
thanks for your work!!

Hi, got your library working but im using leaflet in simple crs mode with the coords just being the pixels of my map (no projection, just hanging in space) (its for a game)

The weight/distance returned seems to be hard coded for spherical ?

How would i go about getting a usable value ?

for example my image / crs is 1024 wide and 888 high, if i path a line from top to bottom, the weight is 18680.77347923352 if i do a path from left to right , the weight is 3906.0551639612486

First of all, thanks for this wonderful library!

I was thinking if it was possible to give instructions like walk for 10 metres, turn right, etc. along with the route in the response. If not, is there any other library which gives instructions for a given route?

Maybe this is first pathfinder for vector data by javascript in github

Hi again @perliedman ! Your algorithm working well but i have a problem. when i try to create a small section (max 8-9 segments) , the result returning missing start point.
Marker on the left is start point.

Here is the result

But this problem did not occur in larger sections. Can you help me ?