Compacted graph contains no forks (topology has no intersections)

[Omnyyah]

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

[perliedman]

Hi!

I common problem is that even though lines in the network cross, they do not share a common vertex (at least one of the coordinates in each line are the same or very close to each other). So, even though the lines cross, geojson-path-finder will not consider it an intersection unless both lines have a vertex at the crossing.

Might that explain the problem you're seeing?

[Omnyyah]

oh, ok in the network.json, are we only going to draw a polygon (collection of Linestring) around the area that we want to find the shortest path in? is it correct? how can we draw the GeoJSON correctly (I used geojson.io)? and if the area is small will it calculate the shortest path?

Thank you!

[perliedman]

The network should only contain LineString features, and those line strings are the paths used to find the shortest path - so normally those line strings would represent roads you want to route along.

Where two paths meet (a fork or crossing), the line strings have to have a coordinate in common, otherwise the router will have no way to know that it can take another path.

You can certainly draw the network in geojson.io or any other tool that outputs GeoJSON, but for most cases I would assume the network comes from some other source, for example OpenStreetMap or some proprietary source.

[Omnyyah]

Thank you for your response, but unfortunately, it didn't work with me, I think because the area I'm working on is small and it maybe recognizes all points as one point!

[perliedman]

Migth be, but in that case you have a very small area. For this case, you can use the precision option to manually set the tolerance that will snap coordinates together; it defaults to 1e-5.

If possible, you could show the network you're using and it might be easier to tell what the problem is.

[Omnyyah]

I changed it but the same problem, no intersections,,

this is my code :

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

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

var start = {
    "type": "Feature",
    "properties": {},
    "geometry": {
      "type": "Point",
      "coordinates": [24.467735, 39.609475 ]
    }
}
var finish = {
    "type": "Feature",
    "properties": {},
    "geometry": {
      "type": "Point",
      "coordinates": [24.468815, 39.608772]
    }
}

var path = pathFinder.findPath(start,finish );

  console.log(path);

and here is network.json

{"type":"FeatureCollection","features":[{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.60794448852539,24.470998163518342],[39.60790157318115,24.470724741090123],[39.60789084434509,24.470392727343242],[39.60788011550903,24.47009000816385],[39.607858657836914,24.469757992743045],[39.60789084434509,24.469474802427534],[39.607858657836914,24.46910372449819],[39.607869386672974,24.468879124167533],[39.607847929000854,24.468586166612376],[39.607847929000854,24.46832250422992],[39.607826471328735,24.467970953527793],[39.607847929000854,24.467629167181894],[39.607837200164795,24.467258083813036],[39.607837200164795,24.46699441864953],[39.60779428482056,24.466642864239347],[39.60774064064026,24.466320605167788],[39.60775136947631,24.4660471725815],[39.60801959037781,24.4660471725815],[39.60801959037781,24.466291308847655],[39.608051776885986,24.46663309882505],[39.608051776885986,24.467111603234795],[39.608094692230225,24.467541279114425],[39.608116149902344,24.4680197800729],[39.608116149902344,24.46838109591819],[39.608116149902344,24.46883029795567],[39.60813760757446,24.46953339357955],[39.60813760757446,24.470060712720752],[39.60808396339416,24.470558734326133],[39.60813760757446,24.471007928594076],[39.60794448852539,24.470998163518342]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.60819125175476,24.47097863336458],[39.60794448852539,24.47102745874328]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.60819125175476,24.47097863336458],[39.60849165916443,24.470998163518342],[39.60845947265625,24.470754036378686],[39.60845947265625,24.470402492465933],[39.60845947265625,24.470168129312075],[39.60842728614807,24.46990447024251],[39.60843801498413,24.469591984704312],[39.60845947265625,24.469162315822896],[39.60848093032837,24.4686838192065],[39.60845947265625,24.46839086119691],[39.60845947265625,24.468136963703895],[39.60851311683655,24.467697524525292],[39.60844874382019,24.467375268152928],[39.60843801498413,24.46705301095581],[39.60843801498413,24.466789345362876],[39.60844874382019,24.466457321238266],[39.60839509963989,24.466183888948866],[39.60837364196777,24.466076468958434],[39.60798740386963,24.4660471725815]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.60849165916443,24.47097863336458],[39.6086847782135,24.470988398441843],[39.608867168426514,24.470988398441843],[39.608834981918335,24.470754036378686],[39.60872769355774,24.470441552949158],[39.60869550704956,24.470060712720752],[39.60867404937744,24.469806818595135],[39.60869550704956,24.469504098006936],[39.60871696472168,24.469191611475033],[39.60871696472168,24.468791236972564],[39.6086847782135,24.46838109591819],[39.6086847782135,24.4681955554785],[39.60869550704956,24.46791236164868],[39.6086847782135,24.46772682051826],[39.60870623588562,24.46755104445828],[39.60873842239379,24.467219022342164],[39.60872769355774,24.466984653262497],[39.60873842239379,24.466740518340636],[39.60873842239379,24.46638896322157],[39.60873842239379,24.466232716186937],[39.60872769355774,24.466037407121007],[39.608330726623535,24.46611553078374]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.608867168426514,24.47097863336458],[39.609113931655884,24.470988398441843],[39.609103202819824,24.470832157114884],[39.609092473983765,24.470412257587874],[39.609092473983765,24.47004118242158],[39.60906028747558,24.469757992743045],[39.60907101631164,24.46941621124824],[39.60906028747558,24.46918184625841],[39.609049558639526,24.468898654646967],[39.60903882980347,24.46856663608447],[39.609049558639526,24.468273677802216],[39.609049558639526,24.467814708456213],[39.609049558639526,24.46750221773141],[39.609049558639526,24.467082307098703],[39.60902810096741,24.466789345362876],[39.60906028747558,24.46643779038014],[39.60907101631164,24.466203419846362],[39.60906028747558,24.466076468958434],[39.60870623588562,24.466076468958434]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.609049558639526,24.467844004421902],[39.6092426776886,24.467844004421902],[39.6092426776886,24.46750221773141],[39.6092426776886,24.467267849178864],[39.60926413536072,24.466896764745158],[39.6092963218689,24.466301074288452],[39.60928559303284,24.466027641659764],[39.609049558639526,24.466076468958434]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.60926413536072,24.46783423910077],[39.60945725440979,24.467814708456213],[39.60945725440979,24.467531513769806],[39.60946798324585,24.46728737990824],[39.60946798324585,24.467062776337524],[39.60946798324585,24.466789345362876],[39.60947871208191,24.466515913794456],[39.60952162742615,24.466262012520705],[39.60950016975403,24.466027641659764],[39.60921049118042,24.466027641659764]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.60943579673767,24.467795177808643],[39.6096932888031,24.467795177808643],[39.60970401763916,24.467560809801384],[39.60970401763916,24.467345972078185],[39.60970401763916,24.467140899364093],[39.60972547531127,24.466974887874713],[39.6097469329834,24.4667502837466],[39.60973620414734,24.466584271742224],[39.6097469329834,24.466359666917352],[39.609800577163696,24.466203419846362],[39.60976839065552,24.46606670350022],[39.60947871208191,24.466076468958434]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.60968255996704,24.46771705518803],[39.60997223854065,24.467707289857035],[39.60997223854065,24.46744362563417],[39.60998296737671,24.467297145271786],[39.61001515388489,24.46692606092443],[39.61002588272095,24.46672098752643],[39.61002588272095,24.466447555809577],[39.61005806922912,24.466193654397994],[39.61005806922912,24.466076468958434],[39.60972547531127,24.46610576532855]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.60998296737671,24.467697524525292],[39.610390663146966,24.46771705518803],[39.610358476638794,24.467404564220853],[39.610358476638794,24.4671994916022],[39.610358476638794,24.46701394942132],[39.610379934310906,24.4667502837466],[39.61036920547485,24.466496382945415],[39.610326290130615,24.466232716186937],[39.610315561294556,24.4660471725815],[39.61001515388489,24.466086234415897]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.610304832458496,24.467707289857035],[39.610583782196045,24.467668228525532],[39.610594511032104,24.467404564220853],[39.61062669754028,24.467121368611984],[39.61055159568786,24.466906530139],[39.610562324523926,24.466681925888942],[39.610562324523926,24.46639872865481],[39.610573053359985,24.466076468958434],[39.61027264595032,24.466076468958434]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.61063742637634,24.467297145271786],[39.61089491844177,24.46728737990824],[39.61089491844177,24.46701394942132],[39.61090564727783,24.46679911076505],[39.61091637611389,24.46655497548344],[39.61091637611389,24.46641825951899],[39.61092710494995,24.466242481632293],[39.61092710494995,24.466076468958434],[39.6105408668518,24.466086234415897]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.607912302017205,24.470754036378686],[39.60837364196777,24.470675915594025],[39.608588218688965,24.47066615049253],[39.608845710754395,24.47058802965333],[39.609103202819824,24.47058802965333]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.607912302017205,24.47054896921554],[39.60822343826294,24.47045131806807],[39.60864186286926,24.470402492465933],[39.608856439590454,24.470373197095554],[39.609092473983765,24.470402492465933]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.60789084434509,24.470295076074567],[39.60816979408264,24.470324371463114],[39.608352184295654,24.470285310943545],[39.6085774898529,24.47022672014144],[39.60888862609863,24.470187659591566],[39.609081745147705,24.4701583641712]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.607912302017205,24.469982591505868],[39.608105421066284,24.469972826350606],[39.60838437080383,24.46992400056289],[39.608620405197144,24.46989470508118],[39.609081745147705,24.469845879263172]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.60789084434509,24.469972826350606],[39.60789084434509,24.470011886967132]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.607869386672974,24.469797053426237],[39.60822343826294,24.469748227570353],[39.608405828475945,24.469709166872025],[39.608588218688965,24.469709166872025],[39.6087920665741,24.469699401695557],[39.609081745147705,24.469699401695557]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.607858657836914,24.469504098006936],[39.60819125175476,24.46953339357955],[39.60845947265625,24.469484567621432],[39.60867404937744,24.469474802427534],[39.60906028747558,24.469425976446683]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.60790157318115,24.469259967970164],[39.60822343826294,24.469259967970164],[39.60843801498413,24.469240437546773],[39.60873842239379,24.469211141905994],[39.609092473983765,24.46918184625841]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.607847929000854,24.469025602689495],[39.60824489593505,24.468996306998733],[39.60847020149231,24.468996306998733],[39.60873842239379,24.468986541766974],[39.60907101631164,24.46896701130115]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.60788011550903,24.46871311496997],[39.608234167099,24.468722880222952],[39.60845947265625,24.46870334971624],[39.6086847782135,24.46871311496997],[39.60896372795105,24.46871311496997],[39.609049558639526,24.46871311496997]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.607847929000854,24.468498279212913],[39.60819125175476,24.468459218126785],[39.60853457450867,24.468420157028543],[39.608910083770745,24.468400626474875],[39.60906028747558,24.468420157028543]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.607837200164795,24.468234616646406],[39.608105421066284,24.468234616646406],[39.60838437080383,24.468224851355576],[39.6086847782135,24.4681955554785],[39.609049558639526,24.4681662595946]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.607826471328735,24.468010014765394],[39.60822343826294,24.468000249457123],[39.60856676101684,24.4679904841481],[39.608845710754395,24.4679904841481],[39.60903882980347,24.467970953527793]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.607858657836914,24.46775611650439],[39.608362913131714,24.467707289857035],[39.608813524246216,24.4676877591928],[39.609135389328,24.467629167181894],[39.609403610229485,24.467599871166232],[39.60975766181946,24.467599871166232],[39.61001515388489,24.46755104445828],[39.61046576499939,24.46750221773141],[39.610594511032104,24.467511983078307]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.607847929000854,24.467541279114425],[39.60822343826294,24.467521748424424],[39.60853457450867,24.467472921686205],[39.608802795410156,24.467472921686205],[39.60922122001648,24.46744362563417],[39.60956454277038,24.46739479886565],[39.609854221343994,24.46739479886565],[39.6101438999176,24.46735573743719],[39.61048722267151,24.467306910634587],[39.61062669754028,24.46728737990824]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.607837200164795,24.46731667599661],[39.608234167099,24.46724831844646],[39.60850238800049,24.4671994916022],[39.608813524246216,24.467111603234795],[39.609328508377075,24.46713113398842],[39.60962891578674,24.467111603234795],[39.60991859436035,24.46707254171849],[39.61026191711426,24.46707254171849],[39.610583782196045,24.46705301095581],[39.610819816589355,24.467043245573315],[39.61091637611389,24.467043245573315]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.607858657836914,24.46705301095581],[39.60813760757446,24.46705301095581],[39.60851311683655,24.46699441864953],[39.608867168426514,24.466935826315993],[39.609307050704956,24.466955357096865],[39.60952162742615,24.466916295532087],[39.609886407852166,24.4668577031622],[39.61026191711426,24.466789345362876],[39.61051940917969,24.46677957995994],[39.61078763008118,24.46677957995994],[39.61091637611389,24.46679911076505]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.607826471328735,24.466877233955188],[39.60827708244324,24.46682840696703],[39.6085774898529,24.466789345362876],[39.608910083770745,24.46676981455625],[39.60922122001648,24.466730752933906],[39.60955381393432,24.466701456709206],[39.609843492507935,24.46665262965288],[39.61017608642578,24.466642864239347],[39.61046576499939,24.4666135679942],[39.61078763008118,24.466584271742224],[39.61092710494995,24.466594037160313]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.6077835559845,24.46665262965288],[39.60819125175476,24.46663309882505],[39.608556032180786,24.466594037160313],[39.608824253082275,24.466564740903795],[39.6092426776886,24.46655497548344],[39.6096932888031,24.466515913794456],[39.61012244224548,24.46647685209336],[39.61045503616333,24.46646708666619],[39.61091637611389,24.466457321238266]]}},{"type":"Feature","properties":{},"geometry":{"type":"LineString","coordinates":[[39.60774064064026,24.46636943235286],[39.608116149902344,24.466359666917352],[39.608556032180786,24.46636943235286],[39.608899354934685,24.46636943235286],[39.609339237213135,24.46638896322157],[39.6096396446228,24.466320605167788],[39.60998296737671,24.466291308847655],[39.61044430732727,24.466291308847655],[39.610798358917236,24.466301074288452],[39.61091637611389,24.466301074288452]]}}]}

[perliedman]

Hi again, a couple of things to note: you have swapped latitude and longitude in the coordinates for start and finish - they need to use longitude first, as in all GeoJSON.

Also, the start and finish coordinates need to exactly match coordinates actually in the network (for real world usage, find the network coordinate closest to the user's coordinates).

Finally, the network you supplied seems to not have coordinates that match up at each fork: for every place where the route can make a turn, you need to have two coordinates, one for each segment, that are really close to each other (where "close" is defined by the network's precision option).

As a test, I created a somewhat simpler example of your network to show what I mean. You can have a look at it here: https://gist.github.com/perliedman/f1357157096748d289d9d93c2fa66792

I run it with this slightly modified version of your code:

var pathFinder = new PathFinder(geojson);

var start = {
    "type": "Feature",
    "properties": {},
    "geometry": {
      "type": "Point",
      "coordinates": [39.607925713062286,24.47097863336458]
    }
}
var finish = {
    "type": "Feature",
    "properties": {},
    "geometry": {
      "type": "Point",
      "coordinates": [39.60842192173004,24.46606670350022]
    }
}

var path = pathFinder.findPath(start,finish);
console.log(path);

And it outputs:

{ path: 
   [ [ 39.607925713062286, 24.47097863336458 ],
     [ 39.60849165916443, 24.47098351590331 ],
     [ 39.608494341373444, 24.470785772933606 ],
     [ 39.60849165916443, 24.47078333166044 ],
     [ 39.60848093032837, 24.4702145137209 ],
     [ 39.60848093032837, 24.469269733180717 ],
     [ 39.608462154865265, 24.4685764013488 ],
     [ 39.608451426029205, 24.46781959111763 ],
     [ 39.6084326505661, 24.46720925697256 ],
     [ 39.608424603939056, 24.46649150023269 ],
     [ 39.60842192173004, 24.46606670350022 ] ],
  weight: 0.6041907698481844,
  edgeDatas: undefined }

Hope this helps!

Just out of curiosity, given the location of your example data, what are you planning on using this for?

[Omnyyah]

ohhh, so it's my fault :( Thank you so much for your time, effort and help!

Just out of curiosity, given the location of your example data, what are you planning on using this for?

Actually I want to use it in one of school projects, I want to take user location along with any point he select on the map in my android application and then send these 2 locations to html file to calculate the shortest path using your AMAZING library, after getting the shortest path I want to draw it on a map, and display the path to the user to guide him :) (long story :) )

anyway, thank you very much.

[cigone-openindoor]

What about a circular LineString ?

I get also "topology has no intersections".