What's the fastest C++ class or C library to convert latitude and longitude from decimal degrees to string and back

Question

I'm looking for the best C or C++ code to encode and decode decimal latitude and longitude values from/to double/char. I'd prefer the code convert from double to char[] and vice-versa rather than c++ strings.

If you have a code snippet that would be great too.

To clarify: I need to convert from a string Degrees/Minutes/Seconds to double and back to string. I have 300 million records, so speed is a big concern.

See: http://en.wikipedia.org/wiki/Geographic_coordinate_conversion

Answer 1

Working with the OP(amanda) via email, we've developed a fast function based on a large switch-case statement.

amanda reports that is runs somewhere around 15x faster than the code they had been using.
Considering this is run over 300 million records, that should be a pretty substantial time savings.

I found the problem to be very interesting.

Here is the code:

/* WARNING:  These values are very important, as used under the "default" case. */
#define INT_PART 3
#define DEC_PART 2

double Str2LatLong(char* coord)
//double LLStr::Str2LL(char* coord)
{
    int sign = +1;
    double val;

    int i = 0;  /* an index into coord, the text-input string, indicating the character currently being parsed */

    int p[9] = {0,0,1,  /* degrees */
                0,0,1,  /* minutes */
                0,0,1   /* seconds */
               };
    int* ptr = p;   /* p starts at Degrees. 
                       It will advance to the Decimal part when a decimal-point is encountered,
                       and advance to minutes & seconds when a separator is encountered */
    int  flag = INT_PART; /* Flips back and forth from INT_PART and DEC_PART */

    while(1)
    {
        switch (coord[i])
        {
            /* Any digit contributes to either degrees,minutes, or seconds */
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                *ptr = 10* (*ptr) + (coord[i] - '0');
                if (flag == DEC_PART)  /* it'd be nice if I could find a clever way to avoid this test */
                {
                    ptr[1] *= 10;
                }
                break;

            case '.':     /* A decimal point implies ptr is on an integer-part; advance to decimal part */
                flag = DEC_PART; /* after encountering a decimal point, we are now processing the Decimal Part */
                ptr++;  /* ptr[0] is now the Decimal piece; ptr[1] is the Denominator piece (powers of 10) */
                break;

            /* A Null terminator triggers return (no break necessary) */
            case '\0':
                val = p[0]*3600 + p[3]*60 + p[6];             /* All Integer math */
                if (p[1]) val += ((double)p[1]/p[2]) * 3600;  /* Floating-point operations only if needed */
                if (p[4]) val += ((double)p[4]/p[5]) *   60;  /* (ditto) */
                if (p[7]) val += ((double)p[7]/p[8]);         /* (ditto) */
                return sign * val / 3600.0;                 /* Only one floating-point division! */

            case 'W':
            case 'S':
                sign = -1;
                break;

            /* Any other symbol is a separator, and moves ptr from degrees to minutes, or minutes to seconds */
            default:
                /* Note, by setting DEC_PART=2 and INT_PART=3, I avoid an if-test. (testing and branching is slow) */
                ptr += flag;
                flag = INT_PART; /* reset to Integer part, we're now starting a new "piece" (degrees, min, or sec). */
        }
        i++;
    }

    return -1.0;  /* Should never reach here! */
}

Answer 2

Here's the code I developed:

double Str2LatLong(char* coord)
{
    // char* testInput = "47,26'14\"";

    int i = 0;
    int parts[3] = {0};  // parts[0] is degrees, parts[1] is minutes, parts[2] is seconds
    int* pCurr = parts;

    do
    {
        if (coord[i] == '\0')
        {
            break;
        }
        if (!isdigit(coord[i]))
        {
            *pCurr++; // skip from parts[0] ==> [1], or [1] ==> [2]
            continue;
        }
        *pCurr = 10* (*pCurr) + coord[i] - '0';
        ++i;
    } while (1);

    return parts[0] + ((double)parts[1])/60.0 + ((double)parts[2])/3600.0;
}

Because it is written for speed, there is NO input validation.
You must supply proper input, or it will mess up badly.

I kept everything to integer math, and sequential memory as best I could.
It doesn't check for "proper" delimiters. Rather, anytime something is not a digit, it assumes that is the transition from degrees to minutes, or minutes to seconds.

It is only at the very last line that it converts to double with some very simple floating point operations.

I suspect you'll want to modify it to handle positive/negative values and North/South, East/West indicators, and decimal places after the seconds. But I think this code is a good foundation for a really fast conversion routine.

I hope this will test out very fast. Please let me know how it goes.

Answer 3

C++ strings and streams are very much a good idea, but if you absolutely can't use them, the following code might be useful. The first function writes the two doubles into an existing C string. The second function reads two doubles out of an existing C string and returns them by pointer:

void CoordinatesToString(double lat, double long, char *buffer, size_t len) {
    assert(buffer != NULL);
    assert(len > 0);

    snprintf(buffer, len, "%f, %f", lat, long);
    buffer[len - 1] = 0; /* ensure null terminated */
}

int StringToCoordinates(const char *string, double *outLatitude, double *outLongitude) {
    assert(string != NULL);
    assert(outLatitude != NULL);
    assert(outLongitude != NULL);

    return (2 == sscanf(string, "%f, %f", outLatitude, outLongitude));
}

Usage:

char buffer[128];
CoordinatesToString(90.0, -33.0, buffer, 128);

double lat, lng;
if (StringToCoordinates(buffer, &lat, &lng)) {
    printf("lat: %f long %f\n", lat, lng);
}

BUT. C++ strings are designed for this sort of use. They don't suffer from potential overflow problems inherent to char arrays, and you don't have to manually manage their memory--they resize to fit their contents as needed. Is there a reason why you want to avoid std::string when you say you're otherwise okay with a C++ solution?

Answer 4

Here's another variation.

The logic is the same, but it uses a switch-case statement for better organization, fewer break/continue statements, and a faster return.

You should also be able to enhance this one with

case 'N':
case 'S':
case 'E':
case 'W': 

as needed.

double Str2LatLong(char* coord)
{
    // char* testInput = "47,26'14\"";

    int i = 0;
    int parts[3] = {0};
    int* pCurr = parts;

    while(1)
    {
        switch (coord[i])
        {
            /* Any digit contributes to either degrees,minutes, or seconds (as *pCurr) */
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                *pCurr = 10* (*pCurr) + coord[i] - '0';
                break;

            /* A Null terminator triggers return (no break necessary) */
            case '\0':
                return parts[0] + ((double)parts[1])/60.0 + ((double)parts[2])/3600.0;

            /* Any other symbol moves pCurr from degrees to minutes, or minutes to seconds */
            default:
                *pCurr++;
        }
        i++;
    }

    return -1.0;  /* Should never reach this point! */
}

Answer 5

The hard part is going to be representing all the format variations with a single grammar. Once you do, you can use a lexer generator tool to spit out a highly optimized DFA that will be competitive with the best hand-tuned code.