Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

.NET

GPS Programming & .NET


June, 2004: GPS Programming & .NET

Finding your way back home

Johan is the founder of franson.biz, a GPSTools provider in Sweden. He can be contacted at johanfranson.biz.


The Global Positioning System (GPS) is a worldwide navigation system built around 24 satellites and millions of receivers. Each satellite has a very exact atomic clock to keep time accurate to within three nanoseconds (three billionths of a second). With the aid of ground stations, all satellites also have an exact model of their orbits around the earth. Each satellite continuously broadcasts its time- stamped position. By measuring the differences in timestamp and satellite positions, a receiver on Earth can determine its position using triangulation.

It wasn't so long ago that GPS devices were limited to high-end applications, such as those used by the military. However, today GPS receivers are considered consumer items and embedded in everything from farm equipment and automobiles, to handheld devices and laptop computers.

One main application area for GPS receivers is in navigation. The killer application of the GPS is, of course, to know a position in real time. But there are also a few other elements related to basic navigation, such as converting latitude/longitude information from a GPS to easting/northing coordinates used by many maps, or calculating distance/direction between known positions. In this article, I show how you can get position and speed by accessing GPS devices via .NET, and examine a method for calculating distance and bearing between two positions. The application I present saves a position and shows the distance/direction from your current position to the saved position, ensuring that you'll always find your way back.

Geographic Information Systems (GIS) are another common GPS application. A GIS system typically contains information about objects—their positions and other characteristics—in a database. The database is then used to plot maps or make queries such as "How many houses are located in this particular area?" A GPS is ideal in the process of creating and updating information in a GIS database.

GPS devices can be connected to computers in a number of ways—standard serial ports, USB, Bluetooth, and CF slot are the most common. For the programs presented here, I used DeLorme USB. While there are a number of proprietary protocols used to communicate with a GPS (SiRF and Garmin are the most common), there is one protocol that's supported by almost every available GPS—the National Marine Electronics Association 0183 (NMEA 0183). As the name implies, NMEA was originally developed for marine use, which is evident when studying the protocol. However, to transfer position, speed, satellite, and error information, a GPS only uses a subset of NMEA. NMEA is a simple, ASCII-based protocol that communicates over a serial port at 4800 baud, 8 bit, no parity, and 1 stop bit. If a GPS is not connected via a serial port, it usually comes with some kind of software to emulate a serial port.

Unfortunately, .NET does not support serial-port access natively. Luckily, there are third-party workarounds. Gotdotnet.com, for instance, has an open-source C# implementation for .the NET Desktop Framework, while opennetcf.org has an open-source implementation for the .NET Compact Framework. Here, I assume you get a stream of serial data from one of these components.

When connected, the GPS sends NMEA data continuously over the serial port. (Some GPS receivers need to be configured to use NMEA because they default to their proprietary protocols.) The NMEA data is divided into sentences, where each sentence starts with a "$" and ends with a carriage-return/line-feed (CR/LF). The integrity of each sentence is confirmed by a checksum. In turn, each sentence is divided into a set of comma-separated fields. The first field contains a command and the following fields contain data, ended by the checksum. Table 1 describes the NMEA syntax in detail. The first field cmd specifies the type of the sentence. Following the "*" is hh, a two-digit hexadecimal checksum. The checksum is calculated by XORing the ASCII value of all data between (not including) the "$" and "*." Listing One implements an NMEA checksum validator in C#, and Listing Two presents a full NMEA parser.

A GPS receiver needs an open sky to calculate its position, referred to as a "fix." The accuracy of the position depends on how many satellites it can track and the angle of the satellites over the horizon. There are also other factors such as atmospheric conditions and errors in the satellites orbits that influence accuracy. An open sky with no high buildings nearby usually means an error of less than 10 meters. A GPS device can usually determine its position indoors if it is close to a window, which can be useful during development.

The errors introduced by atmospheric conditions and satellite orbit discrepancies are systematic in nature. This fact is used by differential GPS systems that send out local error corrections over radio. A GPS receiver is placed at a known position, where it continuously calculates its position. The difference between its known position and its calculated position is assumed to have been introduced by the systematic error sources described. This information is then broadcast and can be used by mobile GPS receivers for fine tuning. WAAS, a common system in the U.S., is implemented in many low-cost GPS receivers and increases accuracy to within 3-4 meters. Developers using NMEA do not need to worry much about this because the corrections are already included in the data sent from the GPS, if the GPS supports it.

The position is contained in any of the following three NMEA sentences—GGA, RMC, and GLL. (Table 2 describes these sentences in detail.) Some GPS receivers send all three sentences, while some only support one or two. Therefore, support for all three must be implemented to ensure the application works with all GPS receivers on the market. The GPS continuously sends this information over the serial link automatically. Since these sentences are sent even when the GPS has no fix, it is important to check the "valid" field to make sure the positioning information is okay.

From the GGA, RMC, and GLL sentences, latitude/longitude information can be extracted. Latitude determines the position in the south to north direction. It is 0 at the equator, minus 90 degrees at the southern pole, and plus 90 degrees at the northern pole. Longitude determines the position in the west to east direction. It is 0 at the Greenwich meridian, negative on the western hemisphere, and positive on the eastern hemisphere. One lap around the equator is 360 degrees. One degree is divided into 60 minutes, and one minute into 60 seconds. This has nothing to do with time, it just shares the same terminology. In NMEA, the latitude/longitude are encoded the same way. One field contains the number of degrees and minutes in an ASCII string, and one field the hemisphere. For most purposes, this information can be converted to a double, where the integer part is degrees, and the fractional part minutes and seconds. The sign determines the hemisphere. This format is called "decimal degrees." Listing Three converts the NMEA formatted position (latitude/longitude) to decimal degrees.

Speed and heading information can be obtained from the RMC and VTG sentences. A GPS may implement one or both of these sentences, which makes it necessary to include support for both. NMEA's marine heritage dictates that speed is measured in knots, which need to be converted by the application. The direction in which the GPS is moving is specified in degrees. Ninety degrees for east, 180 for south, 270 for west, and 0 or 360 for north.

The Earth could be described as a sphere that is slightly pressed together at the top and bottom. The Earth is wider at the equator because it rotates. This is mathematically modeled as an ellipsoid. The parameters that define the ellipsoid—its major axis, minor axis, and displacement from the center of the Earth—is called a "datum." The datum used in GPS systems is called "WGS84." A position described in latitude/longitude defines a point on a datum. Since there are many different data in use over the world, a specific set of latitude/longitude coordinates does not necessarily mean the same physical position on Earth. In the U.S., two different data in use are NAD27 and NAD83. NAD83 is almost identical to WGS84, but NAD27 is different from WGS84. In this article, I assume all coordinates are based on WGS84, but you always need to be aware of the differences when dealing with coordinates from sources other than a GPS. Transformation between data can be made using the 7-parameter Helmert formula (see http://earth-info.nima.mil/GandG/datums/ natodt.html for details).

It is tricky to use latitude/longitude to calculate distances and directions. A spherical coordinate system, which the latitude/longitude coordinates span, is unsuitable for the task. For example, the distance in meters (or feet) of 1 degree east depends on the latitude. However, a Cartesian coordinate system with an x-y-axis, where x indicates west to east and y indicates south to north, would be more suitable. The axes in such a coordinate system are called "easting and northing." With the coordinates in easting and northing measured in meters (or feet), calculations of distances and directions are almost trivial. This change of coordinate systems is made by a process called "projection." Each position on the spherical surface of the Earth is moved to a flat surface. The created surface should be conformal, which means that shapes in the real world should be locally preserved on the projected surface. There are many projections available to accomplish this, all with their own trade offs. "Transverse mercator" is the most commonly used, and it will be used here. The new coordinate system is sometimes referred to as a "grid." The penalty for this transformation is the introduction of an error, the coordinate system will also only be valid on a local area as the error increases with the distance from the grid's center. (For more information on map projection, see http://www.colorado.edu/geography/gcraft/notes/mapproj/mapproj_f.html)

All states in the U.S. and all countries in the world use different grids to make local maps. In the U.S., the most commonly used system is the State Plane Coordinate System (SPCS), which exists in two different versions—one from 1927 and one from 1983. There is also the international Universal Transverse Mercator (UTM) grid, which is the one I use in this article. UTM is divided into 60 zones. Each zone is 6-degrees-wide longitude. The zone starting at 180 degrees west is number 1. The zone starting at 174 degrees west is number 2, and so on. Each zone spans its own easting/northing coordinate system. The error is about 1/1250 at the zones boundaries, but much less in the center. SPCS and most national grids are designed to have an error of less than 1/10,000, but they also have smaller defined zones. To avoid a negative northing, 10,000,000 meters are added to UTM coordinates south of the equator. The important thing to remember about UTM is that it provides a method to transform the coordinates received from the GPS to a Cartesian coordinate system, where positions can be handled as if the surface of the Earth were flat. Listing Four implements the projection in C#.

With this information, calculating the distance between two points is as simple as using the Pythagorean theorem, and the bearing can be determined using simple trigonometry. Listings Five and Six implement this in C#.

Using Listings One through Six, it is straightforward to build an application that helps you find the way back to a saved position (for example, that great fishing spot on the lake). Listing Seven presents an application that shows the distance and bearing back to a saved position. OnSerialData takes unparsed NMEA data received from a GPS as its argument and continuously saves the current position in m_latitude and m_longitude. OnSavePositon converts the current position to UTM and saves it to m_saved_easting and m_saved_northing.

OnSavePosition could be called by a button event handler. OnFindWay calculates and displays the distance and bearing from the current position to the saved position; this method could be called by a timer or button handler.

Finally, there are third-party GPS components available that simplify GPS development. Listing Eight implements the application I've presented here in C#, but using the GpsToolsNET.DLL (which my company produces).

DDJ



Listing One

// Returns true if checksum of NMEA sentence is valid
public bool ValidateChecksum(string Sentence)
{
    int  sum = 0, inx;
    char[] sentence_chars = Sentence.ToCharArray();
    char tmp;
    // All character xor:ed results in the trailing hex checksum
    // The checksum calc starts after '$' and ends before '*'
    for(inx = 1; ; inx++)
    {
        if(inx >= sentence_chars.Length) // No checksum found
            return false;
        tmp = sentence_chars[inx];
        // Indicates end of data and start of checksum
        if(tmp == '*')   
            break;
        sum = sum ^ tmp;    // Build checksum
    }
    // Calculated checksum converted to a 2 digit hex string
    string sum_str = String.Format("{0:X2}", sum);
    // Compare to checksum in sentence
    return sum_str.Equals(Sentence.Substring(inx + 1, 2));
}
Back to article


Listing Two
private string m_raw_buffer;
// Returns an array of all fields in the next valid NMEA sentence RawData 
// adds new raw data to be parsed. If RawData is null parsing of old data 
// continues. Returns null if no more valid sentences are found
public string[] Parse(string RawData)
{

    string sentence;
    int start, end;
    if(RawData != null)
    {
        m_raw_buffer += RawData; // Add new data
    }
    do
    {
        // Find start of next sentence
        start = m_raw_buffer.IndexOf("$");
        if(start == -1)
        {
            // No start found
            m_raw_buffer = null;
            return null;
        }
        m_raw_buffer = m_raw_buffer.Substring(start);
        // Find end of sentence
        end = m_raw_buffer.IndexOf("\r\n");
        if(end == -1)
        {
            // No end found, wait for more data
            return null;
        }
        sentence = m_raw_buffer.Substring(0, end + 2);
        m_raw_buffer = m_raw_buffer.Substring(end + 2);
    }
    while(!ValidateChecksum(sentence));
    // Valid sentence found!
    // Remove trailing checksum and \r\n
    sentence = sentence.Substring(0, sentence.IndexOf("*"));
    // Split into fields and return array
    return sentence.Split(",".ToCharArray());
}
Back to article


Listing Three
// Converts NMEA formatted (DDMM.MMMMM) position (latitude or longitude)
// to decimal degrees
public double Nmea2DecDeg(string NmeaLonLat, string Hemisphere)
{
    int inx = NmeaLonLat.IndexOf(".");
    if(inx == -1)
    {
        return 0;    // Invalid syntax
    }
    string minutes_str = NmeaLonLat.Substring(inx - 2);
    double minutes = Double.Parse(minutes_str, new 
              System.Globalization.CultureInfo("en-US"));
    string degrees_str = NmeaLonLat.Substring(0, inx-2);
    double degrees = Convert.ToDouble(degrees_str) + minutes / 60.0;
    if(Hemisphere.Equals("W") || Hemisphere.Equals("S"))
    {
        degrees = -degrees;

    }
    return degrees;
}
Back to article


Listing Four
// Parameters for the GWS84 ellipsoid
const double WGS84_E2 = 0.006694379990197;
const double WGS84_E4 = WGS84_E2 * WGS84_E2;
const double WGS84_E6 = WGS84_E4 * WGS84_E2;
const double WGS84_SEMI_MAJOR_AXIS = 6378137.0;
const double WGS84_SEMI_MINOR_AXIS = 6356752.314245;
// Parameters for UTM projection
const double UTM_LONGITUDE_OF_ORIGIN = 3.0 / 180 * Math.PI;
const double UTM_LATITUDE_OF_ORIGIN = 0;
const double UTM_FALSE_EASTING = 500000;
const double UTM_FALSE_NORTHING_N = 0;    // Northern hemisphere
const double UTM_FALSE_NORTHING_S = 10000000; // Southern hemisphere
const double UTM_SCALE_FACTOR = 0.9996;

// Takes a position in latitude / longitude (WGS84) as input
// Returns position in UTM easting/northing/zone (in meters)
public void DecDeg2UTM(double latitude, double longitude,
    out double easting, out double northing, out int zone)
{
    // Normalize longitude into Zone, 6 degrees
    int int_zone = (int) (longitude / 6.0);
    if(longitude < 0)
        int_zone--;
    longitude -= (double) int_zone * 6.0;
    zone = int_zone + 31;    // UTM zone
    // Convert from decimal degrees to radians
    longitude *= Math.PI / 180.0;
    latitude *= Math.PI / 180.0;
    // Projection
    double M = WGS84_SEMI_MAJOR_AXIS * m_calc(latitude);
    double M_origin = WGS84_SEMI_MAJOR_AXIS * m_calc(UTM_LATITUDE_OF_ORIGIN);
    double A = (longitude - UTM_LONGITUDE_OF_ORIGIN) * Math.Cos(latitude);
    double A2 = A * A;
    double e2_prim = WGS84_E2 / (1 - WGS84_E2);
    double C = e2_prim * Math.Pow(Math.Cos(latitude), 2);
    double T = Math.Tan(latitude);
    T *= T;
    double v = WGS84_SEMI_MAJOR_AXIS / Math.Sqrt(1 - WGS84_E2 *
        Math.Pow(Math.Sin(latitude), 2));
    northing = UTM_SCALE_FACTOR * (M - M_origin + v * Math.Tan(latitude) * (
        A2 / 2 + (5 - T + 9 * C + 4 * C * C) * A2 * A2 / 24 +
        (61 - 58 * T + T * T + 600 * C - 330 * e2_prim) *
        A2 * A2 * A2 / 720));
    if(latitude < 0)
        northing += UTM_FALSE_NORTHING_S;
    easting = UTM_FALSE_EASTING + UTM_SCALE_FACTOR * v * (
        A + (1 - T + C) * A2 * A / 6 +
        (5 - 18 * T + T * T + 72 * C - 58 * e2_prim) * A2 * A2 * A / 120);

}
private double m_calc(double lat)
{
   return (1 - WGS84_E2 / 4 - 3 * WGS84_E4 / 64 - 5 * WGS84_E6 / 256) * lat -
        (3 * WGS84_E2 / 8 + 3 * WGS84_E4 / 32 + 45 * WGS84_E6 / 1024) * 
        Math.Sin(2 * lat) + (15 * WGS84_E4 / 256 + 45 * WGS84_E6 / 1024) * 
        Math.Sin(4 * lat) - (35 * WGS84_E6 / 3072) * Math.Sin(6 * lat);
}
Back to article


Listing Five
// Calculates the distance between two UTM coordinates using Pythagoras 
// theorem. The coordinates must be in the same UTM zone and in 
// the same hemisphere.
public double Distance(double easting1, double northing1, double 
easting2, double northing2)
{
    return Math.Sqrt(
        Math.Pow((easting1 - easting2), 2) +
        Math.Pow((northing1 - northing2), 2));
}
Back to article


Listing Six
// Calculates the bearing between two UTM coordinates. Works best on local 
// calculations and the coordinates must be in the same UTM zone.
public double Bearing(double easting1, double northing1, 
                                      double easting2, double northing2)
{
    double a = 0;
    double dEast = easting2 - easting1;
    double dNorth = northing2 - northing1;
    if(dEast == 0)   
    {
        if(dNorth < 0)
        {
            a = Math.PI;
        }
    }
    else
    {
        a = -Math.Atan(dNorth / dEast) + Math.PI / 2;
    }
    if(dEast < 0)
        a = a + Math.PI;
    return a * 180.0 / Math.PI;    // Convert from radians to degrees
}
Back to article


Listing Seven
// An application that shows direction and distance from the current
// position to a saved position using the previous samples

private double m_latitude;
private double m_longitude;
// Should be called by the serial port handler.
private void OnSerialData(string data)
{
    string[] fields = Parse(data);
    // Parse all sentences in data
    while(fields != null)
    {
        if(fields[0] == "$GPRMC")
        {
            if(fields[2] == "A")
            {
                // Fix valid
                m_latitude = Nmea2DecDeg(fields[3], fields[4]);
                m_longitude = Nmea2DecDeg(fields[5], fields[6]);
            }
        }
        // Support for GLL and GGA should also be implemented
    }
}
private double m_saved_easting;
private double m_saved_northing;
// Should be called by a button handler or similar
private void OnSavePosition()
{
    double zone;
    DecDeg2UTM(m_latitude, m_longitude,
        out m_saved_easting, out m_saved_northing, out zone);
}
// Should be called by a timer or button handler
private void OnFindWay()
{
    double zone, easting, northing;
    DecDeg2UTM(m_latitude, m_longitude, out easting, out northing, out zone);
    double distance;
    distance = Distance(easting, northing, m_saved_easting, m_saved_northing);
    double bearing;
    bearing = Bearing(easting, northing, m_saved_easting, m_saved_northing);
    // Prints distance and bearing to those text boxes
    txtDistance.Text = distance.ToString();
    txtBearing.Text = bearing.ToString();
}
Back to article


Listing Eight
// An application that shows direction and distance from the current
// position to a saved position using GpsTools from franson.biz

private GpsToolsNET.NmeaParser m_parser;
private GpsToolsNET.Position m_saved_position;

// Should be called at startup
private void Init()
{

    m_parser = new GpsToolsNET.NmeaParser();
    m_parser.NoEvents = true;
    m_parser.PortEnabled = true; // Auto detect GPS
}
// Should be called by a button handler or similar
private void OnSavePosition()
{
    GpsToolsNET.GpsFix fix = m_parser.GetGpsFix(2, 0);
    m_saved_position = fix.Position;
}
// Should be called by a timer or button handler
private void OnFindWay()
{
    GpsToolsNET.GpsFix fix = m_parser.GetGpsFix(2, 0);
    GpsToolsNET.Position position = fix.Position;
    double distance = position.Distance(m_saved_position);
    double bearing = position.Bearing(m_saved_position);
    // Prints distance and bearing to those text boxes
    txtDistance.Text = distance.ToString();
    txtBearing.Text = bearing.ToString();
}
Back to article


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.