Немного геохэшей в Go

Широта и долгота как строка, сохраняющая местоположение

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

Geohash кодирует долготу и широту в простой URL-безопасной строке для geohash.org. Они интересны тем, что два геохэша с одинаковым префиксом довольно близки друг к другу. Например, на площади Александерплац в Берлине геохеш u33dc1r4. Рядом с Бранденбургскими воротами есть геохэш u33db2jx — обратите внимание на общий префикс u33d.

Кстати, я раньше не программировал на Go и просто запускал hello world. Я не собирался оставлять эту аллитерацию на столе!

Что такое геохеш?

Geohash кодирует широту и долготу в строку цифр и букв. Он закодирован по основанию 32, поэтому использует 32 возможных символа: 10 цифр 0–9 и 22 буквы az, исключая a, i, l и o.

Например, геохеш солнечный расшифровывается как 23,7 42,5 или 23°42.000' северной широты 42°30.000' в Саудовской Аравии. Большинство геохэшей не такие запоминающиеся слова, но если вам скучно, вы можете проверить, где слова или имена находятся в географическом положении. Мое имя находится недалеко от побережья Мадагаскара.

Для читателей с географическими проблемами, таких как я: при выражении в десятичных дробях положительная широта находится к северу от экватора, а отрицательная - к югу. Широта колеблется от -90° до 90° на южном и северном полюсах соответственно. Положительная долгота — это восток от нулевого меридиана (через Гринвич, Великобритания), а отрицательная — запад. Долгота колеблется от -180° до 180°. В старой доброй Британской энциклопедии есть несколько симпатичных визуализаций.

Как мы увидим, геохеши по построению обладают несколькими интересными свойствами.

Два геохэша с общим префиксом имеют близкие координаты.
Чем длиннее геохэш, тем он точнее. Более длинные геохэши описывают меньшие регионы.
Геохэш, добавляющий символы к другому геохешу, является субрегионом этого геохеша.

С другой стороны, НЕ обязательно, чтобы два соседних местоположения имели общий префикс geohash. Вокруг экватора, нулевого меридиана и полюсов близлежащие места могут иметь совершенно разные широты и долготы, что приводит к разным геохэшам.

Кривые Z-порядка

Geohash отображает широту и долготу на кривой z-порядка. Кривая z-порядка — это общее отображение двумерной координаты в одномерную координату — точку на линии. Отображение сохраняет локальность: если две 2D-координаты близки, их 1D-координаты также близки. Кривые Z-порядка — это особый тип кривой, заполняющей пространство: кривая, диапазон которой содержит весь двумерный квадрат. Проще говоря: непрерывная линия через таблицу, которая проходит через все ячейки таблицы один раз.

Кривые Z-порядка построить просто: чередуйте биты координат x и y, чтобы получить одномерную координату. Если вы расположите свои оси правильно, это создаст рекурсивную Z-образную кривую в 2-мерной плоскости:

Таблица имеет координаты x 0–3 по горизонтали вверху и координаты y по вертикали слева. Пунктирная линия показывает результирующий z-порядок, начиная с верхнего левого угла.

Кривые Z-порядка могут быть обобщены более чем на два измерения и полезны, когда многомерные данные необходимо размещать последовательно, как правило, из соображений производительности. Примеры:

Индексы базы данных для местоположений. Позволяет искать близлежащие местоположения, ища похожие префиксы.
Макет текстурных карт в памяти в графических процессорах. Оптимизирует структуру памяти, чтобы уменьшить промахи кэша.
Эффективное матричное умножение для уменьшения промахов кэша.

Расшифровка геохэша

Во-первых, давайте попробуем расшифровать заданный геохэш до широты и долготы.

Простая часть — найти битовое представление строки геохэша, например «gbsuv». Поскольку геохеш использует кодировку base-32, каждый символ соответствует 5 битам. Все, что нам нужно, это константа, содержащая допустимые символы. Индекс символа в строке содержит интересующие нас 5 бит:

const base32 = "0123456789bcdefghjkmnpqrstuvwxyz" 

c := strings.IndexRune(base32, letter)

Теперь, как обработать эти биты в широту и долготу?

Во-первых, мы знаем, что геохеш представляет собой кривую z-порядка, поэтому его биты чередуются по долготе и широте. Четные биты геохеша — это долгота, нечетные — широта.

Во-вторых, геохэш не описывает точное местоположение. Координата, которую возвращает geohash.org, на самом деле является серединой прямоугольной области. Прямоугольник в кавычках, потому что это прямоугольник, спроецированный на сферу — на полюсах это треугольник! Область может быть описана минимальной и максимальной долготой и широтой для двух углов прямоугольника.

Вот анимация того, как 10 бит сходятся во все меньшей и меньшей области (выделены оранжевым цветом) — каждый бит перемещает один из углов:

Пустой геохеш представляет всю Землю. Первый бит определяет, находится ли местоположение в восточном или западном полушарии. Второй бит определяет, находится ли область в северном или южном полушарии — через два бита мы знаем, в каком квадранте Земли находится местоположение. Каждый бит примерно делит регион дальше пополам, вдоль с востока на запад или с севера на юг.

Чем длиннее геохеш, тем меньше регион. Чтобы откалибровать вашу интуицию, геохэш из 8 символов описывает область размером 40 м на 40 м.

Вот код Go для декодирования геохеша:

const latMin, latMax = -90.0, 90.0
const lonMin, lonMax = -180.0, 180.0

func decode(geohash string) (lat, lon float64) {
    curMinLat, curMaxLat := latMin, latMax
    curMinLon, curMaxLon := lonMin, lonMax
    bitIsLongitude := true

    // loop through each character in the geohash from left to right
    for _, character := range geohash {

        // decode the base32 representation
        nibblebit := strings.IndexRune(base32, character)

        // each character represents 5 bits
        for b := 4; b >= 0; b-- {
            // get the bit at position b
            bit := nibblebit & (1 << uint(b))
            if bitIsLongitude {
                if bit == 0 {
                    curMaxLon = (curMinLon + curMaxLon) / 2
                } else {
                    curMinLon = (curMinLon + curMaxLon) / 2
                }
            } else {
                if bit == 0 {
                    curMaxLat = (curMinLat + curMaxLat) / 2
                } else {
                    curMinLat = (curMinLat + curMaxLat) / 2
                }
            }
            bitIsLongitude = !bitIsLongitude
        }
    }

    // we now have a region - return the midpoint
    return (curMinLat + curMaxLat) / 2, (curMinLon + curMaxLon) / 2
}

Кодирование геохэша

Аналогичным образом работает кодирование геохэша по широте и долготе.

Мы снова начинаем с области, которая охватывает всю Землю. Сначала мы определяем, находится ли долгота в западном или восточном полушарии, и добавляем 0 или 1 соответственно. Затем мы смотрим на широту, чтобы определить следующий бит, снова деля регион пополам.

func encode(lat, lon float64, precision int) string {
    var geohash []rune

    if precision > 12 {
        precision = 12
    }

    curMinLat, curMaxLat := latMin, latMax
    curMinLon, curMaxLon := lonMin, lonMax
    bitIsLongitude := true
    nibblebit_idx := 4
    nibblebit := 0

    for len(geohash) < precision {

        if bitIsLongitude {
            mid := (curMinLon + curMaxLon) / 2
            if lon > mid {
                nibblebit |= 1 << uint(nibblebit_idx)
                curMinLon = mid
            } else {
                curMaxLon = mid
            }
        } else {
            mid := (curMinLat + curMaxLat) / 2
            if lat > mid {
                nibblebit |= 1 << uint(nibblebit_idx)
                curMinLat = mid
            } else {
                curMaxLat = mid
            }
        }
        bitIsLongitude = !bitIsLongitude

        nibblebit_idx--
        if nibblebit_idx == -1 {
            // we have a full base32 character
            geohash = append(geohash, rune(base32[nibblebit]))
            nibblebit_idx = 4
            nibblebit = 0
        }
    }

    return string(geohash)
}

Лежачий полицейский заключался в том, что я не понимал, когда остановиться — каждую область можно делить дальше пополам навсегда (пока вы не достигнете предела точности с плавающей запятой). Чтобы исправить это, я добавил аргумент precision, чтобы указать количество символов, которое должен иметь результирующий геохэш.

это обертка

На этом геохэши и кривые z-порядка заканчиваются. Кривые Z-порядка будут полезны для создания деревьев квадрантов, структуры данных с дальнейшими приложениями географической и компьютерной геометрии. Я расскажу о деревьях квадрантов в следующем фрагменте, так что следите за обновлениями.

Примечание о Go: я понимаю, почему он популярен. Он сразу показался знакомым и позволил избежать нелепого взрыва функций, накопленных некоторыми другими языками. Мне также нравится, что он собирает мусор. Сборщик мусора идеально подходит для множества приложений, возьмите его от Джона Кармака!

Спасибо за прочтение! Я пишу кусочек (или два) каждый месяц. Чтобы узнать больше, подпишитесь на мою рассылку и следите за мной в Twitter или Mastodon.

Ссылки и благодарности

Геохэш.орг
Кодировать и декодировать геохеши в браузере и ссылаться на код JavaScript
CoPilot GitHub сгенерировал много кода Go. Памятные случаи: я набрал base32, и он заполнил константы. Я набрал decode(geohash, и он частично заполнил функцию decode, включая описание алгоритма. В коде было несколько ошибок и проблем.
Иллюстрации созданы совместно с Маним комьюнити.

Первоначально опубликовано наhttps://getcode.substack.com.