모턴 코드(Z-order) 변환기

좌표의 비트를 번갈아 끼워 넣어 하나의 정수로 만든 값입니다. x = 0b1011, y = 0b0110이면 y와 x의 비트를 한 칸씩 걸러 엮어 0b01101101 = 109가 됩니다. 이렇게 접은 수로 정렬하면 가까운 좌표끼리 대체로 가까운 번호를 받으므로, 2차원·3차원 자료를 1차원 인덱스(B-트리·디스크·캐시)에 얹을 수 있습니다. 지나는 길이 Z자를 반복해 Z-order 곡선이라고도 부릅니다.

비트를 벌리는 다섯 줄짜리 트릭에서 남길 자리를 고르는 마스크입니다. 0x55555555는 2진수로 0101…이라 «한 칸 걸러 하나»를, 0x33333333은 00110011…이라 «둘씩 묶어 걸러»를 뜻해서, 마스크 자체가 그 단계에서 만들려는 모양입니다. 비트마다 반복문을 도는 대신 자리를 절반씩 갈라 옮겨 다섯 번 만에 끝냅니다. 3차원은 한 칸 걸러 둘씩 벌려야 해서 0x09249249(001001001…)를 씁니다.

같습니다. 쿼드키는 모턴 코드를 4진수로 적은 것이고, 자릿수 하나가 확대 단계 하나입니다. 각 자리의 두 비트가 «위·아래»와 «왼쪽·오른쪽»을 뜻하므로 앞자리를 잘라내면 곧바로 상위 타일이 되고, 문자열 접두사만 봐도 포함 관계를 알 수 있습니다.

모턴 코드는 변환이 시프트와 마스크 몇 번으로 끝나 훨씬 싸지만, 격자에서 붙어 있는데 번호는 멀리 떨어지는 자리가 생깁니다. 힐베르트 곡선은 그런 자리가 없어 지역성이 좋은 대신 단계마다 방향을 따져야 해 변환이 비쌉니다. 두 곡선의 도약 거리를 실제로 세어 견주는 것은 힐베르트 곡선 계산기 쪽에 있습니다.

격자를 반으로 가르는 선을 넘을 때입니다. 한 칸 옆으로 갔을 뿐인데 상위 비트가 바뀌면 코드가 통째로 건너뜁니다. 특히 위아래로 가르는 선이 가장 심한데, y가 각 비트 쌍의 높은 자리를 차지해 좌우로 가르는 선을 넘을 때보다 두 배 넘게 벌어지기 때문입니다. 8×8 격자에서 (3,3)과 (3,4)는 맞닿아 있지만 코드는 15와 37로 22만큼 떨어집니다.

2차원은 축마다 16비트(코드 32비트), 3차원은 축마다 10비트(코드 30비트)까지 다룹니다. 널리 쓰이는 32비트 구현의 한계와 같으며, 자바스크립트의 비트 연산이 32비트에서 부호를 뒤집는 것도 이 범위로 맞춘 이유입니다.

그대로 쓰면 조건 밖의 칸이 섞여 들어옵니다. 한 축만 늘리면 코드도 반드시 커지므로 «x가 a 이상 b 이하»인 칸들이 이어진 구간 안에 들어 있기는 하지만, 그 구간에는 조건을 벗어난 칸도 함께 들어갑니다. 실제 공간 데이터베이스는 구간을 조건에 맞게 잘게 쪼개는 계산을 따로 합니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지며 입력한 좌표는 이 기기에만 남습니다.