What's the fastest way to find which coordinates are in a certain perimeter?

Question

Let's say that i have a database of 100,000 coordinates, i need to find which ones are less than 1 mile away from a certain coordinate.

What's the most efficient way to do this?(in any language)

Answer 1

Firstly, we have to write a basic function to calculate the distance between 2 points:

function distance(lat1, lon1, lat2, lon2) {}

For this example, I will base the function on the formula of a spherical earth projected to a plane (here) Firstly, we have to calculate the deltas (the distance in degrees between the lat and longs) and the mean latitude (average of latitudes):

var dLat = lat1 - lat2;
var dLon = lon1 - lon2;
var mLat = (lat1 + lat2) / 2;
var earthRadius = 3959; //in miles

Then we convert those to Radians using d=180/PI rad:

dLat = dLat * 180 / 3.1415926535;
dLon = dLon * 180 / 3.1415926535;
mLat = mLat * 180 / 3.1415926535;

Now, we use the formula to transform our data into distance:

var distance = earthRadius * (dLat * dLat + Math.pow(Math.cos(mLat) * dLon, 2));

And return the distance

return distance;

Now, just iterating through all the points and checking if the distance is ok for each one. Let's say a point is described in this way:

var p = {
    lat = ...
    lon = ...
}

And assuming there is a list of points (for example, named points) and a reference point (for example, named ref).

var result = []
points.forEach(function (d) {
    if (distance(d.lat, d.lon, ref.lat, ref.lon) <= 1) {
        result.push(d);
    }
};

You can also check for latitude boundary box - longtitude requires more complex calculations and it's just a waste of time. You can determine a mile in degrees is 1/69 deg/mile (approximately 0.1449 degrees). So you can check which points are outside of this boundary box:

var result = []
var maxLat = ref.lat + 0.1449;
var minLat = ref.lat - 0.1449;
points.forEach(function (d) {
    if (d.lat > maxLat || d.lat < minLat) continue;
    if (distance(d.lat, d.lon, ref.lat, ref.lon) <= 1) {
        result.push(d);
    }
};

Then you should finish with an array of points that are closer than 1 mile from the reference point.

I might have a mistake in the formula things (I'm more like a programmer than a mathematican). So double check if they work with the Wikipedia article I added a link to.