У меня есть блоки данных, связанные со значениями широты/долготы. Я хотел бы создать ключ поиска/хеш-значение из значения широты/долготы, чтобы его можно было использовать для поиска на карте или что-то подобное.
Я использую отрицательные значения для запада и юга... поэтому 5W, 10S представлены в программе как -5, -10.
Я хотел бы иметь возможность вернуть значения широты/долготы из значения ключа, если это возможно.
Производное значение ДОЛЖНО быть целым числом.
Я использую С/С++ :)
Спасибо, буду рад ответить на любые вопросы!
Насколько большим (в байтах) может быть ваш хеш-выход? jheddings 08.11.2009
почему бы не использовать std::map. Требуется только определение оператора ‹ Martin York 08.11.2009
бла... Мартин, это, вероятно, сработает :) Иногда вам нужен кто-то еще, чтобы показать вам, что вы не руководствуетесь здравым смыслом Polaris878 08.11.2009
Вы также можете красиво закодировать его в 64-битное целое число, используя некоторые манипуляции с битами.
долгота колеблется от -180 до 180, поэтому требуется минимум 9 бит. широта колеблется от -90 до +90, поэтому требуется минимум 8 бит. минуты идут от 0 до 60, поэтому требуется 6 бит. то же самое на секунды.
9+12 = 21 бит для долготы и 20 бит для широты.
Для точности до доли секунды вы можете использовать 11-битную фиксированную точку. это дает вам точность до 2048-й секунды.
SO для хранения долготы или широты вы можете использовать структуру следующим образом
struct ALatLong
{
int angle:9;
int minutes:6;
int seconds:6;
int subSeconds:11;
};
struct LatAndLong
{
ALatLong longitude;
ALatLong lattitude;
};
Ответ 2 · рейтинг 5 · mjv
На самом деле вы не ищете хэш (хэши обычно разбрасывают базовые ключи, а также допускают коллизии).
Вместо этого, я думаю, поможет простая формула, подобная следующей, и она обратима.
[pseudo code]
Precision = 100 // lat and long precsion, boost to 1000 if need be
LatOffset = 1000 // Anithing above 180 would do
Key = ((int)(Lat * Precision) * LatOffset) + (int)(Long * Precision)
Чтобы изменить
Long = (Key Modulo (LatOffset * Precision)) Div Precision
Lat = (Key Div (LatOffset * Precision)) Div Precision )
Редактировать: К сожалению, я не заметил, что это было в C. Действительно, используйте решение jheddings (или его вариант (с требованием, чтобы ключ "хеш" был целым числом).
Ответ 3 · рейтинг 2 · jheddings
Как указал mjv, хэш обычно запутывает исходные входные данные. Вместо этого это звучит так, как будто вы просто хотите объединить значения.
Чтобы упростить задачу, вы можете просто определить новый тип для своего "хэша":
typedef struct {
float lat;
float lon;
} latlon;
Вы можете рассматривать это как 64-битное число. И используйте его как таковой:
float lat = -5.432;
float lon = 10.3423;
latlon pair = {
.lat = lat,
.lon = lon,
};
Ответ 4 · рейтинг 2 · Jeremy Friesner
Вы на 100% уверены, что хеширование здесь уместно? Поиск по хешу работает только в том случае, если вы знаете точное значение искомого ключа, а значения широты/долготы (AFAIK) не всегда точно известны.
Например, скажем, у вас есть запись, хранящаяся под ключом (-5,432, 10,3423), и кто-то еще хочет знать, какие записи хранятся в радиусе 1,0 от (-5,0, +10,0). Или, возможно, они хотят найти запись, но из-за округления с плавающей запятой в их вычислениях они имеют (-5,431999, 10,3423001) в качестве значения ключа. Хеширование не может помочь вам в этих случаях. Чтобы выполнить такой пространственный/неточный поиск, вам, вероятно, лучше использовать более специализированную структуру данных, такую как октодеревья (или их двумерный эквивалент).
Ответ 5 · David Seiler
Тривиальное решение: сделать хеш-ключ из пары широта/длина и хешировать его. Тогда, если у вас есть ключ, по определению у вас есть координаты. Хэш-ключи довольно компактны, например. восемь байтов, если каждое значение координаты является 32-битным целым числом.
