coordinate conversion using lookup table

Question

I have an application which reads in gridded coordinate data with values (i.e. lat, lon, value) and then plots this data on a map. The map that is drawn uses a lambert conformal conic projection and therefore all the coordinate data has to be converted from lat/lon to easting/northing. This all works great, however there is a noticeable performance issue when reading in several data files. Since all the data files contain the same set of points (although not necessarily in the same order) I'm thinking some sort of lookup table would be useful for the coordinate conversions. However I've never used lookup tables before and am having some trouble figuring out the design.

In a nutshell - any suggestions on the fastest way to take a lat/lon coordinate pair (float values) and look up the corresponding E/N pair (float values) assuming there is a 1:1 relationship between the coordinate pairs, no missing values, etc?

Since the lat/lon are float values I can't use them as array indices (ex: lookup_array[lat][lon]) obviously so this is really where I'm getting the most tripped up.

Note: this solution can be in either C or C++, whichever has the optimal solution.

@DanielFischer, good question, because if it is, a simple table is table[int(factor*lat),int(factor*lon)]=value. if it's not evenly spaced you may replace factor with a function — Johan Lundberg, Jan 26 '12 at 09:08
Well, then if you have enough space, `lookup[round((x-xoff)/step)][round((y-yoff)/step)]` is the simplest. — Daniel Fischer, Jan 26 '12 at 14:27

Alexey Kukanov · Answer 1 · 2012-01-26T11:18:04.647

2

The technique you want to employ is called memoization. For your case, a hash table seems to be a good candidate for the lookup table. C++11 has a standard hash-based associative container called std::unordered_map. There exist implementations for C++03; e.g. earlier versions of GCC and MSVC have std::tr1::unordered_map. You would need to create (or find) a good hash function converting the coordinates into a hash value (see a suggestion from Johan Lundberg in the comments below).

A comparison-based associative container, e.g. std::map, will also fit, though it can be noticeably slower when the number of elements is big enough.

edited Jan 26 '12 at 11:18

answered Jan 25 '12 at 23:03

Alexey Kukanov

12,479
2
36
55

+1. For a hash value just use something like lat + pi*(2+lon) and make sure 0<=lat<=pi and lon >0. Either make a class with that hash, or just use an (unordered) map with that value (a double) as key. – Johan Lundberg Jan 26 '12 at 11:02

score 1 · Accepted Answer · edited May 23 '17 at 11:56

Because the space of possible lat/longs is large, I don't think it's feasible to build the whole table beforehand. However, you could remember the result of each transformation in (say) a hash table. Then each time you go to make a transformation, you first check to see if it's in the table. If it isn't, you do the calculation and store it in the hash table for next time.

However, it's not a good idea to use floats as keys in any lookup based data structure (see this question). In the case of lat/long data, if your input is in a consistent format, then you could avoid this problem by using strings as keys (and if it isn't, then you could use sprintf() or similar to make a lat/long string in a consistent format down to a given precision).

If you'd like an out of the box hash table implementation for C++, have a look at std::unordered_map and this wikipedia article.

score 1 · Answer 3 · answered Jan 25 '12 at 23:46

You might be able to do an interpolation instead of a direct lookup. Calculate the mapping for some regular grid of longitude and latitude that covers the entire surface of the map. When you get a lat/long pair you look up the four points in the grid that surround that point, and use linear interpolation to get a more precise value.

coordinate conversion using lookup table

3 Answers3