Doing some math over GPS output

Hello guys,

I'm using an L80 GPS module together with my Arduino UNO. GPS module responds with a massage in NMEA format, giving me information about the date, time, latitude, longitude, altitude (if possible), number of satellites etc.

Latitude and longitude information of NMEA are in the form of degrees and minutes (DD°MM.mmm’). I'm able to convert them into only degrees notation (DD.dddddd°).

I have the following problem: Given a particular location (e.g. 48.858125, 2.294398) and a safety radius of, let's say, 50 meters, how to determine weather (a, b) point is within a safety circle or not? Can you help me figuring out the math hiding behind? I know that, having latitudes and longitudes in degrees, my points are represented in an angular coordinate system, not Cartesian (linear) one.

I also know that Universal Transferse Mercator (UTM) representation of points on Earth is in Cartesian coordinate system. Do you, maybe, know how to transform degree notation (DD.dddddd°) into UTM notation? I know there are on-line tools that are able to do a conversion. However, I don't know the math. :cold_sweat:

Thank you very much for your time and effort to help me.

Sincerely, Bojan

Maybe I can simplify the problem....

How to determine distance in meters between two points on Earth represented in angular coordinate system?

That is much more clear, I hope.

Sincerely, Bojan.

you need the haversine function - http://forum.arduino.cc/index.php?topic=45760.0 - post #9

bojankoce:
Hello guys,

I’m using an L80 GPS module together with my Arduino UNO. GPS module responds with a massage in NMEA format, giving me information about the date, time, latitude, longitude, altitude (if possible), number of satellites etc.

Latitude and longitude information of NMEA are in the form of degrees and minutes (DD°MM.mmm’).
I’m able to convert them into only degrees notation (DD.dddddd°).

I have the following problem: Given a particular location (e.g. 48.858125, 2.294398) and a safety radius of, let’s say, 50 meters, how to determine weather (a, b) point is within a safety circle or not?

Bojan

Can you assume the Earth is a Sphere? of X diameter? 6371km?
If so, and you assume the safety circle is on this surface.

This gives you a circumference of 40030.1735 km or 4003173.5 meters
so a degree is 111194.93 meters or 8.9932E-6 degrees/meter
so 50m 4.4966E-4 degrees 0.000044966.

subtract the known position from the unknown, divide the difference by the degree to 50meter conversion factor

distance_50mUnits = sqrt(lat_delta^2+long_delta^2)

Any value < 1 is suspect to be within the ‘Safety’ circle.

Chuck.

distance_50mUnits = sqrt(lat_delta^2+long_delta^2)

This would be fine if the Earth were flat, but it is not.

The haversine approach noted above is the accepted approach. This page features a extremely useful collection of navigational formulas and calculators: Calculate distance and bearing between two Latitude/Longitude points using haversine formula in JavaScript

This would be fine if the Earth were flat, but it is not.

Within a 50 meter circle, it is certainly close enough to flat.

Within a 50 meter circle, it is certainly close enough to flat.

Yes, but the distance spanned by one degree of longitude depends on the latitude. Just do it right to begin with.

This gives you a circumference of 40030.1735 km or 4003173.5 meters so a degree is 111194.93 meters or 8.9932E-6 degrees/meter so 50m 4.4966E-4 degrees 0.000044966.

Only for longitude degrees at the equator, or for latitude degrees anywhere (approximately).

At his latitude of 48.8N, a degree of longitude is 8.9932e-6/cos(48.8) degrees/meter, or about 13.6531e-6 degrees/meter. Like PaulS says, you can treat a small region near the target location as being flat. But you have to treat latitude and longitude degrees differently because the Earth is not flat.

Degrees-to-meters is an ok approximation to use in this case, as the single-precision floating point numbers used in the Haversine calculation are not any good at small distances. 100m-ish, IIRC. [edit - see jremington correction below]

And then there's the whole problem of GPS wandering that much when you're stationary. Some GPS devices can guess the error in a location report, in cm. And some can give you a UTM coordinate. Most can tell if they've got a good fix that incorporates ground-based corrections.

Also, averaging location reports can reduce the error. According to this study, several hours of samples would be required to get the standard deviation below 25m or so.

Cheers, /dev

Haversine calculation are not any good at small distances. 100m-ish, IIRC

On the contrary, it works just fine at those distances. Accuracy begins to falls off for distances over about 500 km, keeping in mind the 6-7 decimal digits of precision for coordinates.

This example calculates the distance between two (lat,lon) points separated by 0.001 degree, and is accurate to within 1 meter. Basic code courtesy of Rob Tillaart.

void setup()
{
  Serial.begin(115200);
  float x = HaverSine(0., 180.001, 0., 180.);
  Serial.println(x, 5);
  x = HaverSine(45., 180.001, 45., 180.);
  Serial.println(x, 5);
}

void loop()
{
}

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;
}

Thank you all, guys, to your fruitful discussion. You all helped me a lot! I really appreciate it.

Especially thank to jremington and Rob Tillaart for the HaverSine() function.

I've been testing it and it seems pretty accurate for what I need. This is under the assumption that returned parameter"d" represents distance between two points in Kilometers. Right?

Sincerely, Bojan.

Also, does the same HaverSine() function applies for the points that have negative latitudes (South from the equator) and longitudes (West from the prime meridian), or I need to provide absolute values for function arguments?

Sincerely, Bojan

Everuthing you always wanted to know about haversine and more - https://en.wikipedia.org/wiki/Haversine_formula -

Elaborating the thoughts of /dev above

an approximation for short distances can be derived as follows:

at latitude p the length of one degree longitude ~ 40030174 / 360 * cos(p) = 111194.93 * cos(p) meters / degree for longitude the length is always 111194.93 meters / degree given 2 close points we can use Pythagoras as locally the world is flat enough: (imagine a 3rd point with same longitude as point 1 and same latitude as point 2)

double fastHaverSine(double lat1, double lon1, double lat2, double  lon2)
{
  // assume the sphere has circumference 1 on the equator
  // to keep the number in same order of magnitude
  // helps to keep precision
  double dx = lat2 - lat1;
  double dy = (lon2 - lon1) * cos(lat2 * (PI / 180.0));
  double dist = sqrt(dx * dx + dy * dy);
  return dist * 111194.93;              // correct for earth sizes ;)
}

This fastHaverSine() function will be discussed - http://forum.arduino.cc/index.php?topic=336729 -

It is misleading to call that a "Haversine" function. My favorite reference calls that function the "equirectangular approximation".

jremington: It is misleading to call that a "Haversine" function. My favorite reference calls that function the "equirectangular approximation".

Good reference, thanks for the link, I'll make a note in the other thread.

Rob, buddy, thanks a lot !

This fastHaverSine() function perfectly fits my needs. My distances will never be more than 300m - so this is it !

Cheers, Bojan.