Quad Tree

Quad Tree는 2차원 공간을 재귀적으로 4개의 영역으로 분할하여 표현하는 트리 기반의 데이터 구조로, 각 노드가 정확히 4개의 자식 노드를 갖는 트리 구조이다.
2차원 공간을 표현하고 관리하는 데 효율적이며, 특히 공간 데이터를 계층적으로 구성하는 데 사용된다.

An Illustration of quad-tree data structure
https://www.researchgate.net/figure/An-Illustration-of-quad-tree-data-structure_fig1_280621405

특징

  1. 계층적 구조: 공간을 재귀적으로 4등분하여 표현한다.
  2. 적응적 분할: 필요에 따라 특정 영역을 더 세밀하게 분할할 수 있다.
  3. 공간 효율성: 데이터 분포에 따라 효율적으로 공간을 분할한다.

장점

  1. 효율적인 공간 검색: 특정 영역의 데이터를 빠르게 검색할 수 있다.
  2. 메모리 효율성: 데이터 밀도에 따라 적응적으로 메모리를 사용한다.
  3. 동적 갱신: 데이터의 삽입과 삭제가 비교적 용이하다.

단점

  1. 불균형 가능성: 데이터 분포에 따라 트리가 불균형해질 수 있다.
  2. 구현 복잡성: 기본적인 트리 구조보다 구현이 복잡할 수 있다.
  3. 메모리 오버헤드: 데이터가 적을 때는 오히려 메모리 사용이 비효율적일 수 있다.

응용

  1. 컴퓨터 그래픽스: 충돌 감지, 가시성 결정 등에 사용된다.
  2. 이미지 처리: 이미지 압축, 영역 분할 등에 활용된다.
  3. 지리 정보 시스템(GIS): 공간 데이터 인덱싱에 사용된다.
  4. 게임 개발: 게임 월드의 효율적인 관리와 렌더링에 활용된다.

동작 원리

  1. 초기화: 전체 2D 공간을 포함하는 루트 노드로 시작한다.
  2. 분할: 특정 조건(예: 데이터 수, 깊이 제한)에 따라 노드를 4개의 자식 노드로 분할한다.
  3. 데이터 할당: 각 데이터를 해당하는 영역의 노드에 할당한다.
  4. 검색: 트리를 순회하며 원하는 영역 또는 조건에 맞는 데이터를 검색한다.

구성 요소

  1. 노드: 공간의 한 영역을 나타내며, 데이터와 자식 노드에 대한 참조를 포함한다.
  2. 경계: 각 노드가 나타내는 2D 공간의 경계를 정의한다.
  3. 데이터: 각 노드에 저장되는 실제 데이터 또는 데이터에 대한 참조이다.

구현 방식

다음은 Python을 사용한 간단한 Quad Tree 구현 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Rectangle:
    def __init__(self, x, y, w, h):
        self.x = x
        self.y = y
        self.w = w
        self.h = h

    def contains(self, point):
        return (point.x >= self.x - self.w and
                point.x < self.x + self.w and
                point.y >= self.y - self.h and
                point.y < self.y + self.h)

class QuadTree:
    def __init__(self, boundary, capacity):
        self.boundary = boundary
        self.capacity = capacity
        self.points = []
        self.divided = False
        self.northwest = None
        self.northeast = None
        self.southwest = None
        self.southeast = None

    def insert(self, point):
        if not self.boundary.contains(point):
            return False

        if len(self.points) < self.capacity:
            self.points.append(point)
            return True

        if not self.divided:
            self.subdivide()

        return (self.northwest.insert(point) or
                self.northeast.insert(point) or
                self.southwest.insert(point) or
                self.southeast.insert(point))

    def subdivide(self):
        x = self.boundary.x
        y = self.boundary.y
        w = self.boundary.w / 2
        h = self.boundary.h / 2

        nw = Rectangle(x - w, y - h, w, h)
        self.northwest = QuadTree(nw, self.capacity)
        ne = Rectangle(x + w, y - h, w, h)
        self.northeast = QuadTree(ne, self.capacity)
        sw = Rectangle(x - w, y + h, w, h)
        self.southwest = QuadTree(sw, self.capacity)
        se = Rectangle(x + w, y + h, w, h)
        self.southeast = QuadTree(se, self.capacity)

        self.divided = True

# 사용 예시
boundary = Rectangle(0, 0, 100, 100)
qt = QuadTree(boundary, 4)
for _ in range(20):
    point = Point(random.uniform(-100, 100), random.uniform(-100, 100))
    qt.insert(point)

참고 및 출처