@northeastraces Follow me at http://twitter.com/northeastraces
This photo of the start of the 2004 Kirkby Malzeard 10K was taken by Eric Nutter

KML files for postcode areas

Details (e.g., entry forms and results) of running races (e.g., 10K, 10M and half marathon), both road races and multi-terrain, near North East England: Northumberland, Tyne and Wear, County Durham, Yorkshire, Cumbria, ... Generated: Thu 03 Jan at 11:30:05 GMT

Wikipedia says that "For the purposes of directing mail, the United Kingdom is divided by Royal Mail into postcode areas. The postcode area is the largest geographical unit used and forms the initial characters of the alphanumeric UK postcode.". For example, the postcode area for the postcode "DH1 3LE" is "DH".

This web page provides KML files and Google Maps giving rough outlines of each of the 120 postcode areas that are in England, Wales and Scotland. Use the following links to see:

These KML files use postcode data provided by Ordnance Survey and Royal Mail.
©Crown copyright and database right 2010 and ©Royal Mail copyright and database right 2010.
The postcode data that they provide gives the OS coordinates of a point within each postcode.

Using the "quickhull" algorithm to produce the outlines

So for each postcode area, I produced a list of these points, one for each postcode that is in the postcode area. A polygon providing a rough outline of a postcode area was then produced by using the quickhull algorithm to wrap a convex hull around all these points.
I'm using the code at http://westhoffswelt.de/blog/0040_quickhull_introduction_and_php_implementation.html.
A KML file for each postcode area was then produced from the polygon.

The resulting polygons are in http://www.northeastraces.com/runningstatic/pcas/kmls/overlaps.kml which is shown on this overlaps OS map.

Some statistics: the 120 polygons each contain between 7 and 31 vertices, and they have a total of 2123 vertices.

Removing the overlaps

Many of these polygons overlap. This means a polygon has at least one vertex from a neighbouring polygon inside its area.
I call such a vertex an insider. If you like the polygon is taking a shortcut across the territory of its neighbour.
In some ways it would be better to alter the polygon so that the offending side of the polygon were bent to go round the insider.

The problem is widespread: the 120 polygons contain 1488 insiders.

Here is my improvement algorithm that alters each polygon so that it goes round the insiders:

   for each postcode area
      let "current polygon" be the polygon of this postcode area
      for each postcode area other than the current one
         for each vertex of the polygon of this postcode area
            if the vertex is inside the current polygon, 
            then add it to a set of "insiders"
      while the set is not empty
         choose the insider that causes fewer points to be insiders if
                  the chosen insider were added to the current polygon
         for each side of the current polygon
            determine the distance of this insider from the side
         let "grafting point" be the point at the start of the side that
             has the smallest distance
         add the point of this insider to the polygon after the grafting point
         remove this insider from the set of insiders
         remove any points that are no longer insiders from the set of insiders

I'm using the code at http://www.assemblysys.com/dataServices/php_pointinpolygon.php to determine whether a point is inside a polygon. And I'm using the code at http://coding.pressbin.com/65/PHP-Find-shortest-distance-from-point-to-line-segment to determine the distance of a point from a line.

The resulting polygons are in http://www.northeastraces.com/runningstatic/pcas/kmls/coincides.kml which is shown on this coincides OS map.

Some more statistics: the 120 polygons now contain between 7 and 50 vertices, and they have a total of 3176 vertices.

Adding a perturbation

Modifying a polygon to go round the insiders of a neighbouring polygon means that the sides of the two polygons are in the same place. Because the sides are coincident, the two colours of these sides don't both show in Google Maps or Google Earth.

So rather than just adding the point of the insider to the polygon I've modified the code so that instead
it adds to the polygon a point that is near to the insider. I call this a perturbation.
I choose a point that is 0.5 kilometres away from the insider in the direction of the average position of the vertices of the polygon.

The resulting polygons are in http://www.northeastraces.com/runningstatic/pcas/kmls/perturbs.kml which is shown on this perturbs OS map.

Some more statistics: the 120 polygons now contain between 7 and 43 vertices, and they have a total of 2969 vertices.

Dealing with anomalies: weird postcode data

There are some odd things happening (no matter whether you are looking at the coincides map or the perturbs map). I don't know whether each of these is caused by the improvement algorithm or whether it's because of an anomaly in the postcode data.

I've looked at one of these: this is where the lines for the EH and TD postcode areas are still overlapping. It's roughly in the area of 55.95N, 2.5W. It is caused by there being three postcodes (TD135WD, TD139AA and TD139AB) that have coordinates 367956,678773 which is in Dunbar. However, Dunbar and the surrounding area is in the EH postcode area. Indeed, the postcode data has five EH postcodes (EH403WW, EH421AA, EH421WF, EH421WH and EH421WS) that also have the coordinates 367956,678773.

I looked at the postcode data and detected 48 locations which are shared by postcodes of more than one postcode area. Here is a table of the troublesome locations. The table gives one example of a postcode from the two postcode areas but there may be more than one in each postcode area. For example, 393846,398866 is associated with 74 postcodes in the OL postcode area and 19 in the SK postcode area.

"EH421WS" "TD135WD" 367956 678773
"OL7 9WX" "SK151WB" 393846 398866
"DH981EE" "NE826XX" 424760 560064
"HA2 8BA" "UB5 4EP" 513414 185185
"HA1 3PN" "UB6 0HU" 515454 185843
"NW8 8BD" "W2  1BG" 526948 181865
"NW1 5WX" "W2  1DU" 527147 181671
"NW1 3AR" "W1T 6AE" 528982 182176
"SW1A1RA" "W1J 9EA" 529120 180348
"NW1 3AQ" "W1T 5PE" 529223 182260
"SW1Y6DS" "W1J 9ET" 529348 180489
"W1T 7NP" "WC1E6JQ" 529405 182087
"SW1Y6AD" "W1J 9EZ" 529437 180530
"SW1Y6WW" "W1J 9HB" 529456 180539
"W1T 7PJ" "WC1E7HJ" 529551 181921
"W1T 6WD" "WC1X8WQ" 529554 181451
        
"SW1Y4XA" "W1J 9HR" 529612 180625
"W1T 7PY" "WC1E7EB" 529618 181756
"W1T 7PZ" "WC1E7DF" 529632 181738
"W1T 7QN" "WC1B3HD" 529696 181637
"SW1Y4SP" "W1D 7AG" 529707 180659
"W1D 6JW" "WC2H7BF" 529751 180822
"SW1Y4EP" "WC2H7DH" 529764 180643
"NW1 2BH" "WC1H0AF" 529766 182542
"W1T 7RE" "WC1B3AU" 529778 181515
"W1T 7RG" "WC1B3GH" 529815 181490
"W1T 7LA" "WC1B3ND" 529819 181451
"W1T 7RQ" "WC1B3BS" 529831 181439
"W1T 7RJ" "WC1A1HL" 529856 181403
"W1T 7AQ" "WC1A1HP" 529872 181440
"NW1 2AU" "WC1H9AA" 529884 182639
"NW1 2AQ" "WC1H9AJ" 529946 182674
        
"NW1 2QE" "WC1H9BL" 530080 182741
"SW1A2DR" "WC2N5BY" 530085 180358
"NW1 2RY" "WC1H8AA" 530296 182882
"SW1A2HR" "WC2N5DJ" 530409 180244
"EC509TY" "WC1X0DG" 531070 182310
"EC1R4SP" "WC1X0AS" 531112 182248
"EC4A1YH" "WC2A1AL" 531115 181482
"EC4A1HL" "WC2A1EL" 531131 181400
"EC1N7WS" "WC1X8HN" 531135 181691
"EC4A2NJ" "WC2A1LF" 531180 181148
"SE5 9HJ" "SW9 7TF" 531606 176306
"E2  8AW" "N1  5LZ" 533354 183413
"E1  7BH" "EC3A7AH" 533479 181372
"E8  2BA" "N1  4BJ" 533494 184791
"E1  7AA" "EC3A7DT" 533608 181326
"E6  9HY" "N6  5SP" 542854 182750

I’ve decided that these locations are too troublesome to deal with. However, there is enough postcode data about a postcode area without having to include these locations. So I’ve chosen to remove postcodes with these locations from the postcode data before it builds the polygons.

Dealing with anomalies: the resulting polygons

The resulting polygons are in http://www.northeastraces.com/runningstatic/pcas/kmls/cleans.kml which is shown on this cleans OS map.

Final statistics: the 120 polygons now contain between 7 and 43 vertices, and they have a total of 2981 vertices.

Credits

The maps mentioned on this web page are provided by OS OpenSpace and this is © Crown copyright and database right Ordnance Survey The use of these maps is subject to these Terms of Use.