RTree is an on-disk, Codable R*-Tree for searching.
RTree is a port of the Rust crate Spade's N-Dimentional R*-Tree, modified to store the tree on disk rather than in memory. It only can perform inserts and nearest neighbor queries.
- Requirements
- Installation
- Disclaimer & Warnings
- Design
- Usage
- Dependencies
- Contributing
- Contact
- Acknowledgements
- License
- Swift 5.1+
- iOS 13, watchOS 6, macOS 10.15, tvOS 15
dependencies: [
.package(
name: "RTree",
url: "https://github.com/emma-k-alexandra/RTree.git",
from: "2.2.0"
)
]RTree performs nearest neighbor searches at the expected speed of a R*-Tree. RTree uses far more space than expected on disk, and inserts are extemely inefficient. RTree does not currently support deletion or updating of records.
This R*-Tree is designed to use exclusively Swift, and provide a general interface for doing nearest neighbor queries on N-dimensional objects.
Expect to a implement your own SpatialObject-implementing structure and PointN-implementing vector type in order to use RTree. For an example, see RTreeTests.swift or Usage
First, you need a SpatialObject-implementing type to store in the R-Tree. For demonstration purposes, I will implement a 2-dimensional vector and SpatialObject that will store a custom field.
2-dimensional vector:
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
}
}Then, I'm able to create an R*-Tree that stores Elements over Point2D:
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)! == oneoneNone
Feel free to email questions and comments to emma@emma.sh.
- Spade's developers and contributors for making a very simple to understand R-Tree implementation that is also (Rust's equivalent to)
Codable.
RTree is released under the MIT license. See LICENSE for details.