GPS resolution planning & Floating Point Avoidance

Avoiding Floats

So, the ARM Cortex M3 processor does not include an FPU.  Any floating point operations would require emulation libraries to be linked in and used.  This increases the size of the code and reduces performance.  Thus, I'm trying to avoid floating point math in the tracker.

GPS Strings

The GPS strings include latitude and longitude which are presumed to be floating point.

$GPGGA,204403.00,4226.59508,N,07628.88487,W,1,06,2.83,283.3,M,-34.5,M,,*66

These numbers need to be converted to decimal degrees for use in grid square math, and also for the math used by the geofencing code.  They have a fair amount of precision, but the question is "How much do we need?"

Grid Square Precision

A 6-character grid square has a precision of about 3x4 miles.   Each degree of latitude and longitude is about 69 miles.  So, if we used 1/10th of a degree resolution, we would have a resolution of about 7 miles.  That's not sufficient.  However, if we use 1/100th of a degree, we would then have a resolution of about 0.69 miles.  That's more than adequate for a 6 character grid square.

Geofencing precision

The generally available geofencing polygons are composed of relatively few points enclosing the countries on the map.  They're not drawn with a great deal of precision near the borders.  A resolution of 0.69 miles should be sufficient to fence off areas in which transmission is prohibited.   So, 1/100th of a degree would work fine here, as well.

Assuring 1/100 degree is safe for int32_t

The latitude and longitude numbers, when in decimal degree will range from -180.00 to 180.00.  By shifting the decimal point two places, we can represent these as integer values from -18000 to 18000.

Grid square calculations begin with the latitude and longitude and do divisions and modulo operations to build the grid square representation. Those won't present any difficulties for 32 bit integer math.

The Geofencing logic is more complicated.  The heart of the "PointInPoly" routine, used by the geofencing logic, looks like this:

if ( ((verty[i]>testy) != (verty[j]>testy)) &&
    (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
         c = !c;

I want to remove the division.  There's a risk that the denominator may be negative.  If it is, it will switch the case of the test from "Less Than" to "Greater Than".  Modifying the code as I implement this algebra yields this:

if  ((verty[i]>testy) != (verty[j]>testy)) {
   denominator =  verty[j]-verty[i];
   if (denominator > 0) {
      if ( (testx - vertx[i]) * denominator < (testy-verty[i]) ) {
         c = !c;
      }
   } else if ( (testx - vertx[i]) * denominator > (testy-verty[i]) ) {
      c = !c;
   }
}

Denominator worst case:  18000 - -18000 == 36000

So, the worst case math is this:

(testx - vertx[i]) * denominator

IE:  

(( 18000 --18000) * 36000) == 36000 * 36000 = 1,296,000,000

The max value of a signed 32 bit integer is:

2^^31 == 2,147,483,647

So, the worst case scanario in the PointInPoly routine, assuming we use integers from -18,000 to 18,000, fits comfortably inside a 32 bit signed number.

Conclusion

I'll be using Latitude and Longitude to the 1/100th of a degree. I'll represent the values as signed 32 bit integers by multiplying the values by 100 and rounding.  By doing so, I can completely avoid using floating point math and/or 64 bit numbers.  This should keep the tracker code lean and mean.