Map image

In my last post I found some great algorithms and libraries for calculating distances between two points.  I used it to update some archaic data listing adjacent postcodes.

With these algorithms and some online services that are now available it should be quite simple to create your own, “find my nearest store”, type service in your own websites/apps.  So here is how I plan to do it.

For ease of reference I’m going to talk about finding people instead of stores and it explores more avenues than a fixed number of stores and searching through large datasets for geo data.  Also SQL Server 2005 can do spatial searches and here is the article on doing it, it is probably really fast, but I didn’t have time to get my head around some of the complex topics discussed here, and sometimes its just fun to code it.

The system in question stores members details. They store, amongst other data, their address, postcode,zip code and work place.  Then they search the system for other members nearby who they can share a care journey with to a common destination, work.

Now trying to mathematically find the distance between 12 Arcadia Ave, Coventry and 26 The Oaks, Little Bottom isn’t possible.  So all this hinges on being able to get a mathematical representation of their location, this is the WGS84 co-ordinate system, decimal lat/long to you and me.

Imagine that you capture the address, you need to get hold of the lat/long info.  Thanks to the many API’s out their for mapping this is close at hand *. 

Yahoo have a Geocoding API, it is free to use provided you meet the terms and conditions one of those being < 5000 hits per day, This application discussed here, does not meet the T&C’s for using this API as you are not allowed to store the geodata returned.  So its a good job this app is not real.

Once you sign up you get an API and can make a call like this, which returns this data.

<?xml version=”1.0″?>
<ResultSet xmlns:xsi=”http://www.w3.org/2001/XMLSchema-instance” xmlns=”urn:yahoo:maps” xsi:schemaLocation=”urn:yahoo:maps http://api.local.yahoo.com/MapsService/V1/GeocodeResponse.xsd”>
  <Result precision=”address” warning=”The exact location could not be found, here is the closest match: 701 1st Ave, Sunnyvale, CA 94089″>
    <Latitude>37.416402</Latitude>
    <Longitude>-122.025078</Longitude>
    <Address>701 1st Ave</Address>
    <City>Sunnyvale</City>
    <State>CA</State>
    <Zip>94089-1019</Zip>
    <Country>US</Country>
  </Result>
</ResultSet>

The call can also be just http://local.yahooapis.com/MapsService/V1/geocode?appid=YahooDemo&location=cv3%208lg , Notice that the parameter location only has a postcode, and yet it finds the Lat Long we require.

Sorry, but I found this just so cool.

Still all we want is the Lat/Long.  Store this against that user in the database, and the same for every other user, while your at it store the common end points and their lat/longs, that might come in handy later too.

Now we have a database full of geo data.  So how do we calculate nearest neighbours.  In our example our intrepid car sharer needs to find people near him lets say he selected within a 2 mile radius.

We need to create a SQL query that quickly filters out all the other people that are no where near him or not going to the same destination.  Calculating a spatial radius on what could be thousands of records, whilst possible in CLR/SQL 2005, is not recommended.  Instead we are going to create a bounding box for that location.  Using the start point as the centre of a square we can get top/bottom/left/right extremities co-ordinate set and use those as a simple less-than/greater-than test against the stored co-ordinates of other users.

e.g.

image

The bounding box is calculated using the libraries I mentioned in the previous post.

The GeoditicCalculator Class has a method called CalculateEndingGlobalCoordinates.  Pass it a start point, distance and a bearing and it calculates the new end point.  To create our box we call this four times for the four points of the compass, angles 0,90,180,270.  With each call we get points at the end of the cross-hairs as seen in the diagram.  The res-points or box corners are simply the extremities for each axis.

I don’t live here by the way and don’t know anyone who does.

Here is some code

// instantiate the calculator
GeodeticCalculator geoCalc = new GeodeticCalculator();
double leftPoint, topPoint, bottomPoint, rightPoint;

// select a reference elllipsoid
Ellipsoid reference = Ellipsoid.WGS84;

// set start coordinates
GlobalCoordinates startPoint;
startPoint = new GlobalCoordinates(
    new Angle(52.63312138), new Angle(-1.569828698)  //Made this up
);

// set the direction and distance
Angle startBearing = new Angle(0);
double distance = (4.0 * 1.609344)  * 1000;  //In Metres   (4 miles)

// find the destination
Angle endBearing;
GlobalCoordinates dest = geoCalc.CalculateEndingGlobalCoordinates(reference, startPoint, startBearing, distance, out endBearing);

topPoint = dest.Latitude.Degrees;

startBearing = new Angle(90);
dest = geoCalc.CalculateEndingGlobalCoordinates(reference, startPoint, startBearing, distance, out endBearing);
rightPoint = dest.Longitude.Degrees;

startBearing = new Angle(180);
dest = geoCalc.CalculateEndingGlobalCoordinates(reference, startPoint, startBearing, distance, out endBearing);
bottomPoint = dest.Latitude.Degrees;

startBearing = new Angle(270);
dest = geoCalc.CalculateEndingGlobalCoordinates(reference, startPoint, startBearing, distance, out endBearing);
leftPoint = dest.Longitude.Degrees;

Those variables can now be used in the SQL statement

where sharer.lat > bottomPoint & sharer.lat < topPoint
and sharer.long> leftPoint and sharer.long<rightPoint
and share.dest = destId

Now I know your thinking, but I live in Alaska and I boat share with a chap in Russia, well tough! I’ll let you figure out problems with the cross-over of the edges of the map !  I live in the UK and won’t have that problem !

This SQL where clause should pull out all those other members within the bounding box, but we are after the radius, well the thing to do here is to do a distance calculation between the two points for each user and reject those outside the distance.

Again taken directly from the example code

// instantiate the calculator
GeodeticCalculator geoCalc = new GeodeticCalculator();

// select a reference elllipsoid
Ellipsoid reference = Ellipsoid.WGS84;

// set Lincoln Memorial coordinates
GlobalCoordinates lincolnMemorial;
lincolnMemorial = new GlobalCoordinates(
    new Angle(38.88922), new Angle(-77.04978)
);

// set Eiffel Tower coordinates
GlobalCoordinates eiffelTower;
eiffelTower = new GlobalCoordinates(
    new Angle(48.85889), new Angle(2.29583)
);

// calculate the geodetic curve
GeodeticCurve geoCurve = geoCalc.CalculateGeodeticCurve(reference, lincolnMemorial, eiffelTower);
double ellipseKilometers = geoCurve.EllipsoidalDistance / 1000.0;
double ellipseMiles = ellipseKilometers * 0.621371192;

Putting this code in a function and get it to return miles/km depending on your preference, I use miles, I use metres for height and Kg’s and Litres for other stuff but I can’t shake miles or stones/lbs.

Those that pass the test are the “nearest neighbours”.  Now you can get flash and plot those people on a google/live/yahoo map in your application if you feel like.

Taking it further

In this particular application we are aiming for an endpoint and lets face it the car sharer in question when travelling south-south west doesn’t want to go and pick up someone 4 miles to the north. What we want to do is restrict our search to those 10 miles away on the same bearing, 4 miles away on a similar bearing, 1 mile away in the wrong direction.

By doing the bounding box filter, then comparing each person returned distance and bearing it should be possible to do filters like this.  I haven’t tried this yet, I haven’t made this app yet just got code fragments of most of the elements involved.  This bit I’m guessing at.

Google’s map API’s provides driving directions with each step of the route and its position by using driving directions we could calculate sharers 1 mile off key route points expanding the nearest neighbour scope but very specifically.  Using this technique I think that I could write the best car sharing algorithm going. 😉

 

*After a lot of digging I’m finding that geocoding, converting an address to a lat long, is a pain in the backside.  Yahoo’s T&C are too restrictive for this purpose, MS Live maps is only for displaying the maps (you could cheat and hide the div!),  Google’s, whilst much better T&C’s was failing constantly due to licensing issues with PAF data  (post office address file).    By not using the postcode and just the address I did get a response from Google.  Also different bits of Google maps have different data and display differing results.  However having done more investigation the Google API seems the best with the most features and best T&C with options to commercially license.

** Update: MS Mappoint WebService is lovely, although a pay for service.  It integrated much better into my server code (of course) than trying to use Live Services, it appeared to be more accurate (in my limited testing ) than Google’s, and didn’t have T&C problems like yahoo.

Advertisements