쿼드트리 시각화
2D 공간을 4분할하여 점을 관리하고 범위 검색하는 과정을 관찰합니다
자료구조★★☆
속도
1 / 1전체 점: 50
점 개수50
노드 용량4
경계선점활성 노드
점이 삽입되고 공간이 분할되는 과정을 관찰하세요.
삽입: 점 ({x}, {y})
쿼드트리란?
쿼드트리(Quad Tree)는 2D 공간을 재귀적으로 4등분하여 점 데이터를 효율적으로 저장·검색하는 자료구조입니다. 게임의 충돌 감지, 지도 시스템, 이미지 압축 등에 널리 사용됩니다.
사용 방법
- 1캔버스를 클릭하여 점을 직접 추가하거나, 랜덤/클러스터 버튼을 사용하세요
- 2노드 용량(기본 4)을 조절하여 분할 빈도를 변경하세요
- 3트리 구성 모드에서 점이 삽입·분할되는 과정을 관찰하세요
- 4범위 검색 모드에서 녹색 영역 내 점만 효율적으로 찾는 것을 확인하세요
- 5건너뛴 노드(빨간 점선)는 검사하지 않아도 되는 영역입니다
동작 원리
- 12D 공간을 정의하는 루트 노드 생성
- 2점(point)이 추가되면 해당 사분면에 삽입
- 3노드의 용량(capacity)을 초과하면 4개 자식(NW, NE, SW, SE)으로 분할
- 4점이 밀집된 영역은 더 깊이 분할, 빈 영역은 분할하지 않음
- 5범위 검색: 쿼리 영역과 겹치는 사분면만 재귀 탐색
실무 활용
- •게임 충돌 감지의 공간 분할 — 가까운 객체만 충돌 검사하여 성능 향상
- •지도 서비스(Google Maps)의 관심 지점(POI) 공간 인덱싱
- •이미지 압축 — 색상이 균일한 영역을 하나의 노드로 표현
- •천체 시뮬레이션(N-body)의 Barnes-Hut 알고리즘 — 먼 천체를 하나로 근사
- •GIS(지리정보시스템)의 공간 데이터 인덱싱
비슷한 알고리즘
- •KD-Tree — 2D 이상의 공간을 번갈아 한 축씩 분할. 최근접 이웃 검색에 더 적합하나 동적 삽입이 어려움
- •R-Tree — 직사각형 영역을 계층적으로 묶음. 데이터베이스의 공간 인덱스 표준(PostGIS)
- •옥트리(Octree) — 쿼드트리의 3D 확장. 3D 게임/시뮬레이션의 공간 분할에 사용
- •그리드(Uniform Grid) — 균등 분할로 구현이 단순하나 밀도 차이가 큰 데이터에 비효율
학습 팁
- •노드 용량을 1로 설정하면 모든 점마다 분할이 일어나 트리가 깊어집니다
- •클러스터 패턴에서는 특정 영역만 깊게 분할되는 것을 관찰하세요
- •범위 검색에서 건너뛴 노드 수가 많을수록 효율적인 검색입니다
- •쿼드트리는 점이 고르게 분포할 때 가장 효율적입니다
자주 묻는 질문
Q. 쿼드트리는 어디에 사용되나요?
A. 게임 충돌 감지(근처 객체만 비교), 지도/GIS 시스템(지역 검색), 이미지 압축, 파티클 시뮬레이션 등에 사용됩니다.
Q. 노드 용량은 얼마가 좋은가요?
A. 보통 4~16이 적절합니다. 너무 작으면 트리가 깊어지고, 너무 크면 검색 효율이 떨어집니다.
Q. 시간 복잡도는?
A. 균형 잡힌 경우 삽입·검색 O(log n), 최악(모든 점이 한 곳) O(n)입니다. 범위 검색은 O(n) 대비 평균 O(√n + k)로 훨씬 빠릅니다.