Determine if a Longitude & Latitude Co-ordinate is Inside a Radius in Miles and Kilometers

Question

Using only pseudo-code or JavaScript, can anyone describe the best way to determine which items in array of objects composed of:

{
"lat": float,
"lng": float
}

are within a given radius in either miles or kilometers?

I am adding geo-location-based queries to ForerunnerDB (https://github.com/irrelon/ForerunnerDB) and would like to be able to produce fast results from the search.

Bonus points if you can describe an indexing strategy that will speed up the query over the array. I have written the ForerunnerDB database from the ground up so can be flexible with integrating the answer into the code, but the main concern is query performance.

While the question pertains to a new feature of ForerunnerDB, it does not require that you go and read that project's source or familiarise yourself with that system and a pseudo-code or stand-alone JS example would be very welcome!

Answer 1

Here is a simple "direct" approach using Haversine formula:

//This function takes in latitude and longitude of two locations
// and returns the distance between them as the crow flies (in meters)
function calcCrow(coords1, coords2)
{
  // var R = 6.371; // km
  var R = 6371000;
  var dLat = toRad(coords2.lat-coords1.lat);
  var dLon = toRad(coords2.lng-coords1.lng);
  var lat1 = toRad(coords1.lat);
  var lat2 = toRad(coords2.lat);

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

// Converts numeric degrees to radians
function toRad(Value)
{
    return Value * Math.PI / 180;
}

I believe this code might have come from here: Function to calculate distance between two coordinates shows wrong

The only optimisation I see is adding tangents for both latitude and longitude to cut out the results that are far outside the search region.

P.S. I really like ForerunnerDB and can't wait to see geo-related functionality