한양과기고 에듀테크 수업도구 대시보드

쿼드트리 (Quadtree)

화면에 점 1,000개가 떠다니고, "마우스 주변 40px 안에 있는 점"을 매 프레임 찾아야 한다고 하자. 모든 점과 거리를 재면 프레임마다 1,000번 검사 — O(n). 쿼드트리는 2차원 공간 자체를 네 개의 사분면으로 계속 쪼개서 트리로 만든다. 한 칸에 점이 일정 개수(용량)를 넘으면 그 칸을 다시 4등분한다. 이렇게 하면 질의 영역과 겹치지 않는 칸은 통째로 건너뛸 수 있어, 평균 O(log n) 근처로 줄어든다. 게임 충돌 검사, 이미지 압축, 지도 데이터, 은하 시뮬레이션(Barnes–Hut)이 모두 같은 아이디어를 쓴다.

인터랙티브 데모 — 범위 질의 vs 전수 검사

칸 용량 4

점 개수 (n)

쿼드트리 검사 횟수

전수 검사였다면

범위 안의 점

캔버스 위에서 마우스를 움직이면 질의 사각형이 따라옵니다. 클릭하면 그 자리에 점이 추가됩니다. 노란 칸은 질의 영역과 겹쳐서 내부를 뒤진 칸, 어두운 칸은 통째로 건너뛴 칸입니다. 점이 많아질수록 두 검사 횟수의 차이가 커집니다.

공간이 트리가 되는 과정

1처음엔 루트 한 칸이 화면 전체. 점을 넣을 때마다 이 칸의 목록에 담는다.

2칸의 점이 용량(capacity)을 넘으면 NW·NE·SW·SE 네 자식으로 4등분(subdivide).

3부모가 갖고 있던 점들을 각자 위치에 맞는 자식으로 내려보낸다.

4점이 몰린 곳은 자식이 다시 넘쳐 더 깊게 쪼개지고, 빈 곳은 큰 칸 그대로 남는다 (적응형).

5질의: 사각형이 칸 경계와 겹치지 않으면 그 서브트리 전체를 건너뛴다. 겹치면 자식으로 재귀.

핵심 코드 — insert 와 query

# 경계(x, y, w, h)를 가진 사각 영역 노드
class QuadTree:
    def __init__(self, boundary, capacity=4):
        self.boundary = boundary        # Rect
        self.capacity = capacity
        self.points   = []
        self.divided  = False

    def insert(self, p):
        if not self.boundary.contains(p):
            return False                # 이 칸 밖 → 무시
        if len(self.points) < self.capacity and not self.divided:
            self.points.append(p)
            return True
        if not self.divided:
            self.subdivide()             # 4등분 + 기존 점 재분배
        return (self.nw.insert(p) or self.ne.insert(p) or
                self.sw.insert(p) or self.se.insert(p))

    def query(self, range_rect, found):
        if not self.boundary.intersects(range_rect):
            return found                # ★ 겹침 없음 → 서브트리 통째로 스킵
        for p in self.points:
            if range_rect.contains(p):
                found.append(p)
        if self.divided:
            for child in (self.nw, self.ne, self.sw, self.se):
                child.query(range_rect, found)
        return found

전수 검사와 비교

항목	전수 검사 (배열)	쿼드트리
범위 질의	O(n) — 모든 점 확인	평균 O(log n) + 결과 수
삽입	O(1)	평균 O(log n)
메모리	점 배열만	노드마다 경계·자식 포인터 추가
약점	점이 많으면 느림	점이 한 좌표에 몰리면 무한 분할 → 최대 깊이 제한 필요

게임/물리 엔진: 충돌 후보를 근처 칸으로만 좁혀 broad phase 처리
이미지 압축: 색이 균일한 영역은 큰 칸 하나로 — 스파스한 부분 압축에 유리
GIS·지도: 화면에 보이는 사각형 범위의 마커만 빠르게 추출
Barnes–Hut: 멀리 있는 별 무리를 하나의 질량 중심으로 근사해 중력 계산 O(n log n)
3차원으로 확장하면 옥트리(Octree) — 8분할, 복셀·포인트 클라우드에 사용