1

i want to apply Dijkstra's algorithm on list of features provided with geoJson file i have up to 100 features look at example . leaflet Dijkstra's algorithm what i have done so far :

  1. extracted all points from features (variable called points)

2. i have built a adjacency list like this using index's from points so 0-1-10 ,will be point of index 0 at points and the same for 1 and the third is the distance from each other. 3. i have built adjacency array but i don't see any use of it the example shown in the image is not the full features i am seeking only the starting point then i can working on the rest of the map.

  1. all black points are (lat , lang)

how can i make edge system so that i can implement Dijkstra's or A* Algorithm

my question is how can i continue to go from A to B ? any suggestions are welcome.

edit 1 : added code

edit 2 : updated question 

 var start = [34.000750, 71.485753];
            var end = [34.000937, 71.485180];
           
            var points=[];
            var nodes=[];
            var features=[];
            var adjacent=[];

            var map = L.map('map').setView(start, 17);;

        map.attributionControl.addAttribution('<a href="https://github.com/tomchadwin/qgis2web" target="_blank">qgis2web</a>');
        var bounds_group = new L.featureGroup([]);
        var basemap0 = L.tileLayer('http://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png', {
            attribution: '&copy; <a href="http://openstreetmap.org">OpenStreetMap</a> contributors,<a href="http://creativecommons.org/licenses/by-sa/2.0/">CC-BY-SA</a>',
            maxZoom: 22
        });
        basemap0.addTo(map);
        L.geoJSON(data).addTo(map);
        //OpenStreetMap_BlackAndWhite.addTo(map)
          //basemap0.addTo(map);
            function getid(){
             var possible = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
             var d = possible.charAt(Math.floor(Math.random() * possible.length));
             while(nodes.indexOf(d) >-1){
               d = possible.charAt(Math.floor(Math.random() * possible.length));
             }
          return d;
            }
            L.geoJSON(data, {
                onEachFeature: function(feature, layer) {
                    //console.log(feature);
                    points.push.apply(points,feature.geometry.coordinates);
                    features.push(feature.geometry.coordinates);
                   // return L.Polyline(layer, geojsonMarkerOptions);
                }
            });

            function init(){
             var marks= [];
             for (var i = 0; i < features.length; i++) {
                 var s = features[i];

                 //var m = L.marker([s[1],s[0]]);
                 //marks.push(m);
                 for (var j = 0; j < s.length; j++) {
                     var k = s[j];

                     var m = L.marker([k[1],k[0]]);
                     m.on('click',function(e){
                         console.log(this.getLatLng());
                     })
                     marks.push(m);
                 }
                
             }
             var heuristik
             for (var i = 0; i < marks.length-1; i++) {
                 var lt = marks[i].getLatLng().distanceTo(marks[i+1].getLatLng());
                 var a =i;
                 var b =i+1;
                 if(lt != 0 ){
                 console.log(a,b,lt,);

                 adjacent.push([a,b,lt]);
                 }
                 //Array.prototype.push.apply(adjacent,{a,b,lt});
      
             }
             //console.log(adjacent)
            }
html,body {
  width: 100%;
  height: 100%;
  overflow: hidden;
 }
 #map{
  width: 100%;
  height: 100%;
 } 
<link rel="stylesheet" href="https://unpkg.com/leaflet@1.0.3/dist/leaflet.css" />
<script src="https://unpkg.com/leaflet@1.0.3/dist/leaflet.js"></script>
 <script src="https://raw.githubusercontent.com/andrewhayward/dijkstra/master/graph.js"></script>
 
   <script></script>
  <script>
    var data = {
"type": "FeatureCollection",
"crs": { "type": "name", "properties": { "name": "urn:ogc:def:crs:OGC:1.3:CRS84" } },
"features": [
{ "type": "Feature", "properties": { "Place": "Kmc Road" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484445376090477, 34.000556224204104 ], [ 71.484619381903997, 34.00055622349123 ], [ 71.485795423886529, 34.000556218673154 ], [ 71.486389444907786, 34.000556088482497 ] ] } },
{ "type": "Feature", "properties": { "Place": "UET Main Road" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486384748456004, 34.002041741407623 ], [ 71.485121131034504, 34.002036564553677 ], [ 71.484897906943033, 34.002035650037541 ], [ 71.484080666224514, 34.002032301923023 ] ] } },
{ "type": "Feature", "properties": { "Place": "Road 2" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486389444907786, 34.000556088482497 ], [ 71.486384748456004, 34.002041741407623 ], [ 71.48638137935751, 34.003043552173651 ], [ 71.486380078137188, 34.003430473641167 ], [ 71.486380045906941, 34.003440057392226 ] ] } },
{ "type": "Feature", "properties": { "Place": "Hostel Road" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486380078137188, 34.003430473641167 ], [ 71.484890807505366, 34.00343866205165 ], [ 71.483730352446614, 34.003445042545671 ] ] } },
{ "type": "Feature", "properties": { "Place": "Commerce College Road" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.483730352446614, 34.003445042545671 ], [ 71.483792886191907, 34.003192857311085 ], [ 71.484080666224514, 34.002032301923023 ], [ 71.484445376090477, 34.000556224204104 ] ] } },
{ "type": "Feature", "properties": { "Place": "Civil Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485795429415916, 34.000635421476822 ], [ 71.485793037373725, 34.000750625722446 ], [ 71.485761836269248, 34.000750627900693 ] ] } },
{ "type": "Feature", "properties": { "Place": "Structure Labs & Library" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485793037373725, 34.000750625722446 ], [ 71.485824238478202, 34.000750623544199 ] ] } },
{ "type": "Feature", "properties": { "Place": "Concrete Testing Lab" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485793037373725, 34.000750625722446 ], [ 71.485797844581057, 34.000851428955635 ], [ 71.485838646025371, 34.000851426107154 ], [ 71.485841053985538, 34.000964229932706 ] ] } },
{ "type": "Feature", "properties": { "Place": "Hydraulic Lab" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485797844581057, 34.000851428955635 ], [ 71.485800253043891, 34.000971433036057 ], [ 71.485783452449184, 34.000971434208964 ], [ 71.485785871468138, 34.001242643641845 ], [ 71.485809872317731, 34.001242641966272 ] ] } },
{ "type": "Feature", "properties": { "Place": "Civil Parking" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485795429415916, 34.000635421476822 ], [ 71.485529019817847, 34.000633039990753 ] ] } },
{ "type": "Feature", "properties": { "Place": "CS & IT" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485797844581057, 34.000851428955635 ], [ 71.485181022746431, 34.000851472017921 ], [ 71.485181028778499, 34.000937875076467 ] ] } },
{ "type": "Feature", "properties": { "Place": "Earthquake Center" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181022746431, 34.000851472017921 ], [ 71.485181021908645, 34.000839471593132 ], [ 71.485181018725044, 34.000793869978892 ], [ 71.485046613967313, 34.000793879362114 ] ] } },
{ "type": "Feature", "properties": { "Place": "New Earthquake Center" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181021908645, 34.000839471593132 ], [ 71.484837809926972, 34.000841895638814 ], [ 71.484837796857477, 34.000654689011959 ], [ 71.484837795852144, 34.000640288502204 ], [ 71.484621788205772, 34.000640303582379 ] ] } },
{ "type": "Feature", "properties": { "Place": "Girls Common Room" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181028778499, 34.000937875076467 ], [ 71.485181035313246, 34.001031478389898 ], [ 71.485181040507527, 34.001105881023648 ] ] } },
{ "type": "Feature", "properties": { "Place": "Mechanical Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181040507527, 34.001105881023648 ], [ 71.485181063088987, 34.001429336832032 ] ] } },
{ "type": "Feature", "properties": { "Place": "New Earthquake Gate" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484621788205772, 34.000640303582379 ], [ 71.484619381903997, 34.00055622349123 ] ] } },
{ "type": "Feature", "properties": { "Place": "Civil Main Gate" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485795429415916, 34.000635421476822 ], [ 71.485795423886529, 34.000556218673154 ] ] } },
{ "type": "Feature", "properties": { "Place": "New Academic Block" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181063088987, 34.001429336832032 ], [ 71.485125861392447, 34.001433029533452 ], [ 71.485128269185054, 34.001543433274037 ], [ 71.48599229960297, 34.001540972868369 ], [ 71.485982728920817, 34.001965788576456 ], [ 71.485677917963386, 34.001963409771299 ], [ 71.485663520302097, 34.00200421222096 ], [ 71.485557916396317, 34.002001819508536 ], [ 71.485567513887673, 34.001961017393988 ], [ 71.485118698167781, 34.001963448812212 ], [ 71.485125876678964, 34.001651992925943 ], [ 71.485128269352614, 34.001545833359003 ] ] } },
{ "type": "Feature", "properties": { "Place": "Tennis Lawn" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181035313246, 34.001031478389898 ], [ 71.484926626229907, 34.001030384828667 ], [ 71.484926669794874, 34.001654406918178 ], [ 71.485125876678964, 34.001651992925943 ] ] } },
{ "type": "Feature", "properties": { "Place": "Agriculture Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484897906943033, 34.002035650037541 ], [ 71.484890084806153, 34.002365054141571 ], [ 71.484888323226841, 34.002439237380912 ] ] } },
{ "type": "Feature", "properties": { "Place": "Chemical & Industrial Egineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484888323226841, 34.002439237380912 ], [ 71.484883546063472, 34.002768782456975 ] ] } },
{ "type": "Feature", "properties": { "Place": "Main Gate Entrance" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485118698167781, 34.001963448812212 ], [ 71.485121131034504, 34.002036564553677 ] ] } },
{ "type": "Feature", "properties": { "Place": "Computer System Parking" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484883546063472, 34.002768782456975 ], [ 71.484888363916895, 34.003022079805255 ], [ 71.484600352381278, 34.003002899232484 ] ] } },
{ "type": "Feature", "properties": { "Place": "Computer System Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484888363916895, 34.003022079805255 ], [ 71.484888365089802, 34.003038880399977 ], [ 71.48488837681883, 34.003206886347151 ] ] } },
{ "type": "Feature", "properties": { "Place": "Hostel Road Entrance" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.48488837681883, 34.003206886347151 ], [ 71.484888930241823, 34.003259657448353 ], [ 71.484890807505366, 34.00343866205165 ] ] } },
{ "type": "Feature", "properties": { "Place": "Canteen" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484888930241823, 34.003259657448353 ], [ 71.485097187393905, 34.003252473383881 ] ] } },
{ "type": "Feature", "properties": { "Place": "High Tension Lab" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484888365089802, 34.003038880399977 ], [ 71.485572389638421, 34.003043632815995 ] ] } },
{ "type": "Feature", "properties": { "Place": "New Admin Block (CMS)" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485572389638421, 34.003043632815995 ], [ 71.485975604079186, 34.00304600475129 ] ] } },
{ "type": "Feature", "properties": { "Place": "Road 2 Gate" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485975604079186, 34.00304600475129 ], [ 71.486088447014453, 34.003045322708608 ], [ 71.48638137935751, 34.003043552173651 ] ] } },
{ "type": "Feature", "properties": { "Place": "VC Lawn" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486088447014453, 34.003045322708608 ], [ 71.486085990058683, 34.002789187952963 ] ] } },
{ "type": "Feature", "properties": { "Place": "Electrical Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485572389638421, 34.003043632815995 ], [ 71.485569981549489, 34.002928984566658 ] ] } },
{ "type": "Feature", "properties": { "Place": "Provost Office" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486085990058683, 34.002789187952963 ], [ 71.486090753237178, 34.00225932450293 ], [ 71.485711539310884, 34.002252150722143 ], [ 71.485469132237981, 34.002273768410092 ], [ 71.485303533078067, 34.00236978336995 ], [ 71.485121126788684, 34.002372196189278 ] ] } },
{ "type": "Feature", "properties": { "Place": "Electrical Lawn" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485121126788684, 34.002372196189278 ], [ 71.484890084806153, 34.002365054141571 ] ] } },
{ "type": "Feature", "properties": { "Place": "Director of Works" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.483792886191907, 34.003192857311085 ], [ 71.483894742186976, 34.003214711632012 ] ] } }
]
}

    </script>
 
 
  
 <div id="map">
  
 </div>
sdx11
  • 181
  • 1
  • 1
  • 9
  • So, what is the problem? Without any code or an actual problem, we can't do more than re-iterate how Dijkstra's works, which you have surely already looked up, haven't you? Also, since you seem to have both a start and a goal, why not use A* instead of Dijkstra's? – tobias_k May 22 '17 at 21:25
  • @tobias_k yes i did , but the hard part is coming up with cost of each edge and moving to the goal , i will try A* thanks and update the question – sdx11 May 22 '17 at 22:34
  • I don't really know geoJson, but if it's geo coordinates, can't you just use the Euclidian distance between two points and use that as edge costs? (There are also more complex methods of calculating the distance on a sphere, but for small distances this should be good enough.) – tobias_k May 23 '17 at 07:20
  • See e.g. [here](https://stackoverflow.com/q/27928/1639625) for calculating distance on a sphere with latitude/longitude – tobias_k May 23 '17 at 07:37
  • @tobias_k cost of edge is availabe using a method distanceTo() availabe in Object L.LatLng() , i think the edge system i did is not correct since i am taking only point by point and creating the edge , what can you suggest ? – sdx11 May 23 '17 at 20:57
  • I'm afraid I can not suggest anything, because I still have no idea what your actual problem is. It's not the algorithms, it's not the cost function, so what else? Maybe you should show some of your code and possibly some example input and (actual and expected) output. – tobias_k May 23 '17 at 20:59
  • @tobias_k i added code + existing Dijkstra algorithm on javascript , i only seek edge system so that i can implement it – sdx11 May 24 '17 at 17:43

2 Answers2

1

Your question is too broad. You don't specify a platform (are you going to calculate the shortest path in a web browser? In a JS backend? In a PostGIS DB table with GeoJSON columns?), so that makes us guess. Note that "leaflet features" doesn't add any information, as Leaflet can load data from different data sources also, and does not guarantee that you will be calculating the shortest paths on the frontend side of things.

There are already hundreds of implementations of path-finding algorithms, so:

IvanSanchez
  • 18,272
  • 3
  • 30
  • 45
  • thank you ,i think the geojson path finder from Per Liedman's is the right choice for me – sdx11 May 23 '17 at 17:36
  • i tried the geojson path finder of Per Liedman it doesn't work for me + lack of documentation , i like to use an edge system and build my own algorithm , how can i do that any suggestion ? , my edge system is wrong ! , i can't relay on the successive node to be an edge between two nodes – sdx11 May 23 '17 at 21:01
0

after while searching for solution, the only possible solution was using Per Liedman existing NodeJs package https://github.com/perliedman/geojson-path-finder .

sdx11
  • 181
  • 1
  • 1
  • 9