• 

KDTree

Swift implementation of a k-dimensional binary space partitioning tree. The KDTree is implemented as an immutable enum, inspired by functional trees from objc.io. KDTree algorithm according to Wikipedia and ubilabs js example.

Example Illustration:

The nodes have labels for their depths, the blue lines go through nodes that partition the plane vertically, the red ones for horizontal partitions.

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(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.

Applications

K-Nearest Neighbour:

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(toElement: point)

or the get the 10 nearest neighbours

let nearestPoints: [CGPoint] = tree.nearestK(10, toElement: 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:

Tesselations:

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)])

I might add an example picture for this later.

Installation

KDTree is available through CocoaPods. To install it, simply add the following line to your Podfile:

pod "KDTree"

To run the example project, clone the repo, and run pod install from the Example directory first.

License

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

Built With

• objective-c
• ruby
• shell
• swift