De Haversine-formule en de Location API voor Location-Based Services

Geschreven door Jeroen Oosterlaar op 30/05/2010
2 reacties
Categorie: Software engineering

Landmeten in de 16de eeuw Een bepaalde categorie Location-Based Services functioneert op basis van de afstand tussen twee (geografische) punten. Deze twee punten zijn doorgaans de locatie van de gebruiker op een zeker moment (het moment waarop de dienst wordt gebruikt) en de locatie van een Point Of Interest (POI). Er zijn veel toepassingen van dit concept denkbaar, bijvoorbeeld het kunnen opvragen van de dichtsbijzijnde pinautomaat en Location-Based Advertising. In dit artikel demonstreer ik dit concept aan de hand van een eenvoudige opstelling.

De opstelling bestaat uit een J2ME-applicatie (client) die via de Location API de GPS-coördinaten van de huidige locatie verstuurt over het internet naar een PHP-script (service). Dit script berekent met behulp van de Haversine-formule de afstand tot de Oudegracht in Utrecht (de POI) en retourneert deze naar de J2ME-applicatie. Ter illustratie is Station Utrecht Centraal de locatie waarop de gebruiker zich bevindt.

De volgende afbeelding laat een kaart zien met daarop gemarkeerd de Oudegracht in Utrecht als de POI en de locatie van de gebruiker (Station Utrecht Centraal).

Kaart met daarop gemarkeerd de locatie van de POI en de gebruiker

De lijn die de twee punten verbindt, is de afstand tussen de gebruiker en de POI die we willen berekenen. Het is wel goed om te weten dat de Haversine-formule de afstand hemelsbreed berekent. Er wordt geen rekening gehouden met tussenliggende obstakels zoals hoogteverschillen in het aardoppervlak en de verkeersinfrastructuur. De feitelijke afstand die men moet afleggen om de POI te bereiken kan (en zal in de meeste gevallen) dus afwijken van de berekende afstand. In hoeverre dat acceptabel is, hangt af van de toepassing.

De Haversine-formule

Wanneer de wereld zou bestaan uit slechts twee ruimtelijke dimensies (zoals de kaart in de bovenstaande afbeelding), dan zouden we voor de berekening van de afstand kunnen volstaan met basale goniometrie. Maar aangezien de Aarde een driedimensionale bol is, moet rekening worden gehouden met de curve van het aardoppervlak. De Haversine-formule biedt een oplossing voor dit probleem.

R = 637100 (the Earth's radius in meters)
Δlatitude = latitude_poi - latitude_user
Δlongitude = longitude_poi - longitude_user
a = sin²(Δlatitude / 2) +
    cos(latitude_user) ∙ cos(latitude_poi) ∙ sin²(Δlongitude / 2)
c = 2 ∙ atan2(√a, √(1 - a))
distance = R ∙ c

De eenheid van de resulterende afstand is dezelfde als de eenheid waarin op de eerste regel de straal van de Aarde (R) is uitgedrukt. In dit geval is de eenheid in meters. De Haversine-formule kan nu worden geïmplementeerd in de software.

De service en de implementatie van de Haversine-formule

De service is een PHP-script dat twee GET-parameters verwacht: de breedte- en lengtegraad van de gebruiker. Zie de volgende 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
}
?>

Er worden twee instanties aangemaakt van de klasse POI, één voor de gebruiker (de gebruiker is in deze context immers ook een POI) en één voor de Oudegracht. De breedte- en lengtegraad worden aan de constructor van de klasse meegegeven. Vervolgens wordt de afstand in meters tussen beide punten (het resultaat van de methode getDistanceInMetersTo()) geretourneerd naar de client.

De implementatie van de klasse POI is in de listings hieronder weergegeven.

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
    }
}

Aangezien de berekening uitsluitend werkt met radialen, worden de breedte- en lengtegraad in de constructor direct naar die eenheid geconverteerd. De methode getDistanceInMetersTo() implementeert de Haversine-formule. Zie de listing hieronder.

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;
}

De J2ME-clientapplicatie

Voor het J2ME-platform is de zogenaamde Location API (JSR 179) beschikbaar. Deze API biedt een abstracte interface naar een hulpbron - zoals een GPS-ontvanger - waaruit de huidige (geografische) locatie kan worden opgevraagd. (De Nokia N85 is een voorbeeld van een mobiele telefoon die via de Location API toegang biedt tot de ingebouwde GPS-ontvanger.) De clientapplicatie gebruikt de Location API en stuurt de coördinaten als GET-parameters van een HTTP-request naar de service.

Hieronder is de listing van de applicatie weergegeven.

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)
    {
    }
}

De applicatie bestaat uit een enkele MIDlet en alles gebeurt in de methode startApp(). Om het overzicht te bewaren heb ik de code van deze methode vervangen door commentaarregels en hieronder respectievelijk in aparte blokken opgedeeld.

(1) De GPS-coördinaten bepalen via de 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) De coördinaten versturen naar de service en de berekende afstand ontvangen

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) De afstand tonen aan de gebruiker

Form form = new Form("HaversineClient");
form.append(inputBuffer.toString() + " meters");

Display display = Display.getDisplay(this);
display.setCurrent(form);

We staan op Station Utrecht Centraal, hoe ver verwijderd van de Oudegracht?

Wanneer we de applicatie nu zouden uitvoeren op Station Utrecht Centraal, dan zal op het scherm verschijnen dat de berekende afstand tot de Oudegracht afgerond 746 meter is. Ter vergelijking hieronder een screenshot van Google Earth die tussen de twee punten eenzelfde afstand berekent.

Screenshot van Google Earth

Reacties

Geschreven door Alan W. op 20/06/2010 om 21:23

Hi Jeroen, thanks for sharing this interesting and helpful article! :)

Geschreven door Mark Monster op 21/07/2010 om 11:41

Nice article Jeroen.

Although I'm not interested in PHP and JavaME it's still very interesting to read these calculation methods.

What's the main reason to implement the actual calculation on the server? I expect that the amount of power required for networking is higher than the amount of power required for calculation.

Reageren

Met behulp van het onderstaande formulier kun je een reactie plaatsen op het artikel. De velden die gemarkeerd zijn met een * zijn verplicht

Jeroen Oosterlaar