One of the requirements that someone requested was to list postcodes visited. I think it was a district nurse, and they need this for expense claims.
So, not a hard task, surely, making it find postcode where you are...
Postcodes are odd shapes
Sadly postcodes are not simple, and odd shapes, but the best I could easily do is find nearest postcode based on the centre for each postcode, which is published free by Ordnance Survey.
Notably the Dutch government does the same but with a bounding box which may help identify when there is ambiguity.
The challenge is that this is a small micro controller. I cannot just "install mysql". I need a way to look up postcodes and finding the nearest. I cannot sensibly scan 1.7 million UK postcodes each time I want to log a postcode.
The "trick" is simple, make a grid. I picked 1km squares on the OSGB E/N grid. So not quite 1km but close enough. More on that later. That meant I could make a grid for the whole UK, and for each grid square I can make a list of possible postcodes with there centre.
That was simple enough, well, except...
Converting lat/lon to OSGB
First issue is, on device, converting GPS lat/lon to E/N OSGB. There are simple algorithms for this, I have seen them, but some are way off, and ultimately the "official" way to do it is make a guess and check a huge look up table of surveyed points (I think each 10km).
I did not want to do this on device, so my solution is convert the postcode list to lat/lon. This runs on linux and can use the official look up table, but gives me a postcode database which uses lat/lon.
Searching one cell
The next step was a simplification for search. I make each grid square (now based on lat/lon) have a list of postcodes with centre location to find the closest.
The problem is that, at the edge of a square, the closest may be in the next square. So I scan the edges of the squares, binary dividing to find all "near" postcodes for all points along it, whether in the target square or not. I then have all that are in the target square.
This means for each square I have a list of all postcodes that could be the closest postcode for any point in the square. This means some duplication from square to square but makes the lookup simple.
The whole lots ends up in one file. Look up the grid to find the list of postcodes, and scan the list for the closest. Simple.