Class KdTree

java.lang.Object
org.ddogleg.nn.alg.KdTree

public class KdTree
extends Object

K-D Tree is short for k-dimensional tree and is a binary tree data structure used for quickly finding the nearest-neighbor of a k-dimensional point in a set. Each point can optionally have data associated with it. The tree is structured such that at each node has a point and two children. All points in the set with values <= to the node's point in the specified dimension/axis are on the the left and >= to the right. A leaf will have no children.

NOTE: If multiple points have identical values then there will be a node for each point.

NOTE: If there is more than one point with an identical value to the node's point, then the identical points can go in either the left or right branches.

  • Field Details

    • N

      public int N
    • root

      @Nullable public @Nullable KdTree.Node root
  • Constructor Details

    • KdTree

      public KdTree​(int N)
      Specifies the type of points it can process.
      Parameters:
      N - Number of elements in a point
    • KdTree

      public KdTree()