Swiftpack.co - Package - emma-k-alexandra/RTree

RTree

RTree is an on-disk, Codable R*-Tree.

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.

Contents

Requirements

  • Swift 5.1+

Installation

Swift Package Manager

dependencies: [
    .package(url: "https://github.com/emma-k-alexandra/RTree.git", from: "2.0.5")
]

Disclaimer & Warnings

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.

Design

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

Usage

Getting started

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)! == oneone

Dependencies

None

Contact

Feel free to email questions and comments to emma@emma.sh.

Acknowledgements

  • Spade's developers and contributors for making a very simple to understand R-Tree implementation that is also (Rust's equivalent to) Codable.

License

RTree is released under the MIT license. See LICENSE for details.

Github

link
Stars: 1
Help us keep the lights on

Dependencies

Releases

v2.0.5 - Nov 10, 2019

v2.0.4 - Nov 10, 2019

v2.0.3 - Nov 10, 2019

v2.0.2 - Nov 10, 2019

v2.0.1 - Nov 10, 2019