Leaflet JS: quickest path with custom points

Question

I'm working on a project where i can let users navigate around my client's building. The pathways inside the building are definitely not defined in maps like OSM or google.

Is there a plugin where i can define each point on the pathway and when i set the start and end points, it will find the shortest path?

Custom Points and Route

The image shows the declared points in green, the start(yellow) and end(red) points. The plugin or algorithm should link the relevant points to form the shortest route (shown in purple)

Thank you so much! If there's no plugin out there, i probably have to create one myself.

PS. I'm using Leaflet JS and i'm not depending on OSM or Google maps as i have my own custom image as the layer

hanesh hanesh · Accepted Answer · 2017-01-30T17:20:20

Ok i managed to do it thanks to the andrewhayward's JavaScript implementation of Dijkstra's algorithm which can be found here.

Apart from that, here's what i did...

These functions are just to help me in deriving the nodes and the distances between the nodes to use in the Dijkstra's algorithm :

Step 1 : Add nodes to the map by clicking on specific points

Enable a node to be created when you click on a specific point.

map.on('click', function (e) {
    var node = [];
    node[0] = e.latlng.lat;
    node[1] = e.latlng.lng;
    addNodes(node,curr_node);
});

You have to create a textarea so that the necessary variables can be printed on for you to use in the Dijkstra's algorithm. Once you're done with all the nodes declaration and all that, you can remove the textarea and all these other functions which will not be needed anymore.

Step 2: Function for Nodes that will be added on the map

Every node that gets added will have a 'ctr+click' function so that you can select other nodes that would be linked to that node.

For example if you hold CTRL and click on node A, you can hold ALT (after removing the CTRL button) and select the nodes B, C & D that will be connected to node A. once you're done, simply remove holding the ALT button.

This will display A{B:25,C:15,D:32}, on the textarea for you to use in the Dijkstra's algorithm.

the numbers 25, 15 and 32 are the distances between the respective node to node A. This is calculated by the getDistanceFromLatLonInM function which i improvised from here.

function addNodes(polyNodes,num){
var marker = L.marker([polyNodes[0], polyNodes[1]]).addTo(map);
var myIcon = L.icon({
    iconUrl: 'images/point.png',
    iconSize: [16, 16],
    iconAnchor: [8, 8],
    popupAnchor: [-3, -76]
});
marker.setIcon(myIcon);
marker.on('click',function(e){
    if(ctrlPressed){
        curr_ctrl_pt = [polyNodes[0], polyNodes[1]];
        var oldText = $('#textarea_nodes').val();
        $('#textarea_nodes').val(oldText + num + ':{');
        var myIcon_2 = L.icon({
            iconUrl: 'images/point_c.png',
            iconSize: [16, 16],
            iconAnchor: [8, 8],
            popupAnchor: [-3, -76]
        });
        this.setIcon(myIcon_2); // custom marker to show that the node has been declared. This is just for your own reference
    }
    if(altPressed){
        var oldText = $('#textarea_nodes').val();
        $('#textarea_nodes').val(oldText + num + ':' + getDistanceFromLatLonInM(polyNodes[0], polyNodes[1],curr_ctrl_pt[0],curr_ctrl_pt[1]) + ',');
        }
    })
}
function getDistanceFromLatLonInM(lat1,lon1,lat2,lon2) {
  var R = 6371; // Radius of the earth in km
  var dLat = deg2rad(lat2-lat1);  // deg2rad below
  var dLon = deg2rad(lon2-lon1); 
  var a = 
    Math.sin(dLat/2) * Math.sin(dLat/2) +
    Math.cos(deg2rad(lat1)) * Math.cos(deg2rad(lat2)) * 
    Math.sin(dLon/2) * Math.sin(dLon/2)
    ; 
  var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
  var d = R * c; // Distance in km
  return (d * 1000).toFixed(1);
}

function deg2rad(deg) {
  return deg * (Math.PI/180)
}

I hope this can help someone out there cause i went through alot of thinking to get to this.

All the best!

Leaflet JS: quickest path with custom points

1 Answers