1

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 ?

Rajat
  • 1,043
  • 12
  • 23
shafi
  • 145
  • 6
  • Which chip are you using? – CL. Dec 22 '15 at 15:20
  • There is another method called [Sferical Law of Cosines](https://jsperf.com/vincenty-vs-haversine-distance-calculations/2) but I don't know its memory requirement. – Weather Vane Dec 22 '15 at 17:34
  • I am using msp430f2274 microcontroller for this process. The issue is showing while trying to find the inverse of cos of a value. – shafi Dec 23 '15 at 09:49
  • So msp430f2274 has 32KB Flash, 1K RAM but after the essential stuff of your application, what is the available memory? Could you impose/cope with, a limit to the max arc/distance? What accuracy is acceptable? – chip_wrangler Dec 24 '15 at 10:56
  • @WeatherVane According to http://www.faqs.org/faqs/geography/infosystems-faq/ (Question Q5.1), the Spherical Law of Cosines method is unreliable for short distances since the inverse cosine deteriorates in accuracy as the angle gets smaller. – sifferman Dec 24 '15 at 12:33
  • @sifferman mine was just a casual google - quite often questions are asked when the answer is very easily found, and OP did not mention this method ;) – Weather Vane Dec 24 '15 at 12:46

1 Answers1

5

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

Community
  • 1
  • 1
sifferman
  • 2,955
  • 2
  • 27
  • 37