Quad Tree로 2차원 공간 데이터를 인덱싱하는 방법
Quad Tree의 공간 분할 구조와 삽입·범위 질의·병합 원리, 파라미터 튜닝 및 공간 인덱스 선택 기준을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
점이 몰린 곳만 더 깊게 나누는 공간 인덱스
공간 데이터를 전부 순회하면 검색과 갱신, 메모리 사용량이 서로 충돌한다. Quad Tree는 2차원 영역을 축 정렬 사각형(AABB) 기준으로 반복해 네 구역으로 나누고, 필요한 영역만 탐색하도록 만든 계층형 자료 구조다.
루트 노드는 전체 경계 상자를 나타낸다. 각 노드는 리프이거나 네 자식을 가지며, 노드가 수용 가능한 점 수인 capacity를 넘으면 분할한다. GIS, 게임, 시뮬레이션, 이미지 처리처럼 위치 기반 데이터를 다루는 작업에서 쓰인다.
저장 방식과 분할 기준에 따라 Point Quadtree, Region Quadtree, PR Quadtree(Point-Region)로 나뉜다. 이 가운데 PR Quadtree가 실무에서 가장 보편적이다. 점을 어느 노드에 저장할지, 언제 나눌지, 삭제 뒤 언제 합칠지는 선택한 변종과 워크로드에 따라 달라진다.
경계와 리프가 맡는 역할
분할은 보통 노드의 점 수가 capacity를 초과할 때 일어난다. 최대 깊이에 이르지 않은 상태에서 분할하면 각 자식은 부모 경계의 NE, NW, SE, SW 영역을 맡고, 기존 점은 해당 자식으로 다시 배치된다.
데이터가 몰린 영역은 더 깊은 노드까지 내려가고, 드문 영역은 얕은 리프로 남는다. 비균일한 분포에 구조가 적응하는 이유다.
리프는 점 목록을 보관하고, 내부 노드는 경계와 자식 포인터를 유지한다. 삽입·삭제·질의에서 먼저 AABB의 포함 또는 교차 여부를 검사하면 관련 없는 노드를 일찍 배제할 수 있다. 정밀 충돌 판정은 마지막 단계에서만 수행한다.
경계 규칙은 특히 일관돼야 한다. 예를 들어 우상단은 열고 좌하단은 닫는 규칙을 정했다면 모든 비교에서 같은 반개구간 규칙을 적용해야 한다. 부동소수점 오차는 epsilon으로 보정할 수 있다.
삽입과 범위 질의가 내려가는 경로
점 삽입은 먼저 루트 경계 안에 있는지 확인한다. 리프에 여유가 있으면 점을 추가하고, 그렇지 않으면 분할한 뒤 적절한 자식으로 재귀 삽입한다. 경계 밖 점은 거부하거나 상위 경계를 조정한다.
범위 또는 교차 질의에서는 질의 창과 노드 경계가 교차하는지 먼저 본다. 교차하지 않으면 그 하위 트리를 배제하고, 리프에 도달했을 때만 저장된 점을 상세 검사해 결과 집합에 추가한다. 삭제 뒤에는 자식의 총 점 수가 용량 이하일 때 병합할 수 있으며, 분할과 병합이 반복해서 흔들리지 않도록 히스테리시스를 둔다.
평균 삽입과 질의는 O(log n)을 가정할 수 있지만, 분포가 한쪽으로 치우치거나 공간이 왜곡되면 최악 O(n)이 된다. 메모리에는 노드 자체의 오버헤드가 따른다. capacity를 높이면 노드 수와 깊이는 줄지만 리프에서의 선형 스캔 비용은 커진다.
주요 조정 대상은 capacity(예: 432), maxDepth(예: 1220), 최소 셀 크기(minSize)다. 읽기 중심 워크로드는 낮은 capacity, 쓰기 중심 워크로드는 높은 capacity가 맞을 수 있다.
충돌 후보부터 공간 이벤트까지
게임과 시뮬레이션에서는 동적 객체의 근접 후보군을 먼저 줄여 충돌 감지에 쓴다. 프레임마다 O(n) 충돌 테스트를 수행하는 대신 O(k) 후보군으로 좁혀 CPU 사용률을 낮출 수 있다.
GIS와 지도 서비스에서는 POI, 지오펜싱, 범위 질의의 인덱스로 활용한다. 타일 레벨별 LOD 제공과 서버 캐시 효율 개선에도 연결된다. 이미지 처리에서는 이진 이미지의 균질 영역을 분할해 저장량을 줄이고, 에지 검출이나 분할 같은 레벨별 처리를 병렬화하기 쉽다.
IoT 위치 이벤트를 다룰 때는 공간 윈도 질의를 빠르게 해 지오펜스 진입·이탈 이벤트의 처리 지연을 낮출 수 있다.
균일 분포를 가정하고 영역 비율을 a라고 할 때, 방문 노드와 후보 점 수는 대략 a에 비례한다. 100만 점, capacity=16, a=1%인 경우 후보군은 10^4이고 최종 비교는 10^310^4 범위가 된다. 분포와 구현에 따라 달라지지만 선형 스캔과 비교해 10100배 가속할 수 있다.
capacity를 8→16으로 조정하면 분할 횟수는 4060% 감소하고, 리프 스캔 비용은 ~2배 증가한다. 노드 수는 ~ O(n/capacity)이며, 얕은 깊이와 연속 메모리 레이아웃(SOA/아레나 할당)을 적용하면 캐시 미스를 줄일 수 있다.
다른 공간 인덱스와 선택 기준
| 항목 | Quad Tree | k-d Tree(2D) | R-Tree/R*-Tree |
|---|---|---|---|
| 성능(범위 질의) | 균일/지역성에 강점, 비균일 분포 시 성능 편차 | 구분 초평균 우수, 분할 평면 기반 | 실무 전반적으로 안정적, 중첩 최소화가 핵심 |
| 업데이트 비용 | 저비용 삽입/삭제, 병합 정책 필요 | 재균형 비용 존재 | 삽입/삭제 중간, 재삽입/강제분할 비용 |
| 확장성(차원) | 2D 특화, 고차원 부적합 | 2D~중간 차원 적합 | 2D/3D 공간 인덱스 표준 |
| 안정성(왜곡 분포) | 파라미터 의존, 최악 O(n) | 분할 선택에 따라 편향 가능 | R*-Tree가 중첩 최소화로 안정성 우수 |
| 운영 편의 | 구현 용이, 튜닝 직관 | 구현 중간 난이도 | 라이브러리 의존, 설정 복잡 |
빠르게 구현하고 직관적으로 튜닝해야 한다면 Quad Tree가 적합하다. 반면 생산 환경에서 일관된 성능과 디스크 인덱싱이 중요하다면 R*-Tree를 검토할 수 있다.
반개구간 경계를 적용한 구현
Python 3.9+에서 외부 라이브러리 없이 실행할 수 있는 예시다. 좌하단을 포함하고 우상단을 제외하는 [xmin, xmax), [ymin, ymax) 경계 규칙을 사용한다.
from dataclasses import dataclass
from typing import List, Tuple, Optional
Point = Tuple[float, float]
@dataclass
class AABB:
xmin: float; ymin: float; xmax: float; ymax: float
def contains(self, p: Point) -> bool:
x, y = p
return self.xmin <= x < self.xmax and self.ymin <= y < self.ymax
def intersects(self, other: "AABB") -> bool:
return not (other.xmax <= self.xmin or other.xmin >= self.xmax or
other.ymax <= self.ymin or other.ymin >= self.ymax)
class QuadTree:
def __init__(self, boundary: AABB, capacity: int = 8, max_depth: int = 16):
self.boundary = boundary
self.capacity = capacity
self.max_depth = max_depth
self.points: List[Point] = []
self.divided = False
self.children: List[QuadTree] = []
self.depth = 0 # root depth; children will override
def subdivide(self):
x0, y0, x1, y1 = self.boundary.xmin, self.boundary.ymin, self.boundary.xmax, self.boundary.ymax
xm, ym = (x0 + x1) / 2, (y0 + y1) / 2
boxes = [
AABB(xm, ym, x1, y1), # NE
AABB(x0, ym, xm, y1), # NW
AABB(x0, y0, xm, ym), # SW
AABB(xm, y0, x1, ym), # SE
]
self.children = [QuadTree(b, self.capacity, self.max_depth) for b in boxes]
for c in self.children:
c.depth = self.depth + 1
# redistribute existing points
for p in self.points:
self._insert_into_children(p)
self.points.clear()
self.divided = True
def _insert_into_children(self, p: Point) -> bool:
for child in self.children:
if child.boundary.contains(p):
return child.insert(p)
# Epsilon clamp to handle border floating-point errors
eps = 1e-9
x, y = p
x = min(max(x, self.boundary.xmin), self.boundary.xmax - eps)
y = min(max(y, self.boundary.ymin), self.boundary.ymax - eps)
for child in self.children:
if child.boundary.contains((x, y)):
return child.insert((x, y))
return False
def insert(self, p: Point) -> bool:
if not self.boundary.contains(p):
return False
if not self.divided and len(self.points) < self.capacity:
self.points.append(p)
return True
if not self.divided:
if self.depth >= self.max_depth:
self.points.append(p) # force insert at max depth
return True
self.subdivide()
return self._insert_into_children(p)
def query_range(self, window: AABB, out: Optional[List[Point]] = None) -> List[Point]:
if out is None:
out = []
if not self.boundary.intersects(window):
return out
if self.divided:
for child in self.children:
child.query_range(window, out)
else:
for p in self.points:
if window.contains(p):
out.append(p)
return out
# 사용 예시
if __name__ == "__main__":
qt = QuadTree(AABB(0, 0, 1000, 1000), capacity=16, max_depth=18)
import random
for _ in range(100_000):
qt.insert((random.random()*1000, random.random()*1000))
result = qt.query_range(AABB(100, 100, 300, 300))
print("Result size:", len(result))병합 기준을 capacity의 0.5~0.75로 두면 분할과 병합의 진동을 줄일 수 있다. 반개구간 경계 규칙과 epsilon 보정은 모든 비교 지점에 같은 방식으로 적용한다. 노드 아레나 할당과 포인트 SOA 구조는 CPU 캐시 효율 개선에 사용할 수 있다.