힐베르트 곡선 좌표 변환기

정사각형 격자의 모든 칸을 한 붓 그리기로 지나는 길입니다. 차수 n이면 한 변이 2ⁿ이고 칸이 4ⁿ개이며, 각 칸에는 출발점에서 몇 번째로 지났는지를 나타내는 번호가 붙습니다. 1891년 다비트 힐베르트가 소개했습니다.

거리 d가 가까우면 좌표도 반드시 가깝기 때문입니다. 2차원 자료를 1차원으로 줄 세워야 하는 곳에서, 가까운 것끼리 디스크나 캐시에서도 가까이 놓이게 됩니다. 지도 타일 정렬, 공간 데이터베이스의 인덱스, 이미지 데이터의 메모리 배치가 대표적입니다.

아닙니다. 그 반대 방향은 성립하지 않습니다. 바로 옆 칸인데 d가 수십 차이 나는 자리가 반드시 생깁니다. 곡선이 어딘가에서는 돌아 나가야 하기 때문이고, 이것은 어떤 공간 채움 곡선에도 있는 한계입니다.

Z-order는 x와 y의 비트를 번갈아 끼우기만 하면 되어 훨씬 간단하지만, 다음 칸으로 멀리 건너뛰는 자리가 많습니다. 차수 3이면 63번의 이동 가운데 31번이 이웃이 아닌 곳으로 건너뛰고 가장 큰 도약은 8칸입니다. 힐베르트 곡선에는 그런 자리가 하나도 없습니다.

한 겹씩 내려가며 어느 사분면인지 고르고, 그때마다 좌표계를 뒤집거나 돌립니다. 이 회전이 사분면끼리 길을 이어 붙이는 비결이고, 그래서 코드가 Z-order보다 깁니다. 차수 n이면 반복이 n번이라 계산 자체는 아주 빠릅니다.

다릅니다. 지오해시는 위경도를 번갈아 쪼개 문자열로 만든 것이라 사실상 Z-order 계열이고, 그래서 이웃한 지역인데 지오해시 앞자리가 완전히 달라지는 경계가 생깁니다. 힐베르트 곡선은 그 경계 문제가 훨씬 적어 공간 인덱스에서 선호됩니다.

전송되지 않습니다. 변환과 그림 그리기는 모두 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.