本文是对 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）
