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.
Microcontroller
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.
In theory (and obviously it wouldn't be suitable for a microcontroller) - could you use the Ordnance Survey's OS Open UPRN which will give you a "unique property reference number" from a lat/lon (there will be a few to the nearest lat/lon - but should be good enough). Once you have the UPRN that could go into the AddressBase to turn it into a postcode. I don't know how much an AddressBase licence would cost though
ReplyDeleteIf you're dividing the country up into squares, why not go one step further and allocate each square some sort of reference - perhaps a few words to uniquely define each location? What could possibly go wrong?
ReplyDeleteThat sounds like a neat and simple bit of code for a microcontroller.
ReplyDeleteI had considered doing a similar thing, using a Voronoi Diagram ( https://en.wikipedia.org/wiki/Voronoi_diagram ) to estimate the bounding boxes of the postcodes from their centroids and an R-Tree to index them ( https://en.wikipedia.org/wiki/R-tree ).
--
andyjpb
Late reply, somebody has already done this, although due to the calculation expense they were not planning on keeping it updated:
Deletehttps://github.com/mhl/postcodes-mapit
Yeh, finding nearest is basically the Voronoi anyway but with one point per postcode (centre). A tree would involve more lookups in many cases I expect - this is a trade of file size to allow grid squares without too many postcodes, and I can build the file with any size grid needed. The fact that for any grid the set of postcodes to check are then contiguous in the file also helps when files are read in blocks anyway.
ReplyDeleteWhat are you using for the final distance sort of candidates? With cells that fit inside the UK, you could probably get away with one k=cos(lat), then take the min of (k*deltalat)^2 + deltalon^2. (Yes, I'm working on similar code myself.)
ReplyDeletedeltalat^2+(deltalon*k)^2 surely... A cos^2 table per whole degree will suffice I suspect.
ReplyDeleteSQLite ports/runs nicely on an ESP32 and makes life so much easier, implementation-wise, for certain tasks. Embedded has come so far since the 8 bit days :-)
ReplyDeletePatrick