Search code examples
gpsmicrocontrollermsp430code-composer

How do I calculate distance between GPS co-ordinates using Microcontroller chip

I need to calculate the distance between GPS co-ordinates to calculate distance being traveled. I've tried both the Haversine and Vincenty algorithms, which work fine on my desktop PC, but when I use the same code for MSP430 chip using CCS IDE, the IDE is throwing error saying that "program will not fit into available memory".

Is there any other alternative method or code to find the distance between two GPS co-ordinates? which will fit in available memory of MSP430 Microcontroller ?

Solution

  • It's not surprising that you're running out of memory, because the microcontroller you are using, the Texas Instruments MSP430F2274, has only 32kB of flash, and 1kB of RAM.

    There are several approaches to solving your problem, each with different tradeoffs. Here are three:

    • Use another microcontroller that has more memory (there are many in the MSP430 family).
    • Optimize your code to fit in the available space.
    • Use a simpler formula than the Vincenty or Haversine.

    I'll address the two latter approaches below.

    Optimize Your Code

    Depending on the accuracy requirements of your application, optimizing your existing code might be a better approach than using a simpler formula than Vincenty or Haversine.

    A Simple Way to Optimize

    Perhaps simply setting the compiler to optimize for size will solve your problem. In the MSP430 toolset, use the --opt_for_speed=0 switch. According to the MSP430 Optimizing C/C++ Compiler User's Guide (v15.9.0.STS) (page 62), this switch:

    enables optimizations geared towards improving the code size with a high risk of worsening or impacting performance.

    So you might very easily get things to work by using this switch, at the cost of trading away speed for memory space.

    A More Involved Way to Optimize

    Assuming you are using the floating point math library provided with your compiler, you might be able to still use Vincenty or Haversine if you replace the math library with a more space-efficient version. The CORDIC fixed-point algorithms provide iterative approaches to calculating the trigonometric functions, that trade away speed for space efficiency. If you roll your own math library, you might achieve a good balance between space, speed, and accuracy. A 16-bit version of the CORDIC approach for sine() and cosine() for the MSP430 is here; you will need to determine whether it provides the degree of accuracy and precision you need.

    Use a Different Formula

    In general, the various algorithms that calculate distance between two points on the earth represent a trade-off between accuracy and complexity. The Vincenty algorithm you cited is much more accurate than the Haversine, as it more correctly represents the earth as an oblate spheroid instead of as a sphere of radius R; hence the math is more complex.

    For reference, the Haversine method (which assumes the earth is a perfect sphere) is shown here:

    dlon = lon2 - lon1
dlat = lat2 - lat1
a = sin^2(dlat/2) + cos(lat1) * cos(lat2) * sin^2(dlon/2)
c = 2 * arcsin(min(1,sqrt(a)))
d = R * c

    The intermediate result c is the distance in radians. The distance d is in the same units as R (radius of the earth).

    As you can see, the Haversine employs an arcsin() in the calculation.

    You can simplify the math further by employing the Polar Coordinate Flat-Earth method:

    a = pi/2 - lat1
b = pi/2 - lat2
c = sqrt(a^2 + b^2 - 2 * a * b * cos(lon2 - lon1)
d = R * c

    Notice that there is no arcsin() in this calculation, but there is a sqrt().

    A discussion of the accuracy tradeoffs between the Haversine and the Polar Coordinate Flat-Earth methods is here, question Q5.1.

    See also