5
\$\begingroup\$

So I have a solution for this which uses a for loop and calculates distance between the main point and other points. I found the code for distance between two points online, changed it to my needs and wrote the rest of the code. While this code works pretty well, I'm just curious if there's a better and more efficient way of doing this. This fits really well with my current code as it's just a small scale project. But I always like looking for stuff I can optimise and improve.

function findDistanceInKm(location1, location2) {
    const lat1 = location1.lat;
    const lon1 = location1.lon;
    const lat2 = location2.lat;
    const lon2 = location2.lon;
    const earthRadius = 6371;
    const dLat = convertDegToRad(lat2 - lat1);
    const dLon = convertDegToRad(lon2 - lon1);
    const squarehalfChordLength =
      Math.sin(dLat / 2) * Math.sin(dLat / 2) +
      Math.cos(convertDegToRad(lat1)) * Math.cos(convertDegToRad(lat2)) *
      Math.sin(dLon / 2) * Math.sin(dLon / 2);

    const angularDistance = 2 * Math.atan2(Math.sqrt(squarehalfChordLength), Math.sqrt(1 - squarehalfChordLength));
    const distance = earthRadius * angularDistance;
    return distance;
}

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

let nearLocations = [];
let newLocation = {
    lat: 65.33714,
    lon: -82.11508
}

let locationList = [
    {
        lat: 65.33714,
        lon: -82.11503
    },
    {
        lat: -1.38370,
        lon: 10.32156
    },
    {
        lat: -69.98601,
        lon: 18.80178
    },
    {
        lat: -29.37968,
        lon: -156.32350
    },
]

for(let i =0; i < locationList.length; i++){
    let distance = findDistanceInKm(newLocation, locationList[i]);
    console.log(distance)
    if(distance < 1){
        nearLocations.push(locationList[i])
    }
}
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

There are a number of performance optimization tricks that you can take advantage of when trying to find efficiency. One mechanism commonly used is to reduce complexity of the code by algorithmic change..... but in your case, you can't really improve the "Big O" complexity that way, you are running at O(n) already, and there's nothing you can do to improve that.

So, it then comes down to nickel-and-diming the current algorithm to shave time off of the work you're already doing. This requires looking at the expensive computations, and reducing the number of operations to improve them.

In your example, you're converting degrees to radians often. In the case of newLocation you're doing it repeatedly for each comparison. It would make sense for you to convert all locations to radian form, and then not have any conversions inside the computation loop. This will be especially useful if your real-world code has to do multiple comparisons on the locations.

So, simply doing something like (include the radian values as part of the location):

func locationToRadians(degrees) {
  return {
    lat: degrees.lat,
    lon: degrees.lon,
    rlat: convertDegToRad(degrees.lat),
    rlon: convertDegToRad(degrees.long)
  }
}


const locationListRadians = locationList.map(locationToRadians);

Do the same with the fromLocation.

Now, in your distance function, you're repeating complex computations (trig functions are non-trivial at a computational level, so let's avoid repeats - I realize that premature optimization is not always great, but this also improves the readability). Your distance computation is significantly simpler:

function findDistanceInKm(location1, location2) {
    const sinLat = Math.sin((location2.rlat - location1.rlat) / 2);
    const sinLon = Math.sin((location2.rlon - location1.rlon) / 2);
    const earthRadius = 6371;
    const squarehalfChordLength =
      sinLat * sinLat +
      sinLon * sinLon *
      Math.cos(location1.rlat) * Math.cos(location2.rlat);

    const angularDistance = 2 * Math.atan2(Math.sqrt(squarehalfChordLength), Math.sqrt(1 - squarehalfChordLength));
    const distance = earthRadius * angularDistance;
    return distance;
}

Now, you can add in the distances that way.

The savings from doing the above will only be noticeable if you reuse computations often, but in a busy system where lots of locations are being repeatedly compared to each other I can easily see a 50% CPU saving.

As a final comment, the last loop does not need the indexing mechanism, a filter is better:

const neadLocations = locationList.filter(location => {
    const distance = findDistanceInKm(newLocation, location);
    console.log(distance);
    return distance < 1
});

(it would be better without the console logging in there...)

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Wow I didn't really expect this in depth of an answer, thank you so much. Will make changes to the current code. Thank you again \$\endgroup\$
    – KSJaay
    Commented Mar 2, 2021 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.