쿼드트리

수치해석 컴퓨터 그래픽스 게임 개발 마지막 수정: 2026-08-30 04:14:26

1. 개요[편집]

사각형을 넷으로 자른다. 붐비는 데만 또 자른다. 이 두 줄로 지도와 게임과 격자가 굴러간다.

쿼드트리(quadtree, 사진트리)는 2차원 영역을 재귀적으로 네 개의 사분면으로 쪼개어 만든, 내부 노드의 자식 수가 넷인 트리 자료구조다. 3차원으로 올리면 옥트리, 1차원으로 내리면 이진 탐색 트리가 된다. 이름은 핑켈과 벤틀리가 1974년에 붙였지만¹, 사실 그 이름 아래에는 성격이 꽤 다른 물건 둘이 섞여 있고 그 구분을 놓치면 복잡도 이야기가 통째로 어긋난다.

핵심 미덕은 KD-트리와 정반대 방향에서 온다. KD-트리가 데이터를 보고 자를 곳을 고르는 대신, 쿼드트리는 대개 자를 곳을 데이터와 무관하게 셀 중심으로 못 박는다. 그 대가로 트리 균형을 잃지만, 셀이 영원히 정사각형이고 레벨이 곧 해상도 $s/2^\ell$ 이며 좌표만으로 셀 주소를 계산할 수 있다는 세 가지가 공짜로 따라온다. 자료구조 전체의 조감도는 공간 분할 자료구조에, 3차원 판의 세부는 옥트리에 있고, 여기서는 2차원 고유의 사정 — 특히 평면에서만 깔끔하게 성립하는 둘레 정리와 이웃 균형 — 을 판다.

2. 점 쿼드트리와 영역 쿼드트리[편집]

	점(point) 쿼드트리	PR 쿼드트리	영역(region) 쿼드트리
분할점	삽입된 데이터 점	셀 중심	셀 중심
잎이 담는 것	점 하나	점 0~ $c$ 개	균질 여부(찼다/비었다)
트리 모양	삽입 순서 의존	순서 무관	순서 무관
셀 모양	임의 직사각형	항상 정사각형	항상 정사각형

점 쿼드트리는 핑켈·벤틀리의 원본이다. 삽입된 점 자체가 그 노드의 4분할 중심이 되고, 다음 점은 자기 사분면으로 내려가 다시 중심이 된다. 이진 탐색 트리의 2차원 판이라 무작위 순서로 넣으면 기대 깊이가 $O(\log n)$ 이지만, 정렬된 순서로 넣으면 한 줄로 퇴화해 최악 $O(n)$ 이다. 삭제가 지옥이라는 것도 BST와 같고 — 지운 점을 대체할 점을 고르면 네 사분면이 전부 재배치되어야 한다 — 그래서 오늘날 이 자리는 KD-트리가 다 가져갔다.

영역 쿼드트리는 공간을 반씩 접는다. 분할점이 언제나 셀의 기하학적 중심이라 데이터와 무관하고, 그래서 셀이 영원히 정사각형이다. 실무에서 「쿼드트리」라 하면 거의 이쪽이며, 잎에 점을 담고 용량 $c$ (보통 4~16개)를 넘으면 쪼개는 것이 PR 쿼드트리(point-region), 잎이 「전부 찼다/전부 비었다」의 균질 라벨을 들고 균질하면 안 쪼개는 것이 좁은 의미의 영역 쿼드트리다. 후자가 이미지·래스터용이고 전자가 점군·입자용이다.

깊이에 관한 함정은 3차원과 똑같다. 영역 쿼드트리의 깊이는 점의 개수가 아니라 「퍼짐 비」(최대 거리 ÷ 최소 거리)가 정한다. 0.001 픽셀 떨어진 두 점을 갈라놓으려면 그 둘이 다른 사분면에 떨어질 때까지 계속 쪼개야 하고, 그동안 자식이 하나뿐인 빈 사슬이 쌓인다. 점이 둘뿐인데 깊이 40이 나온다. 처방은 최대 깊이 상한을 거는 것, 혹은 단일 자식 사슬을 접어 노드 수를 $O(n)$ 으로 보장하는 압축 쿼드트리를 쓰는 것이다.

3. 질의 비용 — 둘레가 값을 매긴다[편집]

삽입은 잎까지 내려가는 것이므로 $O(d)$ ( $d$ = 깊이)이고, 위 사정 때문에 균등 분포에서 $O(\log n)$ , 최악에는 상한 $d_{\max}$ 다. 재미있는 것은 범위 질의다.

$n$ 개의 점을 담은 균형 잡힌 트리라면 축 정렬 사각형 범위 질의의 최악 비용은 KD-트리와 같은 $O(\sqrt n + k)$ 꼴이지만 ( $k$ = 보고된 점 수), 래스터 영역 쿼드트리에서는 훨씬 예쁜 결과가 있다. 쿼드트리 복잡도 정리(헌터·스타이글리츠, 1979)는 $2^q \times 2^q$ 격자 위의 단순 다각형을 표현하는 영역 쿼드트리의 노드 수가

O(p + q)

임을 말한다. 여기서 $p$ 는 픽셀 단위로 잰 다각형의 둘레다. 넓이가 아니라 둘레라는 것이 핵심이다 — 면적이 백만 픽셀이어도 경계가 매끈하면 노드는 수천 개면 된다. 영역 쿼드트리로 하는 거의 모든 연산(합집합, 라벨링, 회전을 뺀 변환)의 비용이 이 노드 수에 비례하므로, 정리 하나가 「쿼드트리로 이미지를 다뤄도 되는가」에 대한 답을 통째로 준다.²

최근접 질의는 우선순위 큐를 쓴 최선 우선 탐색이 표준이다. 후보 노드를 「질의점에서 그 셀까지의 최소 거리」 순으로 우선순위 큐에 넣고 꺼내면서, 큐 머리의 하한이 현재 최선 거리보다 크면 즉시 멈춘다. 균등 분포에서 기대 $O(\log n)$ 이지만 최악은 언제나 $O(n)$ 이고, 그 최악은 생각보다 자주 온다 — 점들이 한 직선 위에 몰려 있으면 질의공이 사실상 모든 잎을 건드린다.

4. 선형 쿼드트리 — 트리를 정수 배열로[편집]

포인터로 노드를 잇는 구현은 캐시에 나쁘고 분산 환경에서 쪼개기가 곤란하다. 선형 쿼드트리(가르간티니, 1982)는 포인터를 없애고 셀 하나를 정수 하나로 표현한다. 그 정수가 공간 채움 곡선 중 모턴 코드(Z-차수)다.

레벨 $\ell$ 셀의 좌표 $(i,j)$ 를 $\ell$ 비트로 쓰고 비트를 둘씩 번갈아 끼운다.

m = i_{\ell-1} j_{\ell-1}\ \ i_{\ell-2} j_{\ell-2}\ \cdots\ i_0 j_0

여기서 계층 구조가 통째로 튀어나온다. 부모는 m >> 2, $u$ 번째 자식은 (m << 2) | u, 형제 넷은 하위 2비트만 달라 연속한 정수 네 개를 차지하고, 조상-자손 판정이 접두사 비교로 끝난다. 트리를 「짓는」 절차는 「점마다 모턴 키를 계산하고 정렬한다」가 전부이며, 정렬된 키 배열이 곧 깊이 우선 순회 순서다. 키가 정수라 기수 정렬이 그대로 먹히고, 그래서 GPU에서 수백만 점짜리 트리를 밀리초 단위로 다시 짓는다.

2차원이 3차원보다 넉넉한 지점이 여기다. 64비트 정수에 좌표 셋을 끼우면 축당 21비트뿐이지만, 둘만 끼우면 축당 32비트라 지구 규모 좌표계에서도 여유가 있다. 웹 지도 타일의 quadkey가 정확히 이 인코딩이다 — 줌 레벨 $z$ 의 타일 하나를 길이 $z$ 짜리 4진수 문자열로 쓴 것이고, 문자열 접두사가 곧 상위 줌 레벨의 타일이라 지리정보시스템 캐시가 접두사 매칭만으로 굴러간다.

5. 이웃 찾기와 2:1 균형[편집]

쿼드트리 연산 중 제일 자주 필요하고 제일 귀찮은 것이 「이 셀의 $+x$ 쪽 이웃은 누구인가」다. 포인터 트리에서는 공통 조상까지 올라갔다 반대편으로 내려오는 재귀가 필요하지만, 모턴 키에서는 좌표 필드 하나만 증감하면 되고 그것이 비트 연산 두 줄이다. 자리올림이 다른 축 비트를 그냥 통과하도록 마스크로 채워 두는 트릭이며, 원리와 코드는 옥트리 문서에 그대로 있다.

문제는 레벨이 섞인 트리다. 이웃 키를 계산했더니 그 셀이 실제로는 더 굵거나 더 잘게 쪼개져 있을 수 있고, 그러면 이웃이 몇 개인지조차 미리 알 수 없다. 그래서 거의 모든 실무 쿼드트리가 거는 조건이 2:1 균형(balanced quadtree, 제약 쿼드트리)이다.

변을 공유하는 두 잎의 레벨 차이는 1 이하여야 한다.

이 조건을 강제하면 한 변의 이웃 후보가 「같은 레벨 하나, 부모 하나, 자식 둘」로 유한하게 닫힌다. 값이 나오는 곳은 두 군데다.

적응 격자 세분화(AMR). 셀 간 플럭스를 계산하려면 굵은 셀과 잘은 셀 사이의 보간·제한 연산자가 필요한데, 레벨 차이가 무제한이면 스텐실을 유한하게 정의할 수 없다. 2:1이면 「1:2 보간」 하나만 구현하면 끝난다. 보존형 유한체적법에서는 굵은 면의 플럭스를 잘은 면 둘의 합으로 덮어써야 질량이 보존되는데, 그 「둘」이 상수라는 것 자체가 2:1 덕분이다.
유한요소법의 매달린 절점. 이웃이 잘게 쪼개지면 굵은 변 중간에 상대 쪽 절점이 매달린다(hanging node). 이 절점은 자유도가 아니라 양 끝 절점의 구속 조건으로 소거해야 하는데, 레벨 차이가 1로 묶여야 구속 패턴이 한 종류로 끝나고 조립 코드가 유한해진다.

균형화는 「이 잎보다 두 레벨 이상 굵은 이웃이 있으면 그 이웃을 쪼갠다」를 더 쪼갤 것이 없을 때까지 반복하는 것인데, 쪼갠 결과가 또 다른 위반을 만드는 연쇄가 일어나 순진하게 짜면 $O(n^2)$ 이 나온다. 정렬 기반 병렬 알고리즘이 표준이고, 다행히 균형화가 노드 수를 상수배 이상 늘리지 않는다는 것이 알려져 있어 메모리 예산은 안전하다. 대신 AMR 프레임워크 코드의 상당 부분이 여기에 들어간다.³

6. 응용[편집]

브로드페이즈 충돌 감지. 2D 게임의 국룰. 객체를 자기가 완전히 들어가는 가장 작은 셀에 등록하고 같은 셀 + 조상·자손만 후보로 삼는다. 고전적 약점도 3차원과 같다 — 셀 경계에 걸친 작은 객체가 루트까지 올라가 전부와 후보 쌍이 된다. 처방은 셀 판정 경계를 2배로 부풀리는 느슨한 쿼드트리이고, 이러면 등록 레벨이 위치와 무관하게 크기만으로 정해진다.
이미지 압축. 블록이 균질하면 한 노드, 아니면 넷으로 쪼개는 구조가 곧 이미지 압축의 고전인 쿼드트리 부호화다. 「쪼갤 것인가 말 것인가」를 비트 비용과 왜곡의 라그랑주 합 $J = D + \lambda R$ 로 정하면 그게 바로 율-왜곡 이론의 RDO이고, 놀랍게도 트리 구조에서는 이 최적화가 잎에서 뿌리로 올라오는 동적 계획법 한 번으로 전역 최적이 나온다. HEVC의 부호화 트리 유닛 분할 결정이 정확히 이 계산이다.
지리정보시스템. 래스터 타일 피라미드, 공간 인덱스, 그리고 위경도를 모턴 비트로 엮은 지오해시가 전부 쿼드트리다. 접두사가 곧 포함 관계라 문자열 인덱스(B-트리)에 그대로 실린다는 것이 실무에서 결정적이다.
2D 반스-헛 알고리즘. 입자를 쿼드트리에 넣고 셀 크기 $s$ 와 거리 $d$ 가 $s/d < \theta$ 를 만족하면 그 셀 전체를 질량중심 하나로 대체해 $O(N^2)$ 을 $O(N \log N)$ 으로 낮춘다. 셀이 정사각형이라야 이 개방 판정의 오차 한계가 깔끔하게 나온다는 것이 데이터 적응 분할 대신 중심 분할을 쓰는 이유다.
지형과 LOD. 하이트맵을 쿼드트리로 덮고 카메라 거리에 따라 레벨을 고르는 것이 지형 레벨 오브 디테일의 기본형이다. 여기서도 2:1 균형이 필수인데, 이유가 수치해석과 판박이다 — 이웃 패치의 레벨이 두 단계 이상 차이 나면 변을 따라 정점이 안 맞아 틈(crack) 이 벌어진다.

7. 구현할 때 밟는 지뢰[편집]

깊이 상한을 안 걸었다. 좌표가 같은 점이 둘 있으면 재귀가 안 끝난다. 부동소수점 오차로 「거의 같은」 점이 생기는 것만으로 깊이가 수십으로 튄다. 상한과 잎 용량을 함께 걸어라.
경계 위의 점. 셀 중심에 정확히 놓인 점이 어느 자식으로 갈지 규칙(< 냐 <= 냐)을 한 번 정하고 삽입·질의·이웃탐색 전부에서 같게 써야 한다. 삽입과 질의가 다른 규칙을 쓰면 있는 점을 못 찾는 유령 버그가 난다.
자식 넷을 항상 할당한다. 대부분의 노드는 자식 대다수가 비어 있다. 4비트 마스크로 존재 여부를 들고 존재하는 것만 연속 배열에 두는 표현이 표준이다.
움직이는 객체를 매 프레임 지웠다 다시 넣는다. 쿼드트리는 국소 갱신이 약하다. 객체가 전부 움직이는 장면이면 매 프레임 모턴 정렬로 통째로 다시 짓거나, 아예 경계 볼륨 계층의 리핏 전략으로 가는 편이 낫다.
균등 분포에 쿼드트리를 쓴다. 점이 고르게 퍼져 있고 질의 반경이 고정이면 균일 격자가 질의당 $O(1)$ 이고 트리 구축 비용조차 없다. 쿼드트리는 밀도가 불균일할 때 값을 하는 물건이다. 「일단 격자부터 깔아 보고 뭉침이 보이면 트리로 간다」가 현장의 순서다.

8. 관련 문서[편집]

옥트리 · KD-트리 · BSP 트리 · 공간 분할 자료구조 · 경계 볼륨 계층
공간 채움 곡선 · 표면적 휴리스틱 · 우선순위 큐
적응 격자 세분화 · 유한요소법 · 유한체적법 · 격자
반스-헛 알고리즘 · 고속 다중극자법 · 부하 분산
충돌 감지 · 프러스텀 컬링 · 레벨 오브 디테일
율-왜곡 이론 · 이미지 압축 · 지리정보시스템
최근접 이웃 탐색 · 계산기하학 · 동적 계획법

Finkel & Bentley (1974), Acta Informatica 4. 제목이 “Quad trees: a data structure for retrieval on composite keys”인데, 정작 세상이 쓰는 것은 이 논문의 점 쿼드트리가 아니라 그 뒤에 나온 영역 쿼드트리다. 저자가 지은 이름만 남고 자료구조는 바뀐 셈. KD-트리도 같은 저자가 이듬해에 내놨고 그쪽이 훨씬 오래 살아남았다는 것이 더 얄궂다. ↩
「노드 수가 넓이가 아니라 둘레에 비례한다」는 정리는 실무에서 이렇게 읽힌다 — 경계가 프랙탈이면 쿼드트리가 죽는다. 매끈한 행정구역 경계는 잘 압축되고, 해안선이나 잡음 섞인 분할 마스크는 둘레가 해상도와 함께 발산해서 노드가 픽셀 수만큼 늘어난다. GIS 쪽에서 쿼드트리를 얹기 전에 경계를 단순화하는 전처리가 관례인 이유. ↩
2:1 균형 조건은 이름이 여럿이다. 그래픽스에서는 “restricted quadtree”, AMR 문헌에서는 “proper nesting” 또는 “2:1 balance”, 메시 쪽에서는 “1-irregular mesh”. 다 같은 조건인데 세 커뮤니티가 서로의 논문을 안 읽어서 이름이 셋이 됐다. 그리고 세 곳 모두 “이거 구현이 제일 짜증난다”는 데는 이견이 없다. ↩