공간정보와 인터넷지도

지오해시(geohash)는 Gustavo Niemeyer가 개발하여 퍼블릭 도메인으로 공개한 지오코딩(geocoding) 시스템이다. 지오해시는 공간을 그리드 형태로 분할하는 계층적 공간 데이터 구조로서, Z-order curve, space-filling curve 등과 같은 많은 공간분할 방법중 하나이다. 

지오해시는 정밀도를 마음대로 정할 수 있고, 코드의 끝부분 문자를 순차적으로 제거하면 크기를 줄일 수 있는 (정확도도 떨어지는) 등의 특성이 있다.

점진적 정밀도 저감 특성의 결과, 인근한 지역(항상 그런 것은 아님)은 대부분 접두어(코드의 시작부분)이 비슷하다. 즉, 접두어가 비슷한 부분이 많을 수록 두 지점은 서로 근접한다.

서비스(Service)

지오해시 서비스는 http://geohash.org/에서 제공된다. 2008년 2월에 시작된 서비스의 목적은 지구상의 위치를 고유하게 구분할 수 있는 짧은 URL을 제공함으로써, 이메일이나 포럼, 웹사이트 등에서 편리하게 사용할 수 있도록 하는 것이다.

지오해시(Geohash)를 얻으려면 사용자는 지오코딩할 주소나 경위도 좌표를 작은 입력박스(대부분 널리 사용되는 정위도 포맷을 인식함)에 넣고, 요청을 시행하면 된다.

주어진 지오해시에 해당되는 경위도 좌표를 보이는 외에도 geohash.org에서 지오해시를 둘러보는 사용자는 내장된 지도도 볼 수 있고, GPX 파일로도 다운로드 받을 수 있으며, 직접 해당 지점을 특정한 GPS 수신기로 전송할 수 도 있다. 아울러 링크를 외부사이트에 제공하여, 특정 지점 주변의 보다 상세한 내역을 제공할 수 있다.

예를 들어 경위도 57.64911,10.40744 (덴마크 Jutland 반도 끝부분)는 약간 짧은 해시인 u4pruydqqvj로 나온다.

사용(Uses)

지오해시의 중요한 사용처는

• 유일 식별자
• point 자료의 표현 (예를 들어 데이터베이스에서)

지오해시는 아울러 지오태깅의 목적으로도 제안되었다.

지오해시 데이터 구조를 데이터베이스에서 사용하면 두가지 장점이 있다. 첫번째, 지오해시로 인덱싱된 데이터는 주어진 직사각형 면적에 포함되는 모든 점들이 인접해 있는 조각에 들어가게 된다.(이때 조각의 수는 필요한 정밀도 및 지오해시 "fault line"의 존재 여부에 따라 달라진다.) 이는 데이터베이스 시스템에서 매우 유용하다. 하나의 인덱스에 대한 쿼리가 여러개의 인덱스로 구성된 쿼리에 비해 훨씬 쉽고 빠르기 때문이다. 두번째, 이 인덱스 체계는 간이 접근성 검색에 사용할 수 있다는 것이다. 즉, 가까운 점들은 지오해시가 비슷하다. 

설계(Design)

해시 값 ezs42를 예로 들어, 지오해시를 십진 경위도로 해석하는 방법을 보이면 아래와 같다.

첫번째 단계는 아래와 같은 문자맵을 사용하여 32진법으로 해시값을 해석하는 것이다.

Decimal	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Base 32	0	1	2	3	4	5	6	7	8	9	b	c	d	e	f	g
Decimal	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
Base 32	h	j	k	m	n	p	q	r	s	t	u	v	w	x	y	z

이 연산을 적용하면 ezs42는 01101 11111 11000 00100 00010 이된다. 여기에서 맨 왼쪽을 0번째 값이라고 가정하여, 짝수 비트는 경도 코드(0111110000000), 홀수 비트는 위도 코드(101111001001)로 둔다.

이제 각각의 2진 코드는 분할에 사용된다. 좌측부터 우측으로 한 비트씩 사용하여 분할 한다. 위도의 경우 -90부터 +90을 두개로 분할 하면, -90 에서 0, 0 에서 +90까지 2개의 구간이 만들어진다. 위도 첫비트는 1이므로, 높은 구간을 사용하게 된다. 이러한 방식으로 모든 비트를 반복한다. 마지막으로 위도 값은 마지막으로 남은 구간의 중앙값이 된다. 경도도 이와 같은 방식으로 처리하되, 시작구간이 -180 에서 180이라는 것만 다르다.

이러한 절차를 마치면 대략 위도 42.6, 경도 -5.6이 된다.

위도 2진값 101111001001이 42.6이 되는 과정은 다음과 같다. 맨 처음에 위도는 -90에서 90 사이라는 것을 알고 있다. 아무런 비트도 없으니, 위도는 0이라고 할 수 있고 에러는 ±90이다. 첫번째 비트를 사용하면, -90 에서 0 구간인지, 0에서 +90 구간인지 결정할 수 있다. 첫번째 비트가 높은(1) 값이므로, 우리의 위도는 0에서 90사이 어디쯤이라는 것을 알 수 있다. 만약 다른 비트가 없다면 위도는 45라고 가정할 수 있고, 에러는 ±45가 된다.

비트가 하나씩 추가될 수록 이 에러가 반으로 줄어든다. 아래의 표는 각각의 비트의 효과이다. 각 단계에서 관계되는 범위는 초록색으로 강조하였다. 즉 낮은 비트(0)은 아래 구간, 높은 비트(1)은 높은 구간을 선택한다.

끝에서 두번째 열은 위도값(범위의 산술평균)이다. 비트가 추가될 수록 이 값은 점점 더 정확해진다.

bit	min	mid	max	val	err
1	-90.000	0.000	90.000	45.000	45.000
0	0.000	45.000	90.000	22.500	22.500
1	0.000	22.500	45.000	33.750	11.250
1	22.500	33.750	45.000	39.375	5.625
1	33.750	39.375	45.000	42.188	2.813
1	39.375	42.188	45.000	43.594	1.406
0	42.188	43.594	45.000	42.891	0.703
0	42.188	42.891	43.594	42.539	0.352
1	42.188	42.539	42.891	42.715	0.176
0	42.539	42.715	42.891	42.627	0.088
0	42.539	42.627	42.715	42.583	0.044
1	42.539	42.583	42.627	42.605	0.022

(위 표에 있는 숫자들은 보기 편하도록 소수점 세자리에서 반올림하였다.)

최종 값은 아래와 같이 사용하여야 한다.

    

따라서 42.61에서 42.61 혹은 42.6은 올바르지만, 43은 아니다.

geohash length	lat bits	lng bits	lat error	lng error	km error
1	2	3	± 23	± 23	± 2500
2	5	5	± 2.8	± 5.6	±630
3	7	8	± 0.70	± 0.7	±78
4	10	10	± 0.087	± 0.18	±20
5	12	13	± 0.022	± 0.022	±2.4
6	15	15	± 0.0027	± 0.0055	±0.61
7	17	18	±0.00068	±0.00068	±0.076
8	20	20	±0.000085	±0.00017	±0.019

지오해시 알고리듬의 한가지 제한은 공통 접두어를 근거로 점들간의 근접성을 찾고자하는 경우에 발생한다. 서로 근접해 있지만, 자오선을 기준으로 180도 떨어져 있는 경계 위치에서는 전혀 접두어가 다르다. (물리적으로는 근접해 있지만, 경도가 다를 경우) 아울러 북극 및 남극에 가까운 점들의 경우, 지오해시가 매우 다르게 된다.(물리적으로는 근접해있지만, 경도가 다를 경우)

적도(혹은 본초자오선)를 기준으로 양쪽으로 근접한 지역에서도 서로 다른 '반구'에 속하기 때문에 접두어가 공통되지 않는다. 간단히 말해 한 지역의 경도(또는 위도)는 011111.... 이 되고 반대쪽은 100000... 이 되어, 공통 접두어는 없고 대부분의 비트가 반대로 된다. 이러한 현상은 점들을 순서대로 나열할 때 Z-order 커브(보다 적당하게는 N-order visit)에 의존하는 경우에도 볼 수 있다. 인접해 있는 두점이 아주 멀리 떨어져 있을 수 있기 때문이다. 그러나, 공통접두어가 긴 점들은 서로 근접하다는 것은 항상 진실이다.

In order to do a proximity search, one could compute the southwest corner (low geohash with low latitude and longitude) and northeast corner (high geohash with high latitude and longitude) of a bounding box and search for geohashes between those two. This will retrieve all points in the z-order curve between the two corners, which can be far too many points, this also breaks down at the 180 meridians and the poles. Solr uses a filter list of prefixes, by computing the prefixes of the nearest squares close to the geohash

인접 검색을 하기 위해서는 먼저 경계 사각형(Bounding box)의 남서쪽 구석(작은 경위도 값을 가진 작은 지오해시)와 북동쪽 구석(높은 경위도 값을 가진 높은 지오해시)를 계산한 뒤, 이 두 점사이의 지오해시를 검색해야 한다. 이렇게 하면 두 꼭지점 사이에 있는 z-order curve에 있는 모든 점을 추출하여, 너무 많은 점이 될 수도 있지만, 180도 자오선 및 극지방에서 분할된다. Solr 는 지오해시에 인접한 사각형의 접두어를 계산함으로써, 접두어 필터 리스트를 사용한다.????

세번째로 지오해시는 경위도좌표에 기반하므로, 두 지오해시간의 거리는 두 지점간의 경위도 좌표에서의 거리가 되는데, 이는 실제 거리가 아니다. 자세한 사항은 Haversine 식을 볼 것.

다음은 경위도 체계의 비 선형성을 보여주는 예이다.

• 적도에서 경도 1도의 길이는 111.320 km 이지만, 위도 1도의 길이는 110.574km로 약 0.67%의 오차가 있다.
• 위도 30도(중위도)에서 이 오류는 110.852/96.486 = 14.89% 로 커진다.
• 위도 60도(고위도)에서는 111.412/55.800 = 99.67% 가 되며, 극에서는 무한대에 근접한다.
  

참고로 이러한 제한은 지오해시 때문이 아니라, 경위도 좌표체계 때문으로, 구면(비선형, 나머지 연산과 비슷하게 값의 겹침 등)상의 좌표를 2차원 좌표로 사상시키는 데 따르는 어려움과 이차원 공간을 균등하게 탐사하는 데 따른 어려움 때문이다. 첫번째는 지리좌표계와 지도투영에 관련된 사항이며, 두번째는 힐버트(Hilbert) 곡선과 z-order curve에 의한 문제이다. 점간의 거리가 선형으로 표현되는 좌표계를 사용하고, 경계에서 중복되지 않는다면 균등하게 탐사하는 것이 가능해져 지오해시를 그러한 좌표계에 적용할 경우 위에서 언급한 제한은 발생하지 않는다.

지오해시를 직각 좌표계를 사용하는 지역에도 적용할 수 있지만, 그 경우 해당 좌표계가 적용하는 지역에서만 사용할 수 있다.

이러한 문제에도 불구하고, 여러가지 회피책이 있으며, 근접성 검색을 구현할 수 있도록 Elasticsearch, MongoDB, HBase, Accumulo 등에서 이 알고리듬을 성공적으로 적용해 왔다.

지오해시를 데이터베이스에서 문자열로 저장하는 대신 다른 대안으로서 위치코드(Locational codes)가 있으며, 이는 공간키(Spatial Key)와 쿼드타일(QuadTiles)과 비슷하게 부른다. 

원문 : https://en.wikipedia.org/wiki/Geohash

11월 19일자 구글 LatLong 블로그 소식입니다. 아주 재미있는 내용이네요. 주소나 업소를 검색해서 나오는 위치표지(marker)가 정확하지 않다면 바른 곳으로 옮겨줄 수 있다는 것입니다. 다만, 이 기능은 미국, 호주, 뉴질랜드만 적용됩니다.

미국의 주소체계는 도로를 기준으로 매겨집니다. 도로의 시작점과 끝점을 정하고 좌측에 1번지 우측에 2번지 또다시 좌측에 3번지... 이런 식으로 매기죠. 이렇게 하면 도로 이름만 알만 쉽게 집을 찾을 수 있습니다. 순서대로 되어 있으니, 길을 잃을 염려가 없는 것이죠.

데이터를 만들 때도 편리합니다. 모든 주소를 일일이 입력할 필요 없이 도로의 시점과 종점에 각각 몇번지에서 시작해서 몇번지로 끝나는지만 기록해 두면 나머지 주소는 계산해서 해결할 수 있으니 저장 장소도 절약되고 검색도 간편해 집니다.

우리나라도 현재 '도로명 주소 등 표기에 관한 법률'에 따라 도로명주소사업단을 구성하고, 새주소를 부여하고 있으며, 현행 지번 방식에 의한 공법 주소제도가 2012년 '도로명 주소체계'로 완전 교체될 예정으로 있습니다. (참고 :도로명 주소사업, 법 제정으로 탄력 받는다)

하지만, 이와 같이 계산에 의해 주소를 찾다보면 원하지 않는 결과가 나오기도 합니다. 예를 들어 주소를 부여할 때는 큰길을 기준으로 먼저 주소를 매기는데, 어떤 집이 큰길에 면해 있기는 하지만, 작은 길에 대문이 있는 경우 정확한 위치를 한번에 찾기 힘들 수 있습니다. 또, 사거리에 집이 있는 경우에는 도로 한가운데에 주소표지가 나타나게 되는 등의 문제가 있죠. (물론 이런 단점에 비해 장점이 훨씬 많기 때문에 전 세계적으로 도로명을 기반으로 한 주소체계를 사용하고 있습니다.)

위에 설명한 문제를 해결하기 위한 방법으로 구글에서는 위치표지를 정확한 곳으로 옮길 수 있도록 허용하게 된 것으로 보입니다. 물론 장난치기 좋아하는 사람때문에 문제가 발생할 수도 있지만, 그 점도 고려를 해 두었네요.

직접 한번 해보세요. 외국에 친구가 있는 분들은 친구네 집을 찾아봐도 좋겠구요, 아니면 본문에 써진 것처럼 스트릿뷰를 켜두고 확인해 보시면 됩니다.

민, 푸른하늘
관련기사 : 구글, 지도 서비스 오류 네티즌이 수정토록 허용
====
http://google-latlong.blogspot.com/2007/11/think-globally-mark-locally.html
Monday, November 19, 2007 at 6:30 AM
Posted by Seth LaForge, Software Engineer, Google Maps

제가 예전 파티를 했을 때, 구글맵에 있는 개인지도(My Maps) 기능을 사용해 친구들에게 저희 집을 정확히 알려주려고 했습니다. 그러나, 친구들은 나름대로 지도에서 우리집 주소를 검색하여 표시된 위치로 가서는, 한버트면 길 한가운데서 파티를 열 뻔 했습니다.

이제 다음 파티 때는 위치표지를 이동시켜서 여러분 집 입구를 정확하게 표시할 수 있게 되었습니다. 여러분의 주소를 검색한 뒤, "편집(edit)"와 "표지 이동(Move Marker)"를 누르고, 원하는 표지를 여러분의 집 앞에 가져다 놓으시면 됩니다.

물론, 주소에 한정된 것은 아닙니다. 때로는 업소를 찾기 힘들 때도 있죠. 이제 여러분은 구글맵에서 찾아본 뒤 위치표지를 정문 앞으로 옮기실 수 있습니다. 이 정보 덕분에 누군가 데이트 시간에 늦지 않을 수도 있습니다! 위치표지 옮기기는 정말 중독성이 강합니다. 저는 몇 시간동안 스트릿뷰(Street View)를 사용하여 업소나 집을 찾아본 후 위치표지를 바른 곳으로 옮겼답니다.

위치표지로 장난을 치는 사람들이 있을까 걱정하실 수도 있겠지만, 걱정 마세요. 그것도 고려해 뒀습니다. 최근에 옮겨진 주소나 업소를 발견하면, "원래 위치(Show Original)"링크를 눌러서 원래 위치를 확인해 보실 수 있습니다. 이상한 곳에 표지가 있으면 그냥 바른 곳으로 옮겨주시면 됩니다.

위치 표지를 고치면 여러분의 가상 마을(Virtual Neighborhood)을 더 나은 곳으로 만들 수 있습니다. 미국, 오스트랠리아, 뉴질랜드에 사신다면 즉시 해보세요. 단, 직접 해보시려면 구글 계정이 필요합니다. 아래 비디오에 나오는 집은 우리집이 아니라는 것... 아시죠?