ABOUT ME

-

인기 태그


kafka elastic_search redis
Today
-
Yesterday
-
Total
-
  • Geohash
    개발하면서/Algorithm,DS,PS 2014. 6. 27. 17:29
    반응형

    http://en.wikipedia.org/wiki/Geohash

    http://geohash.org/site/tips.html

     

    어느 DB 프로젝트 issue를 보다가 GeoHash dataType 지원할 생각은 없냐는 글을 봤다.

    GeoHash? 처음 들어보는 hash다... 공부해보자.

    공부라고 해봤자 wiki를 내 나름대로 정리하자는 거지 뭐...


    Geohash의 근간(?)이 되는 알고리즘은 1966년에 G.M. Morton 개발되었다고 한다.
    간단히 살펴보면
    지구를 커다란 네모로 보고 4등분을 한다. 그리고 나뉜 사각형 각각에 2개 비트를 할당한다. 00~11 총 4개

    4개로 나뉜 사각형을 다시 한번 4등분 한다. 이때 첫 번째로 나누었을 때 비트는 두 번째, 첫 번째 비트에 값이 세팅되고
    두 번째로 나눈 비트는 네 번째, 세 번째 비트에 값을 세팅한다.

    위 과정을 반복하면 네모 한칸의 크기는 작고 위경도를 좀 더 정확하게 표현한다.

    이렇게 2차원을 구간 나눈뒤 모든 구간을 한붓 그리기(?)로 지나가면 1차원으로 표현한다고 생각하면 될듯하다.


    https://en.wikipedia.org/wiki/Z-order_curve

    하지만 가독성이 좋지 않아 널리 쓰이진 않았다고 한다. :cry:

    이후 G. Niemeyer가 2000년 후반에 base32로 표현하도록 다시 개발했고, 2008년 위/경도를 short url(geocode)로 표현할 수 있는
    geohash.org 웹서비스를 개발하면서 GeoHash는 유명해졌다.
    1966년에 만들어진 건 사각형을 4등분, 2008년에 나온 Geohash는 32등분, 차이만 있을 뿐 방식은 비슷하다.

     

    가까운 두 점이라도 Geohash값은 전혀 다른 값이 나올 수 있다. 위에서는 비슷하다고 해놓고 전혀 다른 값이 나온다고??

    그 이유는 본초 자오선과 적도를 경계로 인접한 지역들은 Geohash를 구할 때 상위 비트 값이 달라서 전혀 다른 값이 나온다.
    ※ Geohash 구하는 방법은 아래 더 설명합니다.

     

    예로 적도가 지나가는 인도네시아를 보면 위치는 비슷하지만 Geohash는 전혀 다른 값이 나온다.

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

     

    latitude 위도, longitude 경도

    위도는 적도를 기준으로 북 90, 남, 90이라 하고, 경도는 본초자오선(처음 들어봄..)을 기준으로 동경 180, 서경 180이라 한다.

    Equator 적도, Meridian 자오선

     

    위/경도를 Geohash로 변환하기 위해 어떻게 진행되는지 알아보자

    위도는 42.605이고 경도는 -5.603라고 가정하고 Geohash 변환하는 첫 번째 단계는 비트로 바꾸는 단계이다.

    마치 스무고개를 하듯이 범위를 주고 아래 그림 기준 왼쪽이면 비트는 0, 오른쪽이면 비트 1을 부여한다.

    위도는 -90 ~ 0 ~ +90 범위로 시작하고 경도는 -180 ~ 0 ~ 180으로 시작한다.

     

    위도 bit변환 과정

     

    ※ Geohash값에서 위/경도를 구할때는 소수점 둘째나 셋째에서 반올림해준다.
    위도 42.605 위 규칙을 적용하면 "101111001001"가 되고 경도 -5.603는 "0111110000000"가 된다.

    경도를 시작으로 경도, 위도 비트 하나씩 섞는다. 마치 카드 섞는 것처럼

    출처:http://theknaveofclovers.tumblr.com/post/41608490725/card-shuffle

     

    합친 비트는 "0110111111110000010000010" 이고 이를 5비트씩 나누면 "01101 11111 11000 00100 00010" 가 된다.
    아래 표를 참고해서 base32 값으로 바꾸면 ezs42라는 Geohash값이 나온다.

    특징으로는 구하는 방법이 쉽고 직관적이며 주변 Geohash cell 구하는 방법이 쉽다는 점과
    지구는 타원형이기 때문에 위/경도에 따라 Geohash cell 면적이 다르다는 점이 있다.


    C로 구현한 게 있는데 궁금하신 분은 보면 좋을 것 같다.

    https://github.com/lyokato/libgeohash

     

    참고로 서울 GeoHash는 wydm99uq이다.

    http://geohash.org/wydm99uq

    반응형

    댓글 0

Designed by Tistory.