Okay, so it’s 2019, location services are everywhere, even most desktop computers now have a pretty accurate sense of their physical location in the world, and the rise of portable apps built around user location, from food order apps such as Just Eat, to dating apps such as Tinder, has made any IT companies knowledge of location skyrocket. For those diving deeper into the core of this, a thorough understanding of longitude and latitude comes in handy; yet one thing still seems to be missing, what exactly is the BEST way to find a group of restaurants, places, taxis or even people in the local area, especially while dealing with potentially millions of users.

This issue came up recently here at Prudent Pixel, a client is building a service which – like many services today, requires the ability to find all of a certain – potentially user inputted locations within “the local area”. So how do we do this? In this part one of this blog post we will talk about the common methods out there today, and the biggest downfall to that – in part two we will dive deeper into how we have optimised the performance! If you have ideas on how to optimise performance or know another way to do so, make sure you join our discussion over on our LinkedIn page!

Right, so let’s say for arguments sake that we are dealing with a large number of users, and when the user navigates to the website or opens the app, we want to show the user all the fast food restaurants within a 30 km radius. Now to ensure we keep this complicated enough, let’s assume that this app is designed to be used in multiple countries, so there’s no smart postcode or equivalent type system we can use to discover nearby places. We simply have to rely of the longitude and latitude of the user, and the respective restaurants.

Let’s start by looking at how we can measure the distance between the user and their nearest restaurant – which for now we will assume we will magically know. Because I need some test data, and I want to avoid landing on anyone’s house, I’m going to assume that our user is at Swasey Peak, Utah, USA (39.388281, -113.316093) – now I’ve never visited nor do I know anything about this Peak other than it’s South West of Salt Lake City – and while I am guessing there probably aren’t a lot of restaurants in the area, we are going to pretend that our nearest restaurant is located slightly to the east of our user at 39.389412, -113.050441. The first thing I might point out here is to make sure you check your calculation types going forward – it’s harder to not notice with locations as the decimal longitude and latitude look very to sexagesimal degree (where 39.389412, -113.050441 is equal to 39°23’21.9″N 113°03’01.6″W), but later in the calculations it’s worth remembering this – I spent a long time scratching my head until I realised I was trying to do calculations in radians while my calculator was set to degrees!

The next few things we need to remember are:

It’s worth also noting that the earth is not a perfect sphere it’s slightly egg shaped – but for the sake of this post we are going to assume a perfect sphere.

We now get into the maths! Firstly, take the difference of the two latitudes, multiple it by Pi and divide by 180 (Representing half a circle). Note our examples are written for JavaScript, you may need to make some changes for other languages! After that do the same for longitude.

// For simplicity in this example we will use 5 decimal places in most rough calculations and round where necessary
var latDistance = (lat2 - lat1) * Math.PI / 180; 
// (39.389418 - 39.388281) * 3.14159 / 180 = 0.00001984
var lonDistance = (lon2 - lon1) * Math.PI / 180;
// (-113.050441 - -113.316093) * 3.14159 / 180 = 0.00464

Here comes the complicated bit – I’ve stored this in a variable named X. We are going to take the sine of half the calculated latitude distance, multiplied by itself, plus the cosine of the users latitude (lat1 in my example) multiplied by pi and divided by 180, multiplied by the cosine of the restaurant latitude (lat2 in my example) multiplied by pi and divided by 180, then multiplied by the sine of half the longitude distance multiplied by itself.

Confused yet? Okay, first let’s tackle one of the things we keep having pop up – a position multiplied by pi divided by 180 – what is this doing? By doing this we convert degrees to radians, and by taking a number, multiplying by 180 and dividing by pi, we convert from radians back to degrees. So really, to try and put this is a more technical perspective, our latDistance and lonDistance represent the radians moved along the x and y planes. Now let’s move on to the code for that more confusing part:

var x = Math.sin(latDist/2) * Math.sin(latDist/2) + Math.cos(lat1 * Math.PI / 180) * Math.cos(lat2 * Math.PI / 180) * Math.sin(lonDist/2) * Math.sin(lonDist/2);
// Don't forget BODMAS here!
// x = sin(0.00000992) * sin(0.00000992) + cos(0.68745) * cos(0.68747) * sin(0.00232) * sin(0.00232)
// x = 0.00009919 * 0.00009919 + 0.77287 * 0.77285 * 0.00232 * 0.00232
// x = 0.00000000984 + 0.000051329
// x = 0.000003215

Following? I sure hope so – if not the code is all at the bottom! Next we have a handy function we call in JavaScript! The function in JavaScript is called “Math.atan2()” and it takes two parameters, but for those not using JavaScript, or just for the sake of being able to do the calculation – here’s what it actually does! Officially it “returns the angle in the plane (in radians) between the positive x-axis and the ray from (0,0) to the point (x,y)” (Source: https://developer.mozilla.org/) in reality there are two bits you need to remember – the first will confuse you, don’t ask why it is this way, but the parameters and y and x – NOT x and y as one might imagine! Next: if x is greater than 0, it equals inverse tangent of y over x, if x is less than 0 and y is greater than or equal to 0, it equals inverse tangent y over x plus pi, if x is less than 0 and y is less than 0, it equals inverse tangent y over x minus pi. If x is zero and y is greater than zero, it equals pi over 2, while is x is zero and y is less than 0, it equals negative pi over 2. And if both x and y are zero it will return undefined. Now that’s out of the way, we are going to use the square root of our x as y and the square root of 1-x as our x. Meaning we have y = 0.00179 and x = 0.99999. As our x is greater than zero we simply use inverse tangent y over x. Finally we multiply the result by two to give us the distance in radians! Almost there!

var distanceInRadians = 2 * Math.atan2(Math.sqrt(x), Math.sqrt(1-x));
// atan2 function = 2 * Math.atan2(0.00179, 0.99999)
// atan2 function = 2 * Math.atan(0.00179) <-- NB: atan2 has become atan
// atan result = 2* 0.00179
// distanceInRadians = 0.00358

Right – we now have our distance displayed in radians! Remember earlier I mentioned that the earth has a radius of 6,371kms? All we have to do now is multiply our radians but the radius of the circle we want to calculate the distance for! So:

var calculatedDistance = 6371 * 0.00358
// calculatedDistance = 22.80818

Right, that was a long function and the final number is 22.8 kms. Keep in mind we only used 5 decimal places and there was some rounding in there which of course in your code wouldn’t happen… Drum-roll please! Point to point measured on Google Maps…. Ah now come on, I wouldn’t have written this and not already checked it before publishing! 22.83 kms. Accurate enough!

So after all of that you have now learned the Haversine Formula! It does have an official name, and differs from most trigonometry but calculating the distance along an arc around a triangle.

Of course this doesn’t solve our initial problem – we want to find ALL the restaurants within a 30 km radius, sure in our example in the middle of the state of Utah it’s possible we have found all the restaurants but only by chance! We know how to calculate once we have the restaurant, but how do we find all the restaurants. To my frustration as I searched the web for how others had solved this problem, the main suggestion was to go through a process of running through all the possible restaurants and completing the Haversine formula. Would this work? Yes. Is it efficient? Oh no… Not in the slightest. Would I write a blog post about a piece of work we have put into a clients project if it wasn’t efficient and I didn’t have a better solution – sanity would say no! So stay tuned for Part 2 next week where I will discuss our solution to this unique problem!

The simple code in full:

function getDistance(lat1, lon1, lat2, lon2) {
    var earthRadius = 6371; // Set to 3956 for miles
    var latDistance = (lat2 - lat1) * Math.PI / 180; 
    var lonDistance = (lon2 - lon1) * Math.PI / 180;
    var x = Math.sin(latDist/2) * Math.sin(latDist/2) + Math.cos(lat1 * Math.PI / 180) * Math.cos(lat2 * Math.PI / 180) * Math.sin(lonDist/2) * Math.sin(lonDist/2);
    var distanceInRadians = 2 * Math.atan2(Math.sqrt(x), Math.sqrt(1-x));
    var calculatedDistance = earthRadius * distanceInRadians;
    return calculatedDistance;
}