преобразование координат с использованием таблицы поиска

Question

У меня есть приложение, которое считывает данные координатной сетки со значениями (т. Е. Широта, долгота, значение) и затем отображает эти данные на карте.Нарисованная карта использует конформную коническую проекцию Ламберта, и поэтому все данные координат должны быть преобразованы из широты / долготы в восток / север.Все это прекрасно работает, однако при чтении в нескольких файлах данных возникает заметная проблема с производительностью.Поскольку все файлы данных содержат одинаковый набор точек (хотя и не обязательно в одном и том же порядке), я думаю, что какая-то таблица поиска будет полезна для преобразования координат.Однако я никогда раньше не использовал таблицы поиска и испытываю некоторые затруднения при расчете дизайна.

В двух словах - любые предложения по быстрому способу выбора пары координат широта / долгота (значения с плавающей запятой) и поискасоответствующая пара E / N (значения с плавающей запятой), при условии, что между парами координат существует отношение 1: 1, нет пропущенных значений и т. д.

Поскольку значения широта / долгота являются значениями с плавающей запятой, я не могу использовать их какиндексы массива (например: lookup_array [lat] [lon]), очевидно, именно здесь я и получаю наибольшее количество срабатываний.

Примечание: это решение может быть на C или C ++, в зависимости от того, что имеет оптимальное значение.решение.

Answer 1

Техника, которую вы хотите использовать, называется памятка .В вашем случае хеш-таблица кажется хорошим кандидатом для справочной таблицы .C ++ 11 имеет стандартный ассоциативный контейнер на основе хеша, который называется std::unordered_map.Существуют реализации для C ++ 03;Например, более ранние версии GCC и MSVC имеют std::tr1::unordered_map.Вам необходимо создать (или найти) хорошую хеш-функцию, преобразующую координаты в хеш-значение (см. Предложение Йохана Лундберга в комментариях ниже).

Ассоциативный контейнер на основе сравнения, например std::map, также подойдет, хотя может быть заметно медленнее, когда количество элементов достаточно велико.

Answer 2

Возможно, вы сможете выполнить интерполяцию вместо прямого поиска.Рассчитайте отображение для некоторой регулярной сетки долготы и широты, которая покрывает всю поверхность карты.Когда вы получаете пару широта / длинная, вы ищите четыре точки в сетке, которые окружают эту точку, и используете линейную интерполяцию, чтобы получить более точное значение.

Answer 3

Поскольку пространство возможных длин / длин велико, я не думаю, что целесообразно построить всю таблицу заранее. Однако вы можете помнить результат каждого преобразования в (скажем) хэш-таблице. Затем каждый раз, когда вы делаете преобразование, вы сначала проверяете, есть ли оно в таблице. Если это не так, вы выполняете вычисления и сохраняете их в хэш-таблице в следующий раз.

Тем не менее, не рекомендуется использовать числа с плавающей запятой в качестве ключей в любой структуре данных на основе поиска ( см. Этот вопрос ). В случае данных lat / long, если ваш ввод в согласованном формате, вы могли бы избежать этой проблемы, используя строки в качестве ключей (а если это не так, то вы могли бы использовать sprintf() или подобное, чтобы сделать лат / длинная строка в согласованном формате до заданной точности).

Если вам нужна готовая реализация хеш-таблицы для C ++, посмотрите std::unordered_map и эту статью в Википедии.