Integer GPS navigation - rosco-pc/propeller-wiki GitHub Wiki
This page will discuss a little bit of GPS navigation, and a possible approach using integers only and cartesian planar projection.
A little bit of background
While not propeller related a little bit of background will help you deciding wheter the approach can suit your needs.
GPS System and Earth models
GPS (global positioning system) is a clever triangulation system that uses satellites. GPS returns latitude-longitude coordinates in a system called WGS84. Earth shape is extremely complex, and every mapping system must approximate the real shape. The most used shape is an ellipsoid, where the poles are on the shorter axis. The parameters of the ellipsoid are varying, and it is a matter of trade off. Maps use projections of the curved shape over a plane. Projections must accept a trade off, because it is not possible to preserve distance, angles and area at the same time. To have an idea of the many solution adopted is possible to go to spatialreference Moreover sea level is dependent on measures based on the gravity. So the real sea level can differ a lot from the ellipsoid zero. Wikipedia geoid shows a blue/red image of the difference between geoid and ellipsoid.
Navigation formulas
In order to calculate navigation data it is possible to use the Aviation Formulary. Another source of formulas is movable type scripts. While it simplifies the earth model is still requires heavy math, so a lighter solution can be used with the Propeller.
Assumptions used in this document
While the earth shape is extremely complex it is possible to heavily simplify and still get very good navigation data.
- Earth is a sphere
- 1/60th of degree on latitude (N/S coordinate) equals to 1 nautical mile
- We can accept a small error in the calculation
- We will stay away from the poles (in case an ad hoc planar projection can be used for near pole navigation)
- The next way point will be not too far (up to few hundred miles could be ok)
The planar projection
With planar projection the points on the sphere are projected on a plane tangent to the earth Moreover:
- 1 Prime difference (1/60th of degree) in latitude is one nautical mile (1nm)
- 1 Prime difference (1/60th of degree) in longitude is 1nm*cos(avg_latitude), where avg_latitude is the average latitude
- The latitude projects to a vertical cartesian axis
- The longitude projects to a horizontal cartesian axis So we moved from a spherical system to a planar, cartesian system. Calculations are much easier and requires less math. On the other hand the model introduces errors and approximations. Let's try to quantify the error with respect to the results obtained from the aviation formulary. We'll compare the results of our calculations with the distance between two points calculated with the great circle (shortest path, variable heading) and rhumb line (constant heading, in general longer path). | Point1-lat [degrees] | Point1-long [degrees] | Point2-lat [degrees] | Point2-long [degrees] | Dist (great circle) | Dist (rhumb) | Heading (rhumb) | Dist (cartesian) | Heading (cartesian) | Gerat Circle Distance Error [%] | Rhumb Heading error[°] | |----|----|----|----|----|----|----|----|----|----|----| | 45.5 | 10.5 | 45.51 | 10.51 | 0.7327 | 0.7327 | 35.02 | 0.7327 | 35.03 | 0.0029 | 0.0024 | | 45.5 | 10.5 | 45.51 | 10.5 | 0.6000 | 0.6000 | | 0.6000 | | | | | 45.5 | 10.5 | 45.5 | 10.51 | 0.4206 | 0.4206 | | 0.4206 | | | | | 45.5 | 10.5 | 45.6 | 10.6 | 7.3249 | 7.3249 | 35.00 | 7.3271 | 35.03 | 0.0293 | 0.024 | | 45.5 | 10.5 | 45.6 | 10.5 | 6.0000 | 6.0000 | | 6.0000 | | | | | 45.5 | 10.5 | 45.5 | 10.6 | 4.2055 | 4.2055 | | 4.2055 | | | | | 45.5 | 10.5 | 46.0 | 11.0 | 36.5815 | 36.5816 | 34.91 | 36.6353 | 35.03 | 0.1469 | 0.12 | | 45.5 | 10.5 | 46.0 | 10.5 | 30.0000 | 30.0000 | | 30.0000 | | | | | 45.5 | 10.5 | 46.0 | 11.0 | 36.5815 | 36.5816 | 34.91 | 36.6353 | 35.03 | 0.1469 | 0.12 | | 40.0 | 10.0 | 50.0 | 15.0 | 636.0251 | 636.1264 | 19.40 | 642.5062 | 20.96 | 1.0031 | 1.56 |
So for short distances the errors are negligible. Near the poles the errors are bigger, nonetheless the errors are still small for distances up to few tens of nautical miles between waypoints.
Formulas
If you think this is your case let's move closer to the propeller, and try to use integers only. The propeller is a 32 bit processor, so a variable can be 32 bit, or 4 bytes, or a long. A typical signed long in the propeller ranges between -2^32/2 and (2^32)/2-1, or -2,147,483,648 to 2,147,483,647. The range we expect to handle in our system is -180 to 180 degrees (for longitude). If we move to prime the range is -10,800 to +10,800. So the idea is to add fraction of prime resolution as long as the propeller can hold. We can arrive up to -1,800,000,000 to 1,800,000,000, which means we can get as fine as hudreths of tousanths of prime, or if you prefer 1/100000th of a nautical mile, which is less than a inch or less than 2 centimeters. For example, if we have coordinates from GPS: 4512.3456 N (45° 12.3456' latitude) 01012.3456 E (10° 12.3456' longitude) We will convert the this way: integer latitude = (45*60+12.3456)100000 = 271,234,560 integer longitude = (1060+12.3456)*100000 = 61,234,560 If the coordinates are S and W the sign will be negative.
Range limits:
The max longitude is 180° -> 1,080,000,000 less than the range limit of the long. The problem is when calculating a difference in latitude. While the max difference is 180°, if we have two points at 179°E and 179°W, we get the following coordinates as integers: long1 = 179°W = -1,074,000,000 long2 = 179°E = 1,074,000,000
delta_longitude = long2 - long1 = 1,074,000,000 + 1,074,000,000 = 2,148,000,000 > max long range!!
Note that if delta_longitude > 1,080,000,000 (180°) then delta_longitude = sign(-delta_longitude)*(2,160,000,000 - |delta_longitude|) where 2,160,000,000 is 360°.
In our case delta_longitude = -12,000,000 which is within the range. A possible workaround is to divide by two the coordinates, calculate the difference, and then multiply times 2. In case of the GPS strings used for example we have plenty of resolution available and not used (a factor of 10), so in this case the operation would be lossless.