2024-01-25

GPS Logger project

My GPS logger project is pretty much over at last. All working so well, and several customers happy!

Do buy them (here) but they are not live trackers - they are loggers.

I have had an annoying set of issues.

  • power control FET for GPS/SD picked wrong, way too low power.
  • not spotting I had inputs on non RTC GPIOs on the ESP32S3.
  • not realising the STAT signal from the charger is only charging so stops when charged.
  • having a cap on GPS so it could brownout the power when connected.

Even so, all sorted, and quickly, and the whole project sorted from start to finish in a couple of weeks.

I'd like to thank Neil for inspiring the whole project - his blog: RevK's privacy-friendly GPS logger.

2024-01-22

Finding a postcode

My GPS logger is going well (available here) and it logs journeys when back on home WiFi.

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.

2024-01-13

Distance of point to line in four dimensions (or more)

Why?

I'm writing the blog because searching has not helped me on this. Why do I need to know? well the answer is I am applying a Ramer–Douglas–Peucker algorithm to GPS tracking data.

You can look it up, but it is pretty simple to explain. Imagine you have a set of points starting from A and going to B - in my case it is GPS log data, so points on a map, every second, so lots of points. You want to reduce how many points you have without losing significant information.

Ideally all the intermediate points are on a straight line A to B, and can all be removed leaving just A and B. I practice you allow a tolerance, an allowable deviation from the line. If all of the intermediate points are within that tolerance you can delete them all. If not, you find the most deviant point, call it C. C is effectively a corner point. You apply the algorithm on A to C and C to B recursively.

In the end you have a set of points, which could just be A and B, or A, C, and B, or more. If you join the dots with straight lines you can be sure all of the removed points lay within your tolerance of that line, and so be sure any detail, that is more than the tolerance allowed, has not been missed.

I use this years ago on GPS data.

Before
After

Point to line

The crux of the algorithm is working our the deviation from the line, what wikipedia helpfully just refers to as perpendicularDistance().

Two dimensions

In two dimensions this is simple, and searching finds an algorithm. I used this on latitude and longitude. But this causes problems.

  • Latitude and longitude are not a flat plane. This is not likely to be a real issue unless tracking a plane (pun intended) or a ship over a long distance.
  • Latitude and longitude are in degrees not metres, so working out your distance is not easy. A degree North is not the same distance as a degree West and changes depending one where you are. You need trigonometry to compensate and convert to distance units.

Three dimensions

Of course, we also have altitude, and so seems sensible to include that - why not. Algorithms for a point to a line in 3D are also easy to find, but there seem to be several different approaches. At least altitude is already in metres.

However, the GPS can provide not just lat/lon/alt, but also ECEF data. This is simple Cartesian X/Y/Z co-ordinates from centre of the Earth. This avoids any need to adjust from degrees, and makes it simple.

Four dimensions

I have to push it one step further, don't I? If you travel in a straight line, but stop for a while, you would remove all points. By including time as a 4th dimension we create a corner when speed changes notably or you stop for a while.

It does mean you have to scale time to a distance, but that can be a simple parameter in the algorithm.

However, there is a snag - finding an algorithm for point to line in four dimensions is not simple. The only ones I could find explain it in vector maths - and even with an A in A-level maths, it was a long time ago and I really did not get on with vector maths. Nobody seems to give me a simple algebraic answer which is driving me mad.

Making it simple

So, back to basics, I am interested in three points, and regardless of how many dimensions that is, they can be said to lie on a flat two dimensional plane. This means working out the deviation is a simple matter of considering a triangle.

So I want to find h. To do this I need distances a, b, and c. But that is easy to find as it is simple Pythagoras, regardless of how many dimensions. For two dimensions it is √((Ax-Bx)²+(Ay-By)²). For three dimensions it is √((Ax-Bx)²+(Ay-By)²+(Az-Bz)²), and so on.

Knowing ab, and c I can use Heron's formula to find area...

  • s = ½(a+b+c)
  • 𝔸 = √(s(s-a)(s-b)(s-c))

Then use the formula for area from base and height

  • 𝔸 = ½hb
  • h = 2𝔸/b
  • h = 2√(s(s-a)(s-b)(s-c))/b

So it can be done with any number of dimensions.

Faster

One of the considerations is performance when coding for a microcontroller. They can do integer add/subtract very fast, multiply reasonably fast, division slower, and floating point even slower. As it happens the ESP32 has hardware single precision floating point, which helps.

So can I simplify this?

Thankfully wikipedia helpfully expands Heron's formula to:

  • 𝔸 = ¼√(4a²b²-(a²+b²-c²)²)

Which gives us:

  • h = 2(¼√(4a²b²-(a²+b²-c²)²)/b)
  • h = ½√(4a²b²-(a²+b²-c²)²)/b
  • h² = (4a²b²-(a²+b²-c²)²)/4b²

Working our h² is useful as ultimately I am just comparing this distance so no need to apply a square root. I can square my reference threshold.

Why is this helpful? Well, all of the parameters are a², b², and c². This means that I don't need to use a square root to work out ab, and c in the first place. The whole lot is simple addition, subtraction, multiplication, and just one division.

Turning back

There is another problem with all of the perpendicular distance algorithms, including this one. The all work out a distance of a point to an infinite line which is defined as going through two points.


In this case point C is way off the line A-B, in fact it is c off it, but h is small. If h is within the tolerance  then it would be removed leaving only A-B.

To solve this I can use the fact that if c²-b² is > a² the C must be beyond A and I should use a² as the distance².


Similarly if a²-b² > c² then C is beyond B, meaning I should use c² as the distance².

Fortunately I have a², b², and c² already, so is a simple test.

Of course, what if you have a straight line A-B-C-D and travel A-B-C-B-C-D? No points will be "outside" the A-D range... Well the use of time as a 4th dimension catches that - which means the first case would also have been caught... Even so, this simple test on end points is worth doing I think.

C what I mean...


   inline float dist2 (fix_t * A, fix_t * B)

   {

      float X = x (A) - x (B);

      float Y = y (A) - y (B);

      float Z = z (A) - z (B);

      float T = t (A) - t (B);

      return X * X + Y * Y + Z * Z + T * T;

   }

   float b2 = dist2 (A, B);

   fix_t *m = NULL;

   float best = 0;

   for (fix_t * C = A->next; C && C != B; C = C->next)

   {

      float h2 = 0;

      float a2 = dist2 (A, C);

      if (b2 == 0)

         h2 = a2;               // A/B same, so distance from A

      else

      {

         float c2 = dist2 (B, C);

         if (c2 - b2 >= a2)

            h2 = a2;            // Off end of A

         else if (a2 - b2 >= c2)

            h2 = c2;            // Off end of B

         else

            h2 = (4 * a2 * b2 - (a2 + b2 - c2) * (a2 + b2 - c2)) / (b2 * 4);

      }

      if (m && h2 <= best)

         continue;

      best = h2;

      m = C;

   }

2024-01-12

IBM Model M keyboard

For a very long time my preferred keyboard has been an IBM Model M keyboard. It uses "buckling spring" keys which have good tactile feedback and are clicky and loud...

This has been my preferred keyboard since they really were actual IBM Model M keyboards. These days it is UNICOMP that make them, and as I have moved to Mac as my main machine, and UK Mac keyboard layout.

It works well, I love it.

But it has broken. Some keys get iffy, and this has happened now. It had happened once before, years ago. I assume somehow muck gets in there - but the whole thing is all sealed to a metal plate inside, so not easy to debug or fix. Last time I got a new one.

So, this time, as they have no Mac layout ones, I ordered a PC layout, and sorry, no, I just cannot get used to it. I'd rather have no Z and an iffy S than use a PC layout. Yes, I had to *hit* the Z hard to type that.

As UNICOMP have none of the Mac layout - I am a bit stuck, and, for the first time, in literally decades, looking at another keyboard.

I'll update this post when it arrives. Worrying times when a mad has to change his keyboard. But it may save muting Jitsi when I type.

Updates:

  1. The keys do not map correctly by default on a Mac, notably ±/§ and ~/` reversed. Annoying, but solvable...
  2. The tools to allow remapping using "VIA" app website did not work! It got stuck after connecting to the keyboard, so I fixed the remapping in the OS.
  3. The keys are too sensitive, so being slightly different spacing I keep hitting adjacent keys just enough to register - but I will get used to the spacing. It is quieter.

One Touch Switching

It has been some weeks since One Touch Switching was fully live. TOTSCO say over 100,000 switch orders now, so it is making good progress, ...