RTree 是一个基于磁盘的，实现了Codable协议的 R*-Tree，用于搜索。
RTree 是 Rust crate Spade 的 N 维 R*-Tree 的移植版本，修改为将树存储在磁盘上而不是内存中。 它只能执行插入和最近邻查询。
dependencies: [
.package(
name: "RTree",
url: "https://github.com/emma-k-alexandra/RTree.git",
from: "2.2.0"
)
]
RTree 以 R*-Tree 预期的速度执行最近邻搜索。 RTree 在磁盘上使用的空间比预期多得多，并且插入效率极低。 RTree 目前不支持删除或更新记录。
这个 R*-Tree 旨在专门使用 Swift，并为在 N 维对象上执行最近邻查询提供一个通用接口。
为了使用 RTree，您需要实现您自己的实现了 SpatialObject 协议的结构体和实现了 PointN 协议的向量类型。 有关示例，请参见 RTreeTests.swift 或 用法
首先，您需要一个实现了 SpatialObject 协议的类型来存储在 R-Tree 中。 为了演示目的，我将实现一个二维向量和 SpatialObject，它将存储一个自定义字段。
二维向量
import RTree
struct Point2D: PointN {
typealias Scalar = Double
var x: Scalar
var y: Scalar
init(x: Scalar, y: Scalar) {
self.x = x
self.y = y
}
func dimensions() -> Int {
2
}
static func from(value: Double) -> Self {
Point2D(x: value, y: value)
}
subscript(index: Int) -> Scalar {
get {
if index == 0 {
return self.x
} else {
return self.y
}
}
set(newValue) {
if index == 0 {
self.x = newValue
} else {
self.y = newValue
}
}
}
}
extension Point2D: Equatable {
static func == (lhs: Point2D, rhs: Point2D) -> Bool {
lhs.x == rhs.x && lhs.y == rhs.y
}
}
SpatialObject
struct Element: SpatialObject {
typealias Point = Point2D
let point: Point
let hello = "world"
func minimumBoundingRectangle() -> BoundingRectangle<Point2D> {
BoundingRectangle(lower: self.point, upper: self.point)
}
func distanceSquared(point: Point2D) -> Double {
pow(point.x - self.point.x, 2) + pow(point.y - self.point.y, 2)
}
}
extension Element: Equatable {
static func == (lhs: Element, rhs: Element) -> Bool {
lhs.point == rhs.point && lhs.hello == rhs.hello
}
}
然后，我可以创建一个 R*-Tree，它存储基于 Point2D 的 Elements
var tree = try RTree<Element>(path: path)
let zerozero = Element(point: Point2D(x: 0, y: 0))
let oneone = Element(point: Point2D(x: 1, y: 1))
let threethree = Element(point: Point2D(x: 3, y: 3))
try tree.insert(oneone)
try tree.insert(threethree)
tree.nearestNeighbor(zerozero.point)! == oneone
无
欢迎发送问题和意见至 emma@emma.sh.
Codable 的。RTree 在 MIT 许可证下发布。 有关详细信息，请参见 LICENSE。