Bersaelor/KDTree

Swift implementation of a k-dimensional binary space partitioning tree.

Usage

Import the package in your *.swift file:

import KDTree

Make sure your data values conforom to

public protocol KDTreePoint: Equatable {
  static var dimensions: Int { get }
  func kdDimension(_ dimension: Int) -> Double
  func squaredDistance(to otherPoint: Self) -> Double
}

(CGPoint conforms to KDTreePoint as part of the package)

Then you can grow your own Tree:

extension CustomDataPoint: KDTreePoint { ... }

let dataValues: [CustomDataPoint] = ...

var tree: KDTree<CGPoint> = KDTree(values: dataValues)

Then you can insert(), remove(), map(), filter(), reduce() and forEach() on this tree with the expected results, as KDTree conforms to Sequence.

Applications

K-Nearest Neighbour:

[Example Illustration]

Given a KDTree:

var tree: KDTree<CGPoint> = KDTree(values: points)

we can retrieve the nearest Neighbour to a test point like so

let nearest: CGPoint? = tree.nearest(to: point)

or the get the 10 nearest neighbours

let nearestPoints: [CGPoint] = tree.nearestK(10, to: point)

Complexity is O(log N), while brute-force searching through an Array is of cource O(N).

Preliminary performance results can be gained by running the unit tests, the load example has 10.000 random points in [-1,1]x[-1,1] and find the nearest points for 500 test points:

[Performance Results]

Tesselations:

[Tesselation Example]

Range-Search:

It's also possible to use the KDTree to search for a range of values using:

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

One example is based on the HYG Database of 120 thousand stars. Here we see a piece of the sky around 10h right ascension and 35° declination where the KDTree algorithm can be used to both get the stars in the area the iPhone screen is pointing at and also find the closest Star to a position the user is tapping via NN:

Examples of Implementation

The example app in the Example folder shows some demo implementations on iOS.

KDTree can also be used as a package in a server-side-swift app. StarsOnKitura is one example that returns stars from the HYG database of 120'000 stars using ascension/declination parameters. Live available running on a 64MB instance on IBM Bluemix.

Installation

In Xcode, open File -> Swift Packages -> Add Package Dependency and copy the project url into the text field:

https://github.com/Bersaelor/KDTree

Or add the following to your Package.swift dependencies

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

As of 2020 the Swift package manager covers all use cases and is super convenient, so we felt that supporting other package managers like Carthage or Cocoapods is no longer necessary.

License

KDTree is available under the MIT license. See the LICENSE file for more info.

Package Metadata

Repository: Bersaelor/KDTree

Stars: 166

Forks: 28

Open issues: 5

Default branch: master

Primary language: swift

License: MIT

README: README.md