【译】Swift算法俱乐部-四叉树

本文是对 Swift Algorithm Club 翻译的一篇文章。 Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。 🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/QuadTree

四叉树（QuadTree）

四叉树是一种树，其中每个内部（非叶节点）节点有四个子节点。

问题

考虑以下问题：您需要存储多个点（每个点是一对X和Y坐标），然后您需要回答哪些点位于某个矩形区域。一个天真的解决方案是将点存储在一个数组中，然后迭代这些点并分别检查每个点。该解决方案花费O(n)。

更好的方法

四叉树最常用于通过递归地将其细分为四个区域（象限）来划分二维空间。让我们看看如何使用四叉树来存储点数。

树中的每个节点代表一个矩形区域，并存储所有位于其区域中的有限数量（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
  }

  ...
}

一旦达到叶节点的限制，就会向节点添加四个子节点，它们代表节点rect的topLeft，topRight，bottomLeft，bottomRight象限;rect中的每个结果点都将传递给其中一个子节点。因此，总是将新点添加到叶节点。

extension QuadTreeNode {

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

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

    switch type {
    case .internal(let children):
      // pass the point to one of the children
      for child in children {
        if child.add(point: point) {
          return true
        }
      }
      return false // should never happen
    case .leaf:
      points.append(point)
      // if the max capacity was reached, become an internal node
      if points.count == QuadTreeNode.maxPointCapacity {
        subdivide()
      }
    }
    return true
  }

  private func subdivide() {
    switch type {
    case .leaf:
      type = .internal(children: Children(parentNode: self))
    case .internal:
      preconditionFailure("Calling subdivide on an internal node")
    }
  }
}

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 the node's rect and the given rect don't intersect, return an empty array,
    // because there can't be any points that lie the node's (or its children's) rect and
    // in the given rect
    if !self.rect.intersects(rect: rect) {
      return []
    }

    var result: [Point] = []

    // collect the node's points that lie in the rect
    for point in points {
      if rect.contains(point: point) {
        result.append(point)
      }
    }

    switch type {
    case .leaf:
      break
    case .internal(children: let children):
      // recursively add children's points that lie in the rect
      for childNode in children {
        result.append(contentsOf: childNode.points(inRect: rect))
      }
    }

    return result
  }
}

在最坏的情况下，添加点和搜索仍然可以占用O(n)，因为树不以任何方式平衡。但是，平均而言，它的运行速度明显更快（与O(log n)相当）。

扩展阅读

在MapView中显示大量对象 - 四叉树的一个很好的用例（Thoughtbot Article）

四叉树的维基百科

作者：Timur Galimov
翻译：Andy Ron
校对：Andy Ron