한양과학기술고등학교

1. 어떻게 만들어지나 — U자 하나에서 시작하는 재귀

차수 n=1의 힐베르트 곡선은 2×2 격자를 잇는 ㄷ자(U자) 모양 하나다. 차수를 하나 올릴 때마다 격자는 가로·세로로 2배가 되고, 네 개의 사분면에 축소된 이전 차수 곡선을 하나씩 넣은 뒤 짧은 선분 3개로 이어 붙인다. 이때 아래쪽 두 사분면의 곡선은 서로 다른 방향으로 회전·반사시켜야 곡선의 끝과 다음 곡선의 시작이 딱 맞물린다. 이 "방향을 틀어 넣기"가 힐베르트 곡선의 핵심이다.

• 차수 n → 격자 2ⁿ × 2ⁿ, 방문하는 칸 4ⁿ개
• 연속한 두 칸은 항상 상하좌우로 딱 한 칸 떨어져 있다 (대각선 이동 없음)
• 차수를 올려도 큰 그림의 모양은 유지된다 → 자기 닮음(프랙탈)

2. 왜 쓰나 — 1차원 ↔ 2차원을 지역성을 지키며 오간다

곡선 위의 위치를 거리 d(0부터 4ⁿ−1까지)라고 하면, 모든 d는 격자 좌표 (x, y) 하나에 대응한다. 힐베르트 곡선의 값어치는 이 대응이 양방향으로 지역성을 보존한다는 데 있다.

• d가 가까우면 (x,y)도 가깝다: 스트리밍·캐시에서 연속으로 읽는 픽셀들이 화면상 뭉쳐 있다 → 캐시 적중률↑
• (x,y)가 가까우면 d도 대체로 가깝다: 지도 위 인접 지역이 인덱스에서도 가깝다 → 범위 질의("이 사각형 안의 점 모두")가 디스크에서 적은 조각으로 처리된다

단순한 행 우선 스캔은 한 행 끝에서 다음 행 시작으로 격자 폭만큼 점프하고, Z-곡선(모튼 순서)은 사분면 경계에서 큰 점프가 생긴다. 힐베르트 곡선은 이런 큰 점프가 없어 세 방식 중 지역성이 가장 좋다.

3. 실제 쓰이는 곳

• 공간 인덱스: R-tree·B-tree에 2D 좌표를 1D 키로 넣을 때 (Hilbert R-tree)
• 데이터베이스 샤딩: 위경도를 힐베르트 값 하나로 바꿔 인접 지역을 같은 샤드에 배치
• 이미지: 디더링·점진적 전송의 픽셀 방문 순서, 텍스처 메모리 배치(스위즐링)
• 시각화: IPv4 주소 공간 전체를 한 장의 정사각형 지도로 (xkcd "Map of the Internet")

4. 거리 d ↔ 좌표 (x, y) 변환 코드

재귀 그림 없이도, d를 2비트씩 잘라 보며 사분면을 따라 내려가면서 필요할 때 좌표축을 회전(swap/flip)시키면 O(n)에 변환된다. 위키백과에 실린 고전적인 구현이다.

# d  →  (x, y)   :  side = 2^n 격자에서 곡선상 거리 d의 좌표
def d2xy(side, d):
    x = y = 0
    s = 1
    while s < side:
        rx = 1 & (d // 2)
        ry = 1 & (d ^ rx)
        # 현재 s×s 블록을 회전/반사시켜 방향을 맞춘다
        if ry == 0:
            if rx == 1:
                x = s - 1 - x
                y = s - 1 - y
            x, y = y, x
        x += s * rx
        y += s * ry
        d //= 4
        s *= 2
    return x, y

# (x, y)  →  d   :  역변환도 같은 회전 규칙을 거꾸로 적용
def xy2d(side, x, y):
    d = 0
    s = side // 2
    while s > 0:
        rx = 1 if (x & s) > 0 else 0
        ry = 1 if (y & s) > 0 else 0
        d += s * s * ((3 * rx) ^ ry)
        if ry == 0:
            if rx == 1:
                x = s - 1 - x
                y = s - 1 - y
            x, y = y, x
        s //= 2
    return d

위 두 함수는 서로 역함수다: d2xy(side, xy2d(side, x, y)) == (x, y). 아래 데모의 곡선도 정확히 이 규칙으로 그려진다.