QuadTree

쿼드트리는 각 내부 노드(리프 노드가 아닌 노드)가 네 개의 자식 노드를 가지는 트리 구조이다.

문제

다음과 같은 문제를 생각해 보자: 여러 점을 저장해야 하는데, 각 점은 X와 Y 좌표 쌍으로 이루어져 있다. 그리고 특정 직사각형 영역 안에 있는 점들을 찾아야 한다. 단순한 방법은 점들을 배열에 저장한 후, 각 점을 하나씩 확인하며 직사각형 영역 안에 있는지 검사하는 것이다. 하지만 이 방법은 O(n)의 시간 복잡도를 가진다.

더 나은 접근 방식

쿼드트리는 주로 2차원 공간을 재귀적으로 네 개의 영역(쿼드런트)으로 나누어 분할하는 데 사용된다. 이제 쿼드트리를 사용해 점을 저장하는 방법을 살펴보자.

트리의 각 노드는 직사각형 영역을 나타내며, 해당 영역에 속한 점들을 최대 maxPointCapacity 개수만큼 저장한다.

class QuadTreeNode {

  enum NodeType {
    case leaf
    case `internal`(children: Children)
  }

  struct Children {
    let leftTop: QuadTreeNode
    let leftBottom: QuadTreeNode
    let rightTop: QuadTreeNode
    let rightBottom: QuadTreeNode

    ...
  }

  var points: [Point] = []
  let rect: Rect
  var type: NodeType = .leaf

  static let maxPointCapacity = 3

  init(rect: Rect) {
    self.rect = rect
  }

  ...
}

리프 노드의 한계에 도달하면, 네 개의 자식 노드가 추가되고 이들은 노드의 직사각형 영역을 topLeft, topRight, bottomLeft, bottomRight 쿼드런트로 나눈다. 이후 해당 영역에 추가되는 점들은 자식 노드 중 하나로 전달된다. 따라서 새로운 점은 항상 리프 노드에 추가된다.

extension QuadTreeNode {

  @discardableResult
  func add(point: Point) -> Bool {

    if !rect.contains(point: point) {
      return false
    }

    switch type {
    case .internal(let children):
      // 점을 자식 노드 중 하나로 전달
      for child in children {
        if child.add(point: point) {
          return true
        }
      }
      return false // 절대 발생하지 않음
    case .leaf:
      points.append(point)
      // 최대 용량에 도달하면 내부 노드로 변환
      if points.count == QuadTreeNode.maxPointCapacity {
        subdivide()
      }
    }
    return true
  }

  private func subdivide() {
    switch type {
    case .leaf:
      type = .internal(children: Children(parentNode: self))
    case .internal:
      preconditionFailure("내부 노드에서 subdivide 호출")
    }
  }
}

extension Children {

  init(parentNode: QuadTreeNode) {
    leftTop = QuadTreeNode(rect: parentNode.rect.leftTopRect)
    leftBottom = QuadTreeNode(rect: parentNode.rect.leftBottomRect)
    rightTop = QuadTreeNode(rect: parentNode.rect.rightTopRect)
    rightBottom = QuadTreeNode(rect: parentNode.rect.rightBottomRect)
  }
}

주어진 영역에 속한 점을 찾기 위해 이제 트리를 위에서 아래로 순회하며 적합한 점들을 수집할 수 있다.

class QuadTree {

  ...

  let root: QuadTreeNode

   public func points(inRect rect: Rect) -> [Point] {
    return root.points(inRect: rect)
  }
}

extension QuadTreeNode {
  func points(inRect rect: Rect) -> [Point] {

    // 노드의 직사각형 영역과 주어진 영역이 교차하지 않으면 빈 배열 반환
    // 노드(또는 자식 노드)의 영역과 주어진 영역에 동시에 속하는 점이 없음
    if !self.rect.intersects(rect: rect) {
      return []
    }

    var result: [Point] = []

    // 노드의 점 중 주어진 영역에 속하는 점을 수집
    for point in points {
      if rect.contains(point: point) {
        result.append(point)
      }
    }

    switch type {
    case .leaf:
      break
    case .internal(children: let children):
      // 주어진 영역에 속하는 자식 노드의 점을 재귀적으로 추가
      for childNode in children {
        result.append(contentsOf: childNode.points(inRect: rect))
      }
    }

    return result
  }
}

점을 추가하거나 검색하는 작업은 최악의 경우 여전히 O(n) 시간이 걸릴 수 있다. 트리가 어떤 식으로도 균형을 이루지 않기 때문이다. 그러나 평균적으로는 훨씬 빠르게 동작하며, 이는 O(log n)에 가까운 성능을 보인다.

함께 보기

맵뷰에서 대량의 객체를 표시하는 방법 - 쿼드트리의 훌륭한 활용 사례 (Thoughtbot 글)

더 많은 정보는 위키피디아에서 확인할 수 있다.

Swift Algorithm Club을 위해 Timur Galimov가 작성