The Haversine formula and the Location API for Location-Based Services
Some location-based services operate on the basis of geographical distance. Usually, this concerns the distance between two (geographical) points, being the location of the user at the time he or she uses the service and a certain Point Of Interest (POI). Several examples of such services can be thought of, such as Location-Based Advertising and requesting the nearest ATM. In this article I will present a case demonstrating an implementation of the core functionality of such a service in which two key components are highlighted: the Haversine formula and the J2ME Location API.
The case consists of a J2ME application (the client) that determines the user's current coordinates using the Location API and sends these coordinates to a PHP script (the service) over the Internet. Using the Haversine formula, this script calculates the distance to the POI and returns it to the client. For illustrative purposes, the user's location is Station Utrecht Centraal and the POI is the Oudegracht in Utrecht.
The following image shows a map on which both locations are marked including their coordinates (latitude and longitude).
The line that connects the two locations represents the distance that we want to calculate. It is important to know that the Haversine formula calculates the distance 'as the crow flies'. It does not take into account any obstacles that may lie in between, such as differences in the altitude of the Earth's surface and the transport infrastructure. The actual distance that one needs to travel in order to reach the POI can (and in most cases will) differ from the calculated distance. How acceptable that is depends on the type of service.
The Haversine formula
If the world would consist of only two spatial dimensions (such as a map in the image above suggests), then basal trigonometry would have been sufficient to calculate the distance. However, since the Earth is a three-dimensional 'sphere', the curving of its surface needs to be taken into account. The Haversine formula offers a solution to this problem. Note, however, that the Earth is actually not a perfect sphere, but an oblate spheroid. The Haversine formula calculates a great-circle distance which assumes a perfect sphere. Therefore, the Haversine formula is not completely accurate. Although its accuracy is acceptable for most purposes, you could use the inverse method of Vincenty's formulae to achieve a more accurate result.
The expression of the Haversine formula is listed below.
R = 637100 (the Earth's radius in meters)
Δlatitude = latitudepoi - latitudeuser
Δlongitude = longitudepoi - longitudeuser
a = sin2(Δlatitude / 2) +
cos(latitudeuser) ∙ cos(latitudepoi) ∙ sin2(Δlongitude / 2)
c = 2 ∙ atan2(√a, √(1 - a))
distance = R ∙ c
The unit of the resulting distance corresponds to the unit in which the Earth's radius (R) is expressed on the first row. In this case the unit is in meters. The Haversine formula can now be implemented in the software.
The service and the implementation of the Haversine formula
The service is a PHP script that requires two GET parameters: the latitude and longitude of the user. Refer to the following listing.
<?php
$user = new POI($_GET["latitude"], $_GET["longitude"]);
$poi = new POI(52.089211, 5.121367); // Oudegracht, Utrecht
echo $user->getDistanceInMetersTo($poi);
class POI
{
// Class implementation
}
?>
Two instances of the class POI are created, one for the user (in this context the user can also be regarded as a POI) and one for the Oudegracht being the formal POI. The latitude and longitude are passed to the constructor. Then the method getDistanceInMetersTo() is invoked to calculate the distance between the two locations. The result of this method is returned to the client as a HTTP response.
The implementation of the class POI is presented in the listing below.
class POI
{
private $latitude;
private $longitude;
public function __construct($latitude, $longitude)
{
$this->latitude = deg2rad($latitude);
$this->longitude = deg2rad($longitude);
}
public function getLatitude()
{
return $this->latitude;
}
public function getLongitude()
{
return $this->longitude;
}
public function getDistanceInMetersTo(POI $other)
{
// Method implementation
}
}
Since the calculation solely uses radians, the latitude and longitude are converted to that unit in the constructor directly. The method getDistanceInMetersTo() implements the Haversine formula. Refer to the listing below.
public function getDistanceInMetersTo(POI $other)
{
// Define the Earth's radius in meters.
$radiusOfEarth = 6371000;
// Apply the Haversine formula to calculate the distance.
$diffLatitude = $other->getLatitude() - $this->latitude;
$diffLongitude = $other->getLongitude() - $this->longitude;
$a = sin($diffLatitude / 2) * sin($diffLatitude / 2) +
cos($this->latitude) * cos($other->getLatitude()) *
sin($diffLongitude / 2) * sin($diffLongitude / 2);
$c = 2 * atan2(sqrt($a), sqrt(1 - $a));
$distance = $radiusOfEarth * $c;
// Return the distance.
return $distance;
}
The J2ME client application
The Location API (JSR 179) is an optional package for the J2ME platform. This API offers an abstract interface to a resource - such as a GPS receiver - from which the current geographical location can be requested. (The Nokia N85 is an example of a mobile phone that offers access to the built-in GPS receiver through the Location API.) Our client application uses the Location API to determine the user's current location and sends the coordinates as GET parameters of a HTTP request to the service.
The listing of the client application is presented below.
package nl.jeroenoosterlaar.haversine;
import java.io.InputStream;
import javax.microedition.io.*;
import javax.microedition.lcdui.*;
import javax.microedition.location.*;
import javax.microedition.midlet.MIDlet;
public class HaversineClientMIDlet extends MIDlet
{
public void startApp()
{
try
{
// (1) Determine the GPS coordinates through the
// Location API.
// (2) Request the service URI passing the
// coordinates to retrieve the distance.
// (3) Display the distance.
}
catch(Exception e)
{
}
}
public void pauseApp()
{
}
public void destroyApp(boolean unconditional)
{
}
}
The application consists of a single MIDlet and everything is implemented in the method startApp(). In order to make an explicit distinction between the phases, I have replaced the code of this method with comments and divided it in separate blocks below respectively.
(1) Determine the GPS coordinates through the Location API
Criteria criteria = new Criteria(); LocationProvider provider = LocationProvider.getInstance(criteria); Location location = provider.getLocation(60); QualifiedCoordinates coordinates = location.getQualifiedCoordinates(); double latitude = coordinates.getLatitude(); double longitude = coordinates.getLongitude();
(2) Send the coordinates to the service and receive the calculated distance
String serviceURI = "http://www.jeroenoosterlaar.nl/lab/haversine/service.php?" +
"latitude=" + latitude + "&" +
"longitude=" + longitude;
HttpConnection connection = (HttpConnection) Connector.open(serviceURI, Connector.READ, true);
InputStream inputStream = connection.openInputStream();
StringBuffer inputBuffer = new StringBuffer();
int inputChar;
while((inputChar = inputStream.read()) != -1)
{
inputBuffer.append((char) inputChar);
}
inputStream.close();
connection.close();
(3) Present the distance to the user
Form form = new Form("HaversineClient");
form.append(inputBuffer.toString() + " meters");
Display display = Display.getDisplay(this);
display.setCurrent(form);
Standing on Station Utrecht Centraal, how far away from the Oudegracht?
If we were to execute the client application at Station Utrecht Central, then it will appear on the screen that the calculated distance to the Oudegracht is, rounded, 746 meters. For comparison, below a screenshot of Google Earth that calculates the same distance between the two locations.
