Poor mans navigation system.

[KetilO]

Navigation systems to use in a boat is very expensive if you want a decent screen size and a nice user interface.
Example: GPSMAP® 720/720s https://buy.garmin.com/shop/shop.do?pID=37719#specsTab
In addition I would need a svinger for the sonar and a map covering my area, an additional $400 or so.
Total cost: $1800

For me the solution is obvious: Buy a cheap chart plotter / sonar and hook it up with a small cheap netbook via a RS232 to USB converter. And then make a chart plotter program.

Cuda 350 chart plotter / sonar, svinger included: http://www.cabelas.com/p-0065672020560a.shtml
I could probably get a cheap netbook for around $250, and a RS232 to USB for $20.
The maps I can grab for free.
Total cost: $480

Actually this is both cheaper aand a better solution for me as I will bring the netbook with me and dont have to sit in my boat to do trip planning and plot waypoints.

The Cuda sends GPS data using the NMEA 0183 protocol: http://www.tronico.fi/OH6NT/docs/NMEA0183.pdf
Longitude, Latitude is WGS 84, Degrees, Minutes and fractions of a minute. In my program I convert it to degrees and fractions of a degree and then convert it to an integer by ignoring the decimal point. The number of decimals is constant.

So far so good. But I ran into problems when trying to figure out how to calculate the distance between two Longitude, Latitude coordinates.
My math skills are really getting rusty.

I found this on Wikipedia: http://en.wikipedia.org/wiki/Great-circle_distance
Looking at the 'distance between two airports' example.
The degrees to radians part is easy, but the second formula is Greek to me.

Does anyone know what this formula means, example please?

Currently I assume the earth is flat (back to the middelages), but uses coordinates of the nearest place to reduce the error.

You can get what I have so far here: https://fbedit.svn.sourceforge.net/svnroot/fbedit/RadASM30/Release/Masm/Projects/ShowMap/ShowMap.zip
Note that the map tiles has been blured as they are copyrighted material.
Use the Trip Log / Replay Trip to see me race around my neighbourhood with my car. Actually the replay is x10 so I am not driving very fast. The speed shown is in knots.

If there is any interest in this project I will post the sources when I am done.

KetilO

[oex]

This might be of help to you....

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

(But if you get lost it isnt my fault :bg)

[KetilO]

Thanks a lot oex

Spherical law of cosines:
d = acos(sin(lat1).sin(lat2)+cos(lat1).cos(lat2).cos(long2−long1)).R

This one I can understand. Now I will be programming all night long translating it into fpu instructions.

KetilO

[clive]

I use the following spheroid model. At some level you have to make some compromises, because the global is pretty ugly

It works well for short distances, probably less than 35 KM, I use it for proximity testing geofences.

The value of PI that I typically use is the one specified by the GPS constellation and used by the receiver. I could use the WGS-84 datum for the global too, but the math gets messier because it's an ellipsoid not a sphere.

Code Select Expand


#define PI                      (3.1415926535898)               // ICD-200

#define DEG_TO_RAD              (PI / 180.0)
#define RAD_TO_DEG              (180.0 / PI)

#define EARTH_RADIUS            (6371000.0)
#define EARTH_CIRCUM_METRES     (EARTH_RADIUS * 2.0 * PI)
#define DEG_TO_METRES           (EARTH_CIRCUM_METRES / 360.0)

//****************************************************************************

// Measure short distances, assumes the Earth is a spheroid and readily
//  flattened. In reality it is an ellipsoid, and this computation is
//  overly simplified.

// Input decimal degrees, output metres

double ComputeDelta(double latA, double lonA, double latB, double lonB)
{
  double delta_lat;
  double delta_lon;
  double delta;

  delta_lat = fabs(latA - latB);
  delta_lon = fabs(lonA - lonB);

  delta_lon = delta_lon * DEG_TO_METRES * cos(((latA + latB) / 2.0) * DEG_TO_RAD);
  delta_lat = delta_lat * DEG_TO_METRES;

  delta = sqrt((delta_lon * delta_lon) + (delta_lat * delta_lat));

  return(delta);
}

//****************************************************************************


In reality you can probably loose the fabs()'s because the squaring will remove the sign, but I often want to know the Northing and Easting difference. If you just want to compare the current location to find the nearest waypoint you can loose the square root and perform a simple magnitude test against the table of waypoints. On a Intel processor running at a few gigahertz this probably doesn't matter, but on small embedded micros you want to avoid as much floating point math as possible.

[GregL]

Here is some "Great Circle" FPU code I wrote.  It uses the Spherical Law of Cosines.

[oex]

hmm I tried stealig your code Clive but failed miserably :lol maybe someone can spot my error.... There are other algorithms I have found but maybe the issue is based on my usage of floats rather than doubles?

Code Select Expand


oexLongLatDistance PROC USES esi edi latA:REAL4, lonA:REAL4, latB:REAL4, lonB:REAL4

LOCAL lonX:REAL4
LOCAL latD:REAL4
LOCAL lonD:REAL4
LOCAL latD2:REAL4
LOCAL lonD2:REAL4
LOCAL oexDistance:DWORD

LOCAL oexPI:REAL4
LOCAL oexEarthRadius:REAL4
LOCAL oexEarthCircumferenceMeters:REAL4
LOCAL oexDegreesToRadians:REAL4
LOCAL oexDegreesToMeters:REAL4

m2m oexPI, CFLT(3.1415926535898)
m2m oexEarthRadius, CFLT(6371000.0)

fld oexPI
fdiv CFLT(180.0)
fstp oexDegreesToRadians

fld oexEarthRadius
fmul CFLT(2.0)
fmul oexPI
fstp oexEarthCircumferenceMeters

fld oexEarthCircumferenceMeters
fdiv CFLT(360.0)
fstp oexDegreesToMeters

fld latA
fsub latB
fstp latD

fld lonA
fsub lonB
fstp lonD

fld latA
fadd latB
fdiv CFLT(2.0)
fmul oexDegreesToRadians
fcos
fstp lonX

fld lonD
fmul oexDegreesToMeters
fmul lonX
fstp lonD

fld latD
fmul oexDegreesToMeters
fstp latD

fld lonD
fmul lonD
fstp lonD2

fld latD
fmul latD
fstp latD2

fld lonD2
fadd latD2
fsqrt
fistp oexDistance

mov eax, oexDistance

ret

oexLongLatDistance ENDP


[oex]

:lol I found the bug in my coding of the haversine formula and have updated the code accordingly.... Floats is enough for about 0.3%ish accuracy I believe....

[clive]

The last part you could code like this..

Code Select Expand

...
fld lonD
fmul st,st(0)
fld latD
fmul st,st(0)
faddp st(1),st
fsqrt
fistp oexDistance

mov eax, oexDistance


You could probably keep everything within the FPU, it will take me a little time to code and test

[clive]

Something like this seems to be fairly concise..

Code Select Expand

double ComputeDeltaC(double latA, double lonA, double latB, double lonB)
{
  const double deg2rad = 0.017453292519943334;
  const double deg2metres = 111194.92664455897;
  const double half = 0.5;
  double delta;

  __asm
  {
      fld     qword ptr [latB]
      fadd    qword ptr [latA]
      fmul    qword ptr [half]
      fmul    qword ptr [deg2rad]
      fcos
      fld     qword ptr [lonA]
      fsub    qword ptr [lonB]
      fmulp   st(1),st
      fmul    qword ptr [deg2metres]
      fmul    st(0),st
      fld     qword ptr [latA]
      fsub    qword ptr [latB]
      fmul    qword ptr [deg2metres]
      fmul    st(0),st
      faddp   st(1),st
      fsqrt
      fstp qword ptr [delta]
  }

  return(delta);
}


[oex]

nice 1 Clive, it was a time vs value excercise I dont have more than a few long/lats to programaticallycheck as yet however that code improvement is gratefully accepted for future usage :bg

[GregL]

What, my code = chopped liver?  :P

[dedndave]

"mmmmmmmmm - chopped liver"

[GregL]

Dave,

Gee, thanks. I originally wrote it to calculate bearing and distance for radio contacts. The bearing part is great for aiming beams, the distance part is just interesting and can be used for bragging rights.

[dedndave]

i have always had an interest in writing a program that would generate great circle maps
a user could enter their long and lat and it would crank out a map
of course, there would be a lot of user-selected options
maybe i'll attack that when i am a little better at win32   :bg
something like SM3GSJ has written:

http://www.qsl.net/sm3gsj/download.htm

it would bascially work on the same set of equations, with a database that describes the coast/boundry lines
this one is centered on Chatham Island, and has callsign prefixes (click on image for full-size)



here is a simpler one for W5KFT near Austin, Texas (click on image for W5KFT's site)

[oex]

What, my code = chopped liver?  :P

Hi Greg,

I believe your code is bearing distance rather than distance between 2 points.... I may also have a usage for this yet however havent gotten that far yet :bg