Image:The Earth seen from Apollo 17.jpgA long time ago, before Google maps and live maps there was street map but no API, I wrote an car share application.  It was done in conjunction with a 3rd party who hardware bit. It logged data and awarded points for environmentally friendly travel.  That data fed into the membership system via web services.

The web based membership system interfaced with the identity system and people registered with this system and stored they type of travel they used and there outbound UK postcode.

We needed a way in this system for people to find other car sharers, so as public geodata was in its infancy and very expensive, it was done by adjacent postcodes.  A SQL table stored the adjacent postcodes for another postcode

e.g.

The full post code might be CV5 8FG  (I made this up)

I would store

CV5   CV5

CV5    CV6

CV6    CV5

CV6    CV6

And so on.

As the system grew and more sites came online, the search capability did not service the new sites for finding a car sharer as no one took responsibility for adding new postcodes and budget of course and ignorance of what needed to be done.

Yesterday I figured out that there must be some data somewhere that can help.

Well that proves hard as I have no budget and no time.

Unlike the United States our data is not free, you have the great USGS who recognise as they are funded by the public the data is in the public domain.  In the UK we have Ordnance Survey, a great organisation, but like all UK organisations, private and public alike they charge for pretty much everything, so us UK tax payers pay twice for all our data.  Likewise Postcode information was created by a public organisation, the Post Office, and whilst private now, does and always has charged for Postcode information.

I scoured the interweb for some information and eventually found a great little site, www.nearby.org.uk.  On this site he has a webservice for postcodes and location information in WGS84 format.  This is great, but even better for my purposes was the raw data available as a download !

This file holds UK sector postcode (partial postcode (more refined than mine)) information and a centre point of the Latitude and Longitude for that postcode sector.  I signed up and downloaded it, great, now what !?!

From this information it should be possible to work out the distances between any two postcode sectors by using the location information.  Well have you ever tried it !

There are a number of ways of doing it and you do it by using the Lat/Long data,

A very rough way is that 111km corresponds to very approx 1 degree.  I was not sure of the margin of error here so I did not try and mangle this into an equation.

Spherical Law of Cosines

    d = acos(sin(lat1).sin(lat2)+cos(lat1).cos(lat2).cos(long2?long1)).R

Haversine formula

    R = earth’s radius (mean radius = 6,371km)
    ?lat = lat2? lat1
    ?long = long2? long1
    a = sin²(?lat/2) + cos(lat1).cos(lat2).sin²(?long/2)
    c = 2.atan2(?a, ?(1?a))
    d = R.c

I am no maths guru all of these formulas were found on this site.  Whilst the javascript was there to take I really needed the C# code done for me as its been too long since I did any trig.

There is also another formula which is more accurate than either of the above called the Vincenty formula, a formula much longer than Haversine and more complicated so I’m not including it here.  Now that’s what I want as I want more accuracy as my starting point is not accurate so the more accurate the formula the better.

With not much searching I found a C# library for this algorithm, I cannot thank this chap enough for this and provided free of charge.

With this library I can now easily calculate distance and bearing, but for my immediate purpose I ignore the bearing.

Firstly I needed a list of all outbound postcodes, so I just created a new table based on the ukpcode list  I did this by creating a sql table for the ukpcodes and another for just outbounds, (it was just easier this way in my head but could have been done dynamically I know).

insert into outbound select left(pcode, length(pcode)-1) as pcode.

With this list I searched the ukpcode file for matching partials e.g.

CV4 matched CV4 1, CV4 2, CV4 3

For each one of these matches I got the co-ordinates and did the distance calc against every other entry in the ukpcode file,  this ensured that for CV4 I captured the adjacent postcode for any sector.  Any postcode pair that was in a distance of five miles was stored and trimmed to outbound only.

Once complete all duplicates were removed (as we were comparing sectors, but require the less accurate outbound only).

And there it is a list of adjacent outbound postcode within 5 miles.

Not ideal, not as good as doing it properly by storing members lat/long and distance calcing between members.  But more on how to do that in another post.

 

Advertisements