Tuesday, July 6, 2010

Where am I? The 10:10 code...

A couple months ago, I came across a blog post discussing an encoding of geographic coordinates that might be "easier" to remember or exchange than latitude/longitude pairs.

The encoding, known as "10:10", is able to identify to a 10 meter precision any location on the planet using a 10 character code. Without going into the merits of the scheme, I will just note that there is some good discussion in the comments section about ideas for its improvement.

Under the assumption that most programming blog posts are invitations to port things into Factor, I decided to implement the 10:10 code. Unfortunately, the provided Javascript code uses relatively meaningless variable names, so my implementation suffers via inheritance. Essentially, the code boils down into a couple steps:

  1. Calculate a single p number representing a latitude/longitude pair.
  2. Calculate a tt number representing a version of p modified by a checksum.
  3. Generate a 10:10 code by iteratively indexing into the alphabet.

We will separate each of these steps into words that can be tested individually and then combined to compute the 10:10 codes.

We will need some vocabularies and a namespace:

USING: kernel math math.functions math.ranges memoize sequences
strings ;

IN: ten-ten

The 10:10 code uses a 29 character alphabet, so we will need to define it:

CONSTANT: ALPHABET "ABCDEFGHJKMNPQRVWXY0123456789"

MEMO: BASE ( -- base ) ALPHABET length ;

First, we compute the p value:

: p ( lat lon -- p )
    [ 90 + ] [ 180 + ] bi*
    [ 10000 * floor >fixnum ] bi@
    [ 3600000 * ] dip + ;

Then, we calculate and add the checksum to create a tt value:

: tt ( p -- tt )
    [ BASE * ] keep 10 [1,b) [
        [ BASE /mod ] dip *
    ] map nip sum BASE mod + floor ;

Next, we convert the tt value to a string (inserting spaces for legibility):

: tt>string ( tt -- str )
    10 [ BASE /mod ALPHABET nth ] replicate 
    nip reverse >string
    [ CHAR: \s 3 ] dip insert-nth
    [ CHAR: \s 7 ] dip insert-nth ;

And, finally, putting it all together:

: ten-ten ( lat lon -- tt )
    p tt tt>string ;

When I run 51.09559 1.12207 ten-ten (the included example for the location of the Eurotunnel in the UK), it gives me a value of MEQ N6G 7NY5. This is not the same as the original author, but matches a version written in C# by another commenter as well as a version I wrote in Python to validate my results.

You can find my implementation on my Github account.

No comments: