Options
All
  • Public
  • Public/Protected
  • All
Menu

Class Kdtree

Kdtree

author

Alexander Rose alexander.rose@weirdbyte.de, 2016

author

Roman Bolzern roman.bolzern@fhnw.ch, 2013

author

I4DS http://www.fhnw.ch/i4ds, 2013

license

MIT License http://www.opensource.org/licenses/mit-license.php

description

k-d Tree for typed arrays of 3d points (e.g. for Float32Array), in-place provides fast nearest neighbour search

Based on https://github.com/ubilabs/kd-tree-javascript by Ubilabs

Further information (including mathematical properties) http://en.wikipedia.org/wiki/Binary_tree http://en.wikipedia.org/wiki/K-d_tree

example

points: [x, y, z, x, y, z, x, y, z, ...] metric: function(a, b){ return Math.pow(a[0]-b[0], 2) + Math.pow(a[1]-b[1], 2) + Math.pow(a[2]-b[2], 2); }

param

points

param

metric

Hierarchy

  • Kdtree

Index

Constructors

constructor

Properties

atomIndices

atomIndices: Uint32Array

currentNode

currentNode: number = 0

indices

indices: Uint32Array

kdtree

kdtree: _Kdtree

maxDepth

maxDepth: number = 0

metric

metric: (a: NumberArray, b: NumberArray) => number

Type declaration

nodes

nodes: Int32Array

points

points: Float32Array

rootIndex

rootIndex: number

Methods

buildTree

  • buildTree(depth: number, parent: number, arrBegin: number, arrEnd: number): number
  • Parameters

    • depth: number
    • parent: number
    • arrBegin: number
    • arrEnd: number

    Returns number

getNodeDepth

  • getNodeDepth(nodeIndex: number): number

nearest

  • nearest(point: NumberArray, maxNodes: number, maxDistance: number): [number, number][]
  • find nearest points

    Parameters

    • point: NumberArray

      array of size 3

    • maxNodes: number

      max amount of nodes to return

    • maxDistance: number

      maximum distance of point to result nodes

    Returns [number, number][]

    array of point, distance pairs

verify

  • verify(nodeIndex?: undefined | number, depth?: number): number
  • Parameters

    • Optional nodeIndex: undefined | number
    • Default value depth: number = 0

    Returns number

Generated using TypeDoc