По договоренности
Необходимо реализовать алгоритм преобразования, который принимает долготу и широту и преобразовывает их в одну строку – их хэш. При этом должно выполняться условие, что чем ближе друг к другу на карте находятся географические точки, тем ближе друг к другу по алфавиту будут находиться их хэши. Иными словами, если у меня будет список точек и я отсортирую их по их хэшам, то используя поиск хэша нужной точки (и, возможно, нескольких соседних) в этом массиве, я смогу найти все точки, находящиеся рядом с ней, за логарифмическое время. Такое хэширование предполает разбивку сферы на множество равносторонних треугольников разного размера, каждый из которых соответсвует своему хэшу. Чем длиннее хэш – тем меньше треугольник и тем точнее указана координата.
Нужно реализовать три функции на питоне:
1) создание хэша из координат (принимает x, y, radius) и возвращает хэш треугольника в котором находится точка (x,y), такого что сторона треугольника L удовлетворяет условию L <= radius < 2L. Радиус указывается в метрах.
2) создание координат из хэша (принимает hash) и возвращает x,y центра треугольника с таким хэшем и его длину стороны.
3) поиск. Принимает координату x,y и сторону треугольника. Возвращает массив из хэшей, среди которых первый – хэш этой координаты (функция 1), а ещё 12 – хэши всех соседних с ним треугольников (по стороне или вершине).
Алгоритм разбивки на треугольники следующий:
Вся поверхность сферы разбивается на треугольники. Сперва на 12 больших (по 6 в каждом полушарии, линиями из полюсов к экватору). Затем рекурсивно каждый треугольник разбивается на 4 меньших (по медианам). Хэш формируется следующим образом: первый символ полушарие + северное, – южное. Затем число от 0 до 5 – соответствуют треугольникам 0-60 грабусов долготы, 60-120 градусов и.т.д. Затем для каждого из подтреугольников добавляется один из символов <^>* где <> – левый или правый меньший трегольник, ^ – верхний или нижний, а * – центральный. Таким образом адрес треугольника выглядит примерно так +1<<>**^*>^. Каждый раз размер треугольника уменьшается вдвое и что бы достичь точности в 1 км нужно 15 символов. Для точности в 1 метр 25 символов и.т.д. Так же нужно написать функции для сжатия/расшифровки этих хэшей. При сжатии они укорачиваются с использованием base64 (каждые три символа превращаются в один, лишние остаются без изменений), при расшифровке – возвращается как было.