KDTree

Swift实现的k维二叉空间分割树。KDTree实现为一个不可变的枚举，灵感来源于objc.io函数式树。KDTree算法依据维基百科和ubilabs js示例。

如果您想了解更多，可以观看我在funswiftconf上的演讲此视频。

KDTree创建的视觉动画

简单来说，一个树是通过

1. 在当前方向上找到中点
2. 沿着通过当前中点的超平面（=二维中的线）进行分割
3. 再向下一步，同理于下一个轴

蓝色线条穿过垂直分割平面的节点，红色线条用于水平分割。

用法

在*.swift文件中导入该包

import KDTree

确保您的数据值符合

public protocol KDTreePoint: Equatable {
  static var dimensions: Int { get }
  func kdDimension(_ dimension: Int) -> Double
  func squaredDistance(to otherPoint: Self) -> Double
}

(CGPoint是作为包的一部分符合KDTreePoint)

然后您可以为树添加数据

extension CustomDataPoint: KDTreePoint { ... }

let dataValues: [CustomDataPoint] = ...

var tree: KDTree<CGPoint> = KDTree(values: dataValues)

然后您可以使用KDTree的Sequence协议，在树上进行insert()、remove()、map()、filter()、reduce()和forEach()操作，并期望得到预期结果

应用

K-最近邻算法

给定一个KD树

var tree: KDTree<CGPoint> = KDTree(values: points)

我们可以这样检索测试点的最近邻

let nearest: CGPoint? = tree.nearest(to: point)

或者检索前10个最近的邻居

let nearestPoints: [CGPoint] = tree.nearestK(10, to: point)

复杂度为O(log N)，而通过数组进行暴力搜索的复杂度当然是O(N)。

可以通过运行单元测试来获取初步的性能结果，负载示例包含10,000个随机点在[-1,1]x[-1,1]，并找到100个测试点的最近点

几何分块

范围搜索

还可以使用KD树通过范围搜索来寻找一系列值

let pointsInRange: [CGPoint] = tree.elementsInRange([(0.2, 0.4), (0.45, 0.75)])

一个例子是基于HYG星库，包含12万颗星星。在这里，我们看到赤道大约是10时和赤纬35°的区域，KD树算法可以用来找到iPhone屏幕所指区域内的所有星星，以及通过NN找到用户点击位置最近的星星

实现示例

在“示例”文件夹中的示例应用程序展示了在iOS上的某些演示实现。

KDTree 也可以作为一个包在服务器端Swift应用程序中使用。 StarsOnKitura 是一个例子，它使用ascension/declination参数从HYG数据库中返回120,000颗星星。实时运行在64MB的实例上，可在IBM Bluemix上。

安装

友伴果酱

KDTree 提供通过 友伴果酱 使用。要安装它，只需将以下行添加到您的 Podfile

pod "KDTree"

要运行示例项目，首先克隆仓库，然后从 Example 目录运行 pod install。

Swift 包管理器

将以下内容添加到您的 Package.swift 依赖关系中

.Package(url: "https://github.com/Bersaelor/KDTree", majorVersion: 1, minor: 3),

Carthage

要使用 Carthage 添加 KDTree，请将以下内容添加到您的 Cartfile

github "Bersaelor/KDTree"

许可协议

KDTree 在 MIT 许可协议下可用。有关更多信息，请参阅 LICENSE 文件。