⚡Geohash
Обычно координаты задаются парой чисел - долготой и широтой. Это позволяет описать любую точку на земле, однако работать с таким представлением весьма сложно (см. например формулу расстояния между двумя точками)
Другим представлением координат является geohash:
1. Плоскость земли делится на 32 участка
2. Каждому участку приписывается определенная буква/цифра из Base32
Мы научились одним символом делить пространство на 32 участка. Чтобы получить бОльшую точность, выбираем один из участков и делаем ту же процедуру
1. Плоскость участка делится на 32 под-участка
2. Каждому под-участку приписывается определенная буква/цифра из Base32
И так далее
---
Точность получается примерно следующая:
1 символ ~ 1000 км2
2 символа ~ 1000 км2 / 32
...
n+1 символов ~ 1000 км2 / 32^n
При n=6 точность будет будет около 1м2
---
Основные плюсы такого представления:
1. Не пара чисел, а одна строка - легче индексировать
2. Если пара точек имеет одинаковый префикс geohash-а, то они находятся в одном участке. Это позволяет очень быстро выполнять запросы на поиск ближайших точек с нужной точностью
3. Можно выбрать любую требуемую для конкретной задачи точность и экономить место на хранение, если скажем точности в 1м2 будет достаточно
---
Идея "Hierarchical Spatial Index", когда пространство делится на большие участки, большие участки делятся на участки поменьше и тд, весьма популярна и используется многими компаниями. Про подход Uber, где они делят пространство на шестиугольники можно почитать здесь
Обычно координаты задаются парой чисел - долготой и широтой. Это позволяет описать любую точку на земле, однако работать с таким представлением весьма сложно (см. например формулу расстояния между двумя точками)
Другим представлением координат является geohash:
1. Плоскость земли делится на 32 участка
2. Каждому участку приписывается определенная буква/цифра из Base32
Мы научились одним символом делить пространство на 32 участка. Чтобы получить бОльшую точность, выбираем один из участков и делаем ту же процедуру
1. Плоскость участка делится на 32 под-участка
2. Каждому под-участку приписывается определенная буква/цифра из Base32
И так далее
---
Точность получается примерно следующая:
1 символ ~ 1000 км2
2 символа ~ 1000 км2 / 32
...
n+1 символов ~ 1000 км2 / 32^n
При n=6 точность будет будет около 1м2
---
Основные плюсы такого представления:
1. Не пара чисел, а одна строка - легче индексировать
2. Если пара точек имеет одинаковый префикс geohash-а, то они находятся в одном участке. Это позволяет очень быстро выполнять запросы на поиск ближайших точек с нужной точностью
3. Можно выбрать любую требуемую для конкретной задачи точность и экономить место на хранение, если скажем точности в 1м2 будет достаточно
---
Идея "Hierarchical Spatial Index", когда пространство делится на большие участки, большие участки делятся на участки поменьше и тд, весьма популярна и используется многими компаниями. Про подход Uber, где они делят пространство на шестиугольники можно почитать здесь