<개요>

- 일반적으로 많이 사용하는 지리좌표계는 위도, 경도로 이루어져있다.

  이는 실제 정확한 위치를 측정하는 것이 목표이기 때문에 소수점 표현에 제한이 없이 무한하게 표현한다. (보통 6자리)

- 특정 영역(Area) 에 대한 처리를 하기에는 적합하지 않기 때문에, 영역기반의 검색/표현에 적합한 구조가 필요하다.

- 즉, (무한->유한) 한정된 공간내에서 필요한 만큼만의 데이터(의미있는 데이터) 를 관리할 수 있도록 개선이 필요하다.

 

<내용>

- 지도뷰를 기반으로 하는 시스템에서 좌표를 기반으로 검색하는 것은 속도/공간에서 많은 손해를 본다. (대부분 특정영역 내 검색)

- 지도내에서 살짝만 움직여도 소수점 값이 변경되는데 실제 서비스내에서 의미를 갖는 값으로 보기 어려울때가 있다.

- 또한 Round처리를 통해서 어느정도 고정적으로 표현할 수는 있으나 연산에 역시 불편함이 있다.

- 지역내 검색이나 가까운 위치 등을 계산할때도 복잡한 수식을 사용해야 하며 Index 나 Key를 사용하기에 쉬운 구조는 아니다.

 

<GeoHash Concept>

전 세계를 잘라내기

- 이를 보완하기 위해서 전 세계 지역을 특정영역 단위로 잘라낸 것이 GeoHash의 기본사상이다.

- 좌표값을 특정 해시값으로 변경하여 지역기반 검색 이나 캐시 활용에서 편리하게 활용 할 수 있다. ( f(x) -> y )

- GeoHash의 결과는 특정 영역(Area) 이다.  지점(Point)이 아니다.

 

<GeoHash Algorithm>

- 알고리즘은 간단히 설명하면 Index Tree, Binary Search등과 비슷하다.

1. Latitude (-90 ~ 90), Longitude (-180 ~ 180) 범위 내에서 Binary Search를 수행한다.

2. 왼쪽에 속하면 0, 오른쪽에 속하면 1 이다. (bits)

3. 다음 구간으로 이동하여 1,2를 반복한다.

Longtitude / Latitude 변환

4. 이렇게 해서 얻은 각 bit를 하나씩 꺼내어 결합한다.

- Geohash level이 높아질 수록 더 자세한 위치를 표현해야 하기 때문에, 더 많은 bit를 필요로 하게 된다.

- latitude 1개, longitude 1개 순으로 번갈아가면서 결합한다.

 (Longitude의 값의 범위가 더 넓기 때문에 Level에 따라서 Bit가 1개 더 필요한 경우가 있고, 이 때 마지막 두 개를 연속해서 붙인다. )

 

5. 마지막으로 얻은 bits를 5개씩 나눠서 BASE32 encoding으로 변환하여 알파벳 문자를 얻을 수 있다. (2^5=32)

BASE32

6. Binary Search를 많이 반복할 수록 더욱 정확한 숫자를 얻게 되고, GeoHash 의 길이는 길어진다고 볼 수 있다.

 - GeoHash Stirng의 길이가 GeoHash Level로 생각하면 된다.

 

7. 위의 연산을 통해서 얻은 결과값은 다음과 같다.

위/경도 좌표 (37.385595, 127.122759) -> Level 2 (wy), Level 8 (wydkstzf)

위/경도 좌표 (37.384887, 127.123689) -> Level 2 (wy), Level 8 (wydksv8w)

 

*장점

- 매우 길고 큰 값을 상대적으로 짧고 저장공간을 적게 차지하는 String으로 바꿀 수 있게 된다. (Hash의 기본사상)

- GeoHash알고리즘의 특성상 prefix비교를 통해서 이웃인지 판별할 수 있다.

 예를 들어서 GeoHash를 통해서 gbsuv (Level 5)값을 얻은경우 아래의 지역들은  Neighbours 로 판별할 수 있다.

gbsvh gbsvj gbsvn
gbsuu gbsuv gbsuy
gbsus gbsut gbsuw

 

<코드>

전체코드는 다음 위치에서 확인 가능합니다.

https://github.com/ggthename/geohash

 

GitHub - ggthename/geohash: get a geohash value from a coordinate (latitude,longitude)

get a geohash value from a coordinate (latitude,longitude) - GitHub - ggthename/geohash: get a geohash value from a coordinate (latitude,longitude)

github.com

위도/경도 기반의 좌표
GeoHash Level에 따른 Binary Search 응용

 

<정리>

- 이를 통해서 특정 지역 내의 데이터값을 관리할때 Key값으로 사용할 수 있다.

 e.g) 특정지역내 위치한 상점 검색, 50 x 50내 인구 등

 

- 해당 지역간의 인접성도 복잡한 계산없이 판별할 수 있다.

 e.g) 현재 위치에서 10km내 이동가능한 곳에 있는 주유소 위치 등

 

- 최대 Level 12로 32.2mm x 18.6mm의 지역까지 표현할 수 있다. 일반적으로 Level 9 까지 사용한다.

 

<참고>

- https://en.wikipedia.org/wiki/Geohash#Technical_description

 

Geohash - Wikipedia

From Wikipedia, the free encyclopedia Jump to navigation Jump to search This article is about the system for encoding geographic coordinates. For the game, see Geohashing. Public domain geocoding invented in 2008 Geohash is a public domain geocode system i

en.wikipedia.org

- https://en.wikipedia.org/wiki/Base32

 

Base32 - Wikipedia

From Wikipedia, the free encyclopedia Jump to navigation Jump to search Binary-to-text encoding scheme using 32 symbols Base32 is the base-32 numeral system. It uses a set of 32 digits, each of which can be represented by 5 bits (25). One way to represent

en.wikipedia.org

https://www.movable-type.co.uk/scripts/geohash.html

 

Geohash encoding/decoding

Movable Type Scripts Geohashes A geohash is a convenient way of expressing a location (anywhere in the world) using a short alphanumeric string, with greater precision obtained with longer strings. A geohash actually identifies a rectangular cell: at each

www.movable-type.co.uk

 

+ Recent posts