Query nearest latitude and longitude from SQLite

Searching for nearby locations is one of the most popular features we see in every app. In this topic, we will see how to implement a SQL query with a with a large dataset of location records. We will see how to calculate the distance and find the closest bus stop to our location.

Assuming that we are at Kovan Station, how to find the nearest bus stops within a radius of 300 meters? First of all, to get the nearest stops we need to calculate the distance from our location to all the bus stops in Singapore.

Table of contents

Calculate the distance on the earth using coordinates

In spherical trigonometry, the law of cosines is a theorem relating the sides and angles of spherical triangles, analogous to the ordinary law of cosines from plane trigonometry.

Spherical triangle solved by the law of cosines. Given a unit sphere, a “spherical triangle” on the surface of the sphere is defined by the great circles connecting three points u, v, and w on the sphere. If the lengths of these three sides are a (from u to v), b (from u to w), and c (from v to w), and the angle of the corner opposite c is C, then the spherical law of cosines states:

cos c = cos a ⋅ cos b + sin a ⋅ sin b ⋅ cos C

Applying the formula, we can calculate the distance between two points on the surface of the Earth. We consider the triangle vuw, where u is the North Pole. The angle of vuw is C = w_longitude - v_longitude. The angular length of uv is u_latitude - v_latitude, and the angular length of uw is u_latitude - w_latitude. The actual distance from v to w can be computed using the radius of the Earth, 6371 km.

Example: Singapore is at 1.3521° N, 103.8198° E, Saigon is at 10.8231° N, 106.6297° E, and North Pole is at 90.0000° N, 135.0000° W.

Let say v is Singapore and w is Saigon, we knew u is the North Pole. We compute:

C = w_longitude - v_longitude = 106.6297° - 103.8198° = 2.8099°
a = uv = u_latitude - v_latitude = 90° - 1.3521° = 88.6479°
b = uw = u_latitude - w_latitude = 90° - 10.8231° = 79.1769°

Applying the formulate.

cos c = cos a ⋅ cos b + sin a ⋅ sin b ⋅ cos C

We get:

cos c = cos (88.6479°) ⋅ cos (79.1769°) + sin (88.6479°) ⋅ sin (79.1769°) ⋅ cos (2.8099°)
cos c = 0.9851884112

Then c = acos (0.9851884112) = 0.1723270018

Given radius of the Earth is 6371 km. The distance between Singapore and Saigon is 0.1723270018 * 6371 equals 1097.895328 km.

Develop a SQL query using the Spherical Law of Cosines

Once we understand the formula of calculating the distance on the Earth’s surface. We can develop our SQL query to get the nearest bus stops within a specific radius.

Assuming that we already had a Table of bus stops with these columns: stop_name, latitude, longitude.

For example, our current location is at Kovan Station at 1.360175° N, 103.882974° E. Let find the nearby stops within 300 meters.

SELECT stop_name, latitude, longitude,
	acos(
		sin(1.360175 * PI() / 180) 
		* sin(lat * PI() / 180) 
		+ cos(1.360175 * PI() / 180) 
		* cos(lat * PI() / 180) 
		* (
			sin(103.882974 * PI() / 180) 
			* sin(lng * PI() / 180) 
			+ cos(103.882974 * PI() / 180) 
			* cos(lng * PI() / 180)
		)
	) * 6371000 AS distance
FROM BusStop
WHERE distance < 300
ORDER BY distance ASC

Note that the function takes in the radian value, so we have to convert from degree to radian by multiple PI / 180. In the query, if we want to compare in the meter unit we have to convert Earth radius to meter unit, 6371000 meters.

Develop a compatible query for mobile SQLite

Now, if we apply the query above to a mobile app. We get an error message.

"no such function: acos" UserInfo={NSLocalizedDescription=no such function: acos}

It means the mobile SQLite does not support the function acos. All the trigonometric functions are not supported. Technically, it can be done by implementing native code functions, but it’s too complicated. There is a simple way to implement it by precalculate the value of sin and cos. However, the input of cos C is impossible to precalculate because it requires longitudes of two points. To resolve it, we can apply some basic math to rearrange the formula.

Apply the Spherical Law of Cosines, we get:

cos c = cos a ⋅ cos b + sin a ⋅ sin b ⋅ cos C

cos a = cos (ulat - vlat) = cos (90 - vlat) = sin vlat

cos b = cos (ulat - wlat) = cos (90 - wlat) = sin wlat

sin a = sin (ulat - vlat) = sin (90 - vlat) = cos vlat

sin b = sin (ulat - wlat) = sin (90 - wlat) = cos wlat

cos C = cos (wlon - vlon) = cos wlon ⋅ cos vlon + sin wlon ⋅ sin vlon

Thus, we get an equivalent formula:

cos c = sin vlat ⋅ sin wlat + cos vlat ⋅ cos wlat ⋅ (cos wlon ⋅ cos vlon + sin wlon ⋅ sin vlon)

Therefore, the bus stop table requires 4 extra columns for cos and sin of latitude and longitude of all the bus stops and requires calculating before inserting into the table.

Assuming, we have a table of all bus stop with these columns: stop_name, latitude, longitude, cos_lat, sin_lat, cos_lon, sin_lon.

String getNearbyBusStop(double latitude, double longitude, double radius) {
    final curCosLat = cos(latitude * pi / 180.0);
    final curSinLat = sin(latitude * pi / 180.0);
    final curCosLng = cos(longitude * pi / 180.0);
    final curSinLng = sin(longitude * pi / 180.0);
    final cosRadius = cos(radius / 6371000.0);
    final cosDistance = "$curSinLat * sin_lat + $curCosLat * cos_lat * (cos_lon * $curCosLng + sin_lon * $curSinLng)";

    return """
    SELECT stop_name, latitude, longitude, $cosDistance AS cos_distance 
    FROM BusStop
    WHERE $cosDistance > $cosRadius
    ORDER BY $cosDistance DESC
    """;
}

Note that, here we compare the cos distance because the SQLite on mobile does not support the cos function. Both methods are equivalent, but here we have to reverse the comparing and order since the arccos function is the inverse of the cosine function.

As a result, we can get the list of nearest bus stops similar to the original query. If we need the distance value, we can calculate it by using the function arccos(cos_distance) then multiply it to the Earth radius, 6371000 meters. Example: acos(0.9999999999914334) x 6371000 = 26 meters.

Apply the Spherical Law of Cosines to the mobile app

SG Bus Tracker is a bus estimated arrival time app in Singapore. In this app, I already precalculated the cos and sin values of latitude and longitude for all the bus stops. That means the app was shipped with around 5000 offline records with the advantages of reducing stress to the server.

For example: here we are at Kovan Station 1.360175° N, 103.882974° E. Let searching for nearby bus stops within a radius of 300 meters.

Additional resources

When the app was successfully launched, it is hard to understand the final formula that can be used with SQLite on the mobile device. While searching for the material to complete this article, I can understand the original idea of the formulate and why it needs to rearrange.

Calculate distance, bearing and more between Latitude/Longitude points

Spherical Law Of Cosines

SG BusTracker