Calculating distance between two points accurately

Forum 2005-2010 (read only) Software Syntax & Programs
1

I want to calculate the distance between two points. I have the latitude and longitude of each of the points as a string formatted as DDDMMmmm (i.e. degrees, minutes and decimal fractions of minutes).

Step one is to convert the latitude and longitude from a string into a decimal number of degrees.
Step two is to calculate the distance between the two points using one of the various mathematical formula easily available on the net. (this one cribbed from http://williams.best.vwh.net/avform.htm#Dist)

The great circle distance d between two points with coordinates {lat1,lon1} and {lat2,lon2} is given by:
d=acos(sin(lat1)*sin(lat2)+cos(lat1)*cos(lat2)*cos(lon1-lon2))

Before I even start on this I'm not sure if it's going to be possible with any reasonable degree of accuracy. I need to be able to convert my string Latitude and Longitude into a number. The best data type for this seems to be float, but on the arduino reference pages I've found the following....

Floats have only 6-7 decimal digits of precision. That means the total number of digits, not the number to the right of the decimal point.

I really need to have lat and long as degrees with at least six decimal places. It seems that a float isn't going to manage this, is this correct?

If I can't get my lat and long accurately converted to a decimal, then the formula quoted above definitely isn't give me an accurate distance. There's a few functions for calculating the distance between two points on this forum, but they all use floats, I guess none of these can be very accurate? I'd like to be able get the distance correct to within a few 10s of meters.

Any suggestions? I had wondered about splitting the lat and long into degrees (as an integer) and minutes (as a float),this should give me the required accuracy, but then I've got to somehow work out the distance the two points using a lot more variables

2

How far apart are the points in question? If one point is in America and the other point is in Europe, why do you need the distance to be that accurate?

If the points are not that far apart, perhaps the great circle distance isn't really required, and a simple(r) point-to-point distance calculation would work.

3

The points are likely to be between 40 and 400 km apart. I'm working on a navigation project and really need an accuracy of at least a couple of 100 meters over these sorts of distances.

I've plugged in some co-ordinates of two points that I know are 38.1 km apart and the result comes out as 39.5. Thats an error of nearly 1500 meters between two points less than 40km apart.

I think my best bet is try to split each lat into degrees (as an integer) and minutes (as a float) and then try to calculate it from there. If (for example) both of my latitudes start with (say) 51 then I think I can strip this off both values without effecting the overall output.

To be honest, this is probably more of an trigonometry problem than an arduino problem.

Any help appreciated.

4

Take a look here:
http://letsmakerobots.com/node/19554

The distance calculation is in one of the posts and in the full source code that is available for download.

5

Thanks arbarnhart

The problem is that both this library and my own both rely on using floats, the limited precision of floats means the end result of the calculations can't be relied on.

I'm looking for some method with a greater degree of accuracy than can be achieved with floats.

6

I am away from the computer where I have my code, but I do basically the same calculations but with double instead of float.

When you say "can't be relied on", what exactly do you mean? How precise do you need? I use almost exactly the same code as Patrick for pretty much the same reason he does, to navigate. I know it works for short distances.

7

As far as I can make out doubles and floats are more-or-less the same in arduino world.

If I have a latitude (as a string) of say 12345678, I can convert this to a float or double such as 123.45678. Floats have a precision of 6-7 digits, this means that the last digit or two of the above number may not be accurate. If my true longitude is 123.45678, the arduino could see this as any value from 123.45600 to 123.45699. In navigational terms, this can equate to an inacuracy of several hundreds of meters for each fix. When working out the distance between two fixes about 40 km appart the calculated distance can be over 1000 meters out.

8

I don't know the internal implementation, but I was using a web site to test my function and was disappointed in the variance with floats, changed to doubles and then got matching results.

EDIT Bad info above. I must have done something else to correct the problems i was having.

Floats have only 6-7 decimal digits of precision. That means the total number of digits, not the number to the right of the decimal point. Unlike other platforms, where you can get more precision by using a double (e.g. up to 15 digits), on the Arduino, double is the same size as float.

Yet another EDIT - I remember now how I convinced myself that doubles work better. Because that code is pretty basic ANSI C, I unit tested it on the PC. So I have in fact confirmed the inaccuracy you mention but did not realize it. In my implementation, wind and current can affect my course and the target may move, so I recalculate a lot and it does seem to be correct (or at least close enough to work) for very short distances.

Below are the relevant functions from my code.

//convert degrees to radians
double dtor(double fdegrees)
{
return(fdegrees * PI / 180);
}

//Convert radians to degrees
double rtod(double fradians)
{
return(fradians * 180.0 / PI);
}

//Calculate distance form lat1/lon1 to lat2/lon2 using haversine formula
//Note lat1/lon1/lat2/lon2 must be in radians
//Returns distance in feet
long CalcDistance(double lat1, double lon1, double lat2, double lon2)
{
double dlon, dlat, a, c;
double dist = 0.0;
dlon = dtor(lon2 - lon1);
dlat = dtor(lat2 - lat1);
a = pow(sin(dlat/2),2) + cos(dtor(lat1)) * cos(dtor(lat2)) * pow(sin(dlon/2),2);
c = 2 * atan2(sqrt(a), sqrt(1-a));

dist = 20925656.2 * c;  //radius of the earth (6378140 meters) in feet 20925656.2
return( (long) dist + 0.5);
}

//Calculate bearing from lat1/lon1 to lat2/lon2
//Note lat1/lon1/lat2/lon2 must be in radians
//Returns bearing in degrees
int CalcBearing(double lat1, double lon1, double lat2, double lon2)
{
lat1 = dtor(lat1);
lon1 = dtor(lon1);
lat2 = dtor(lat2);
lon2 = dtor(lon2);

//determine angle
double bearing = atan2(sin(lon2-lon1)*cos(lat2), (cos(lat1)*sin(lat2))-(sin(lat1)*cos(lat2)*cos(lon2-lon1)));
//convert to degrees
bearing = rtod(bearing);
//use mod to turn -90 = 270
bearing = fmod((bearing + 360.0), 360);
return (int) bearing + 0.5;
}

void ComputeDestPoint(double lat1, double lon1, int iBear, int iDist, double *lat2, double *lon2)
{
double bearing = dtor((double) iBear);
double dist = (double) iDist / 20925656.2;
lat1 = dtor(lat1);
lon1 = dtor(lon1);
*lat2 = asin(sin(lat1)* cos(dist)+ cos(lat1)* sin(dist)*cos(bearing));
*lon2 = lon1 + atan2(sin(bearing)*sin(dist)*cos(lat1), cos(dist)-sin(lat1)*sin(*lat2));
*lon2 = fmod( *lon2 + 3 * PI, 2*PI )- PI;
*lon2 = rtod( *lon2);
*lat2 = rtod( *lat2);
}
9

All distance calculations I could found:

Elipsoidal is the most accurate and heavy, but, we don't live in a round world.

Just multiply everything by 10e6, make everything int, add the comma later as string.

10

http://www.movable-type.co.uk/scripts/latlong.html

The haversine formula 'remains particularly well-conditioned for numerical computation even at small distances' – unlike calculations based on the spherical law of cosines. The 'versed sine' is 1-cos[ch952], and the 'half-versed-sine' (1-cos[ch952])/2 = sin²([ch952]/2) as used above. It was published by R W Sinnott in Sky and Telescope, 1984, though known about for much longer by navigators. (For the curious, c is the angular distance in radians, and a is the square of half the chord length between the points).

long cnt = 1;

void setup()
{
  Serial.begin(115200);
}

void loop()
{
  cnt++;
  Serial.print(millis() / 1000);
  Serial.print("\t");
  Serial.print(cnt);
  Serial.print("\t");  
  Serial.print(cnt * 1000 / millis());
  Serial.print("\t");  
  float x = HaverSine(0, 0, 0, 180);
  Serial.println(x, 5);
} 

float HaverSine(float lat1, float lon1, float lat2, float lon2)
{
  float ToRad = PI / 180.0;
  float R = 6371;   // radius earth in Km
  
  float dLat = (lat2-lat1) * ToRad;
  float dLon = (lon2-lon1) * ToRad; 
  
  float a = sin(dLat/2) * sin(dLat/2) +
        cos(lat1 * ToRad) * cos(lat2 * ToRad) * 
        sin(dLon/2) * sin(dLon/2); 
        
  float c = 2 * atan2(sqrt(a), sqrt(1-a)); 
  
  float d = R * c;
  return d;
}
11

That is the same calculation I am using, except that I have a function for doing the "ToRad" and I return a long that is the number of feet. I am getting away with any lack of precision that may occur due to the aforementioned float precision issue because my use of distance is very limited - far enough away to go really fast, close enough to slow up, close enough to stop...

12

@arbarnhart
Didn't check your code, sorry, but you're right same code and yours has a more precise earth radius so think the result is more precise in the end.

thanks,
Rob

13

No, it isn't precise after all. The stuff I quoted above from the Arduino reference says doubles are just floats and floats are only good for 6 or 7 digits of precision. My constant has 9 digits, so what it is using is just a nearby numerical neighbor of that number.

14

If you convert the two lat/lon values to degrees, minutes, and seconds, and subtract the smaller degree value from the both degree values, and then convert back to degrees values, the result will generally be only one (or two at most) digits before the decimal point, leaving room for more digits after the decimal point, and greater precision. Perhaps that would be enough to get you the accuracy that you require, when computing the distance between the two points.

15

If I have a latitude (as a string) of say 12345678, I can convert this to a float or double such as 123.45678.

This may be part of your accuracy problem (if it's not just a trivial example without proper conversion).

In your first post you say you're getting a string as DDDMMmmm, which is degrees, minutes, and decimal fractions of a minute. Based on this format, 12345678 does NOT equal 123.45678 degrees.

It is 123 degrees and 45.678 minutes.

45.678 minutes = 45.678/60 degrees, or 0.7613 degrees.

So 12345678 would then equal 123.7613 degrees. If your actual calculations are indeed making the proper conversion, then ignore this post.

16

If you convert the two lat/lon values to degrees, minutes, and seconds, and subtract the smaller degree value from the both degree values, and then convert back to degrees values, the result will generally be only one (or two at most) digits before the decimal point, leaving room for more digits after the decimal point, and greater precision. Perhaps that would be enough to get you the accuracy that you require, when computing the distance between the two points.

I am not sure that will do it. I am afraid a completely different calculation would have to be used. I think the problem is that the answer from this equation is always going to be in radians and it is going to be multiplied against a large number (especially since I am using feet). The lack of precision will be compounded by that.

If I could change the calculation of "c" to produce a rational (2 longs, the numerator and denominator) instead of a float, then I might get the precision back. I could be wrong, but I think it is the calculation of the really small number which is then multiplied by the large number where most of the error comes in.

17

(especially since I am using feet). The lack of precision will be compounded by that.

True, but you could compute the distance in larger units (miles, for example), and convert to smaller units only for display purposes.

That way, the 'really big number' won't be so large.

18

Have you considered using this fixed point library? Not used it myself but seems like a possible solution.