쿼드트리

쿼드트리(Quadtree, 사분트리)는 2차원 공간을 4개의 사분면으로 나누고, 필요한 사분면만 다시 4개로 나누기를 되풀이해 만든, 내부 노드마다 자식이 정확히 4개인 트리 자료 구조이다.

개요

뿌리 노드는 전체 영역을 나타내고, 그 자식 4개는 북서(NW)·북동(NE)·남서(SW)·남동(SE) 사분면을 나타낸다. 어떤 사분면이 더 나눌 필요가 없으면(값이 모두 같거나, 들어 있는 점이 정해진 개수 이하이면) 잎 노드가 되고, 그렇지 않으면 다시 4개로 나뉜다. 그래서 단순한 곳은 얕게, 복잡한 곳은 깊게 나뉘어 공간의 밀도에 맞춰 저장량이 달라진다. 1974년 핀켈(Finkel)과 벤틀리(Bentley)가 점 자료 검색용으로 제안했고, 이후 영상·래스터 자료 표현과 공간 색인에 널리 쓰였다. 3차원 공간을 8개로 나누는 것은 옥트리(Octree)다.

종류

종류	나누는 기준	쓰임
영역 쿼드트리(Region Quadtree)	사분면 안의 값(색, 토지 이용 등)이 모두 같아질 때까지 4등분	이진 영상·래스터 지도 압축 → 래스터 데이터 압축
점 쿼드트리(Point Quadtree)	들어오는 점의 좌표를 기준으로 영역을 나눈다(등분 아님)	점 자료 검색
PR 쿼드트리(Point-Region)	영역을 늘 4등분하고, 한 칸에 점이 하나(또는 정한 개수) 이하가 될 때까지 나눈다	위치 기반 서비스의 근처 찾기
MX 쿼드트리	격자 크기를 미리 정하고 점이 있는 칸만 끝까지 나눈다	정해진 해상도의 격자 자료

연산

영역 질의 : 찾는 사각형과 겹치지 않는 사분면은 통째로 건너뛴다. 그래서 전체를 훑지 않고 일부 노드만 본다
최근접 이웃 질의 : 가까운 사분면부터 찾고, 지금까지 찾은 거리보다 먼 사분면은 버린다
삽입·삭제 : 점이 들어가 한 칸의 한도를 넘으면 그 칸을 4개로 나누고, 지워져 한도 밑으로 내려가면 형제 4개를 합친다
균일한 자료는 노드가 적지만, 점이 한곳에 몰리면 트리가 한쪽으로 깊어진다

활용

GIS 의 래스터 자료 압축과 공간 색인 → 다차원 색인구조, 공간 데이터
영상 처리의 영역 분할, 이미지 압축
게임·시뮬레이션의 충돌 검사(가까운 물체끼리만 비교)
지도 서비스의 타일 체계(한 단계 확대할 때마다 타일 하나가 4개로 나뉜다)

비슷한 공간 색인과 비교

구조	나누는 방식	특징
쿼드트리	공간을 4개의 사분면으로 규칙적으로 나눈다	구조가 단순하다. 2차원에 알맞다
k-d 트리	축(x, y, …)을 번갈아 가며 둘로 나눈다(이진 트리)	여러 차원으로 일반화하기 쉽다
R 트리	객체를 감싸는 최소 경계 사각형(MBR)으로 묶는다	공간 데이터베이스에서 선·면 객체 색인에 많이 쓴다

같이 보기