Latest 0.4.0
Homepage https://github.com/Bersaelor/KDTree
License MIT
Platforms ios 8.0, osx 10.10, tvos 9.2, requires ARC
Authors

Swift 3.1
Version
License
Platform
CI Status

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.

Visual animation of creating a KDTree:

Example Illustration

Very simply put, a tree is created by:

  1. find the median point in the current direction
  2. bisect along the hyperplane(=line in 2D) going through the current median
  3. go one step deeper, same thing with next axis

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, 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(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:

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 thousend stars. Here we see a piece of the sky around 12° ascension and 10° 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:

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.

Latest podspec

{
    "name": "KDTree",
    "version": "0.4.0",
    "summary": "Swift implementation of a k-dimensional binary space partitioning tree.",
    "description": "Swift implementation of a k-dimensional binary space partitioning tree. Useful for O(log(N)) nearest neighbour searches.",
    "homepage": "https://github.com/Bersaelor/KDTree",
    "screenshots": [
        "https://raw.githubusercontent.com/Bersaelor/KDTree/master/Screenshots/kNearest.png",
        "https://raw.githubusercontent.com/Bersaelor/KDTree/master/Screenshots/tesselations.png"
    ],
    "license": "MIT",
    "authors": {
        "Konrad Feiler": "[email protected]"
    },
    "source": {
        "git": "https://github.com/Bersaelor/KDTree.git",
        "tag": "0.4.0"
    },
    "social_media_url": "https://twitter.com/bersaelor",
    "platforms": {
        "ios": "8.0",
        "osx": "10.10",
        "tvos": "9.2"
    },
    "requires_arc": true,
    "source_files": "Pod/Classes/**/*",
    "pushed_with_swift_version": "3.0"
}

Pin It on Pinterest

Share This