Whilst working on a mobile development project a while back, we stumbled on quite a few technical challenges regarding the triangulation of given points. I will be posting a couple of articles on the various details of those challenges. Firstly, I’m going to look at how to find the nearest location from a triangulated point by a series of mobile towers.
Mobile user location tracking can be achieved by various means of technologies. The mobile service provider and the integration service will return a location of mobile user (latitude and longitude), the challenge is to provide the nearest point of interest (POI) back to the user. So the answer was to calculate the distance between mobile user and point of interest. It’s easy, the difference between two points, right? Yes, but… the earth’s surface is not flat, it’s spherical – or to be more precise, elliptical.
This distances are most accurately represented as points on sphere. To find the distance between two points on sphere, you have to use Haversine formula:
- haversin is the haversine function, haversin(θ) = sin2(θ/2) = (1−cos(θ))/2
- d is the distance between the two points (along a great circle of the sphere; see spherical distance),
- R is the radius of the sphere,
- φ1 is the latitude of point 1,
- φ2 is the latitude of point 2, and
- Δλ is the longitude separation,
- h is haversin(d/R)
So, how do we convert this mathematical jargon into practical and useful text? Well, after couple of days of struggling, I managed to transfer this mathematical giant into an SQL function with the help of this haversine post.
CREATE FUNCTION dbo.Haversine
WITH EXECUTE AS CALLER
DECLARE @R INT, @dLat FLOAT, @dLon FLOAT, @a FLOAT, @c FLOAT, @d FLOAT
SET @R = 6371 -- this value is in Km
SET @dLat = RADIANS( @Lat2 - @Lat1 )
SET @dLon = RADIANS( @Lon2 - @Lon1 )
SET @a = SIN( @dLat / 2 ) * SIN( @dLat / 2 ) +
( COS( RADIANS ( @lat1 ) ) * COS( RADIANS ( @lat2 ) ) *
SIN( @dLon / 2 ) * SIN( @dLon / 2 ) )
SET @c = 2 * ATN2( SQRT( @a ), SQRT( 1 - @a ) )
SET @d = @R * @c -- in Km
This formula returns the distance between two points in kilometres. At the same time, it does not consider the earth’s bearing (angular distance) as we were dealing with very small part of earth’s overall surface. All angles are in radians.
Once you have the distance between two points on the earth’s surface; it’s just matter of sorting them into ascending order so they serve the nearest required results.