# 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
- Installation
- Disclaimer & Warnings
- Design
- Usage
- Dependencies
- Contributing
- Contact
- Acknowledgements
- License

## Requirements

- Swift 5.1+

## Installation

### Swift Package Manager

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

## 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 |

## You may find interesting

## Dependencies

## Used By

Total: 0

## Releases

## Bug Fixes - 2020-01-04 18:10:11

## Bug Fixes - 2020-01-04 18:07:06

## More efficient storage model - 2020-01-03 17:27:14

RTree files should be much smaller now.

## Correctly order nearest neighbor search heap - 2019-11-10 16:22:41

## Examples corrections - 2019-11-10 13:13:56

## Nearest Neighbor Bug Fix - 2019-11-10 12:28:51

## Bug Fixes - 2019-11-10 03:35:53

## Bug Fixes - 2019-11-10 02:59:14

## Allow tree files to be moved - 2019-11-10 02:46:52

## Read Only R-Trees - 2019-11-09 21:59:57

## Bug Fixes - 2019-11-07 17:26:22

Add public initializer to BoundingRectangle

## Bug Fixes - 2019-11-07 17:17:52

Make the main initializer for RTree public

## R*-Trees! - 2019-11-06 20:19:23

An on-disk, Codable R*-Tree for Swift.