KD树

Swift 5.0 CI Status

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

如果您想了解更多，您可以观看我在 funswiftconf 上所做的 这个演讲。

创建KD树的可视化动画

Example Illustration

简单来说，树的创建方式如下：

  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)

然后，您可以在这棵树上使用 insert()、remove()、map()、filter()、reduce() 和 forEach()，并获得预期的结果，因为 KDTree 符合 Sequence 协议。

应用

K近邻

Example Illustration

给定一个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)。

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

Performance Results

镶嵌

Tesselation Example

范围搜索

还可以使用 KDTree 来搜索一系列值，方法是使用

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

一个例子是基于包含12万颗星星的 HYG数据库。 在这里，我们看到了赤经 10h 和赤纬 35° 附近的一片天空，其中 KDTree 算法可用于获取 iPhone 屏幕指向区域内的星星，还可以通过 NN 找到用户点击位置附近最接近的星星

实现示例

Example 文件夹中的示例应用程序展示了 iOS 上的一些演示实现。

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

安装

在 Xcode 中，打开 File -> Swift Packages -> Add Package Dependency 并将项目 URL 复制到文本字段中

https://github.com/Bersaelor/KDTree

或者将以下内容添加到您的 Package.swift 依赖项中

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

截至 2020 年，Swift 包管理器涵盖了所有用例并且非常方便，因此我们认为不再需要支持其他包管理器，例如 Carthage 或 Cocoapods。

许可证

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