Haversine Distance Optimisation

Benchmark created by Fintan on

Description

A javascript implementation of the Haversine distance formula is given here.

This test case experiments with improving the performance of this function, for when the function will be called thousands of times and performance matters.

Preparation HTML

<script>
  var TO_RAD = Math.PI / 180;
  
  function toRad(deg) {
    return deg * TO_RAD;
  }
  
  var coords = new Array();
  
  function randomLat() {
    return Math.random() * 180 - 90;
  }
  
  function randomLong() {
    return Math.random() * 360 - 180;
  }
  
  for (var i = 0; i < 5000; i++) {
    coords.push([randomLat(), randomLong(), randomLat(), randomLong()]);
  }
  
  function compute(coord, f) {
    return f(coord[0], coord[1], coord[2], coord[3]);
  }
  
  function test(f) {
    for (var i = 0; i < coords.length; i++) {
      var coord = coords[i];
      compute(coord, f);
    }
  }
</script>

Test runner

Ready to run.

Testing in
TestOps/sec
Original
function distance1(lat1, lon1, lat2, lon2) {
  var R = 6371009; // m
  var dLat = toRad(lat2 - lat1);
  var dLon = toRad(lon2 - lon1);

  var a = Math.sin(dLat / 2) * Math.sin(dLat / 2) + Math.cos(toRad(lat1)) * Math.cos(toRad(lat2)) * Math.sin(dLon / 2) * Math.sin(dLon / 2);
  var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
  return R * c;
}

test(distance1);
ready
Optimised1
var R = 6371009; // m

function distance2(lat1, lon1, lat2, lon2) {
  var aLat = toRad(lat1);
  var bLat = toRad(lat2);
  var dLat2 = (bLat - aLat) / 2;
  var dLon2 = toRad(lon2 - lon1) / 2;
  var x = Math.sin(dLat2) * Math.sin(dLat2) + Math.cos(aLat) * Math.cos(bLat) * Math.sin(dLon2) * Math.sin(dLon2);
  return R * 2 * Math.atan2(Math.sqrt(x), Math.sqrt(1 - x));
}

test(distance2);
ready
Optimised2
var R2 = 6371009 * 2; // m

function distance3(lat1, lon1, lat2, lon2) {
  var aLat = toRad(lat1);
  var bLat = toRad(lat2);
  var dLat2 = (bLat - aLat) * 0.5;
  var dLon2 = toRad(lon2 - lon1) * 0.5;
  var sindLat = Math.sin(dLat2);
  var sindLon = Math.sin(dLon2);
  var x = sindLat * sindLat + Math.cos(aLat) * Math.cos(bLat) * sindLon * sindLon;
  return R2 * Math.atan2(Math.sqrt(x), Math.sqrt(1 - x));
}

test(distance3);
ready
Optimised3
var R2 = 6371009 * 2; // m

function distance4(lat1, lon1, lat2, lon2) {
  var aLat = lat1 * TO_RAD;
  var bLat = lat2 * TO_RAD;
  var dLat2 = (bLat - aLat) * 0.5;
  var dLon2 = (lon2 - lon1) * TO_RAD * 0.5;
  var sindLat = Math.sin(dLat2);
  var sindLon = Math.sin(dLon2);
  var x = sindLat * sindLat + Math.cos(aLat) * Math.cos(bLat) * sindLon * sindLon;
  return R2 * Math.atan2(Math.sqrt(x), Math.sqrt(1 - x));
}

test(distance4);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.