Algorithm to calculate the nearest location (from the database) based on logitude & latitude

Question

What i want to do is develop an algorithm to calculate which known locations are closest to the selected location. Let's say i have 7 locations in the database and when the user selects one, he should have the option to see the, let's say, first 3 closest locations (from the database). In the database, each location is saved with latitude and longitude.

Any idea on how i can do that?

Example: Say the list contains 100 locations of bike stations. I am at station 5, and I want to find out what other stations in the list lies nearby. Not the distance, but their location.

Rachellerachis

And where is your code? Distance between two points is a simple equation based on Pythagoras theorem. Have you Googled for this? – Waylay

Look into the k-d tree algorithm en.wikipedia.org/wiki/K-d_tree – Hereabouts

Of course i Googled, but i'm not looking for how to calculate the distance, as i said in the 'question', i want to find out their location – Rachellerachis

lat/lon is a location...so you already have it. And with the distance (like in my answer) you can calculate the closest 3. – Armalla

Also u may have a look at database built-ins. If I am not mistaking, SQL server has methods to work with spatial data. – Asperse

Might have @cyberpug2077, but i preferred some c# or javascript code rather than sql, because i'm not that 'skilled' in working with databases. – Rachellerachis

Answer 1

Good question, Let's think we have following three value in DB:

var dataFromDb = [{
    "location": "First location",
    "lat": "1.28210155945393",
    "lng": "103.81722480263163",

}, {
    "location": "Second location",
    "lat": "1.2777380589964",
    "lng": "103.83749709165197",
    "location": "Stop 2"
}, {
    "location": "Third Location",
    "lat": "1.27832046633393",
    "lng": "103.83762574759974",
}];

Create a function for the distance between two places:

function distanceBetweenTwoPlace(firstLat, firstLon, secondLat, secondLon, unit) {
        var firstRadlat = Math.PI * firstLat/180
        var secondRadlat = Math.PI * secondLat/180
        var theta = firstLon-secondLon;
        var radtheta = Math.PI * theta/180
        var distance = Math.sin(firstRadlat) * Math.sin(secondRadlat) + Math.cos(firstRadlat) * Math.cos(secondRadlat) * Math.cos(radtheta);
        if (distance > 1) {
            distance = 1;
        }
        distance = Math.acos(distance)
        distance = distance * 180/Math.PI
        distance = distance * 60 * 1.1515
        if (unit=="K") { distance = distance * 1.609344 }
        if (unit=="N") { distance = distance * 0.8684 }
        return distance
}

Define current place:

var currentLat = 1.28210155945393;
var currentLng = 103.81722480263163;

Find Records within 1KM:

for (var i = 0; i < data.length; i++) {
    if (distance(currentLat, currentLng, data[i].lat, data[i].lng, "K") <= 1) {
        console.log(data[i].location);
    }
}

Veteran

Very explicit and nice, i'll try it and come back with a reply. Thanks a lot! – Rachellerachis

Answer 2

You can view a great example on how to calculate it here.

From this site:

var R = 6371e3; // metres
var φ1 = lat1.toRadians();
var φ2 = lat2.toRadians();
var Δφ = (lat2-lat1).toRadians();
var Δλ = (lon2-lon1).toRadians();

var a = Math.sin(Δφ/2) * Math.sin(Δφ/2) +
        Math.cos(φ1) * Math.cos(φ2) *
        Math.sin(Δλ/2) * Math.sin(Δλ/2);
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));

var d = R * c; //<-- distance between lat1/lon1 and lat2/lon2

Armalla

This one is pretty nice, I already saw it, but i want to find the actual location of the 'station'. Let's say the ones who are closer than 1 km from me. – Rachellerachis

Yeah and for that you have to calculate the distance for every one of them. Then sort it and pick the first three. – Armalla

Yeah, you are actually right, didn't think of that. I will try doing that and i'll come with a reply. But one more question, i know it my sound dumb, is the distance between 2 location calculated in meters? – Rachellerachis

The site states kilometers so I assume it would be that. But you can test it easily by using the same values as on the site and check the result. If its the same its kilometers. If its 1000x the value its meters. – Armalla

Cool, very helpful, i'll try it out. Thanks. – Rachellerachis