Package com.irurueta.geometry

Class KDTree<P extends Point<P>>

java.lang.Object
com.irurueta.geometry.KDTree<P>
Direct Known Subclasses:
KDTree2D, KDTree3D
public abstract class KDTree<P extends Point<P>> extends Object
Implementation of a k-D tree in an arbitrary dimension. Once a K-D tree is built for a collection of points, it can later be used to efficiently do certain operations such as point location, nearest points searches, etc.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static class 
    KDTree.BoxNode<P extends Point<P>>
    Contains a node of a KD Tree.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected static final double
    BIG
    A very large value to consider as the maximum allowed coordinate value.
    protected KDTree.BoxNode<P>[]
    boxes
    Array of boxes stored in this tree as its nodes.
    static final int
    MIN_PTS
    Minimum number of allowed points to be stored in the tree.
    private static final int
    N_TASKS
    Number of tasks that can be queued.
    private final int
    nPts
    Number of points stored by the tree.
    private final int[]
    ptIndx
    Indices of points going from boxes in the tree to the input collection of points.
    private P[]
    pts
    Array of points containing input collection of points.
    private final int[]
    rPtIndx
    Indices of points going from input collection of points to boxes in the tree.

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    KDTree(Collection<P> pts, Class<P> clazz)
    Constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    protected abstract P
    copyPoint(P point)
    Copies a point.
    protected abstract P
    createPoint(double value)
    Creates a point.
    double
    distance(int jpt, int kpt)
    Gets distance between points located at provided positions on input collection.
    abstract int
    getDimensions()
    Gets number of dimensions supported by this k-D tree implementation on provided list of points.
    private int
    locate(int jpt)
    Gets position of point on input collection for provided internal boxes position.
    KDTree.BoxNode<P>
    locateBox(P pt)
    Gets smallest box containing provided point in the input list of points.
    int
    locateBoxIndex(P pt)
    Gets position of smallest box containing provided point in the input list of points.
    int
    locateNear(P pt, double r, int[] list, int nmax)
    Locates some near points to provided one up to a certain radius of search.
    int
    locateNear(P pt, double r, P[] plist, int nmax)
    Locates near points to provided one up to a certain radius of search defined in a bounding box.
    int
    nearestIndex(P pt)
    Index in provided input list of points of closest point to provided one.
    P
    nearestPoint(P pt)
    Closest point to provided one.
    void
    nNearest(int jpt, int[] nn, double[] dn, int n)
    Gets n nearest point indices to a given one in the input collection.
    void
    nNearest(int jpt, P[] pn, double[] dn, int n)
    Gets n nearest points to a given point index in the input collection.
    void
    nNearest(P pt, int[] nn, double[] dn, int n)
    Gets n nearest point indices to a given point in the input collection.
    void
    nNearest(P pt, P[] pn, double[] dn, int n)
    Gets n nearest points to a given point in the input collection.
    private static int
    selecti(int k, int indxOffset, int[] indx, int n, int arrOffset, double[] arr)
    Makes a selection so that we obtain ordered index at provided k position so that distances are ordered in such a way that resulting array arr contains distances as follows: arr[indx[0 .. k-1]] <= arr[indx[k]] <= arr[indx[k+1 .. n]].
    private static void
    siftDown(double[] heap, int[] ndx, int nn)
    Moves things around.
    private static void
    swap(int[] a, int posA, int[] b, int posB)
    Swaps values.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • MIN_PTS

      public static final int MIN_PTS
      Minimum number of allowed points to be stored in the tree.
      See Also:

    • BIG

      protected static final double BIG
      A very large value to consider as the maximum allowed coordinate value.
      See Also:

    • N_TASKS

      private static final int N_TASKS
      Number of tasks that can be queued.
      See Also:

    • boxes

      protected KDTree.BoxNode<P extends Point<P>>[] boxes
      Array of boxes stored in this tree as its nodes.

    • ptIndx

      private final int[] ptIndx
      Indices of points going from boxes in the tree to the input collection of points. Indices are sorted as the tree is built.

    • rPtIndx

      private final int[] rPtIndx
      Indices of points going from input collection of points to boxes in the tree. This is the reverse of mPtIndx.

    • nPts

      private final int nPts
      Number of points stored by the tree.

    • pts

      private P extends Point<P>[] pts
      Array of points containing input collection of points.

  • Constructor Details

    • KDTree

      protected KDTree(Collection<P> pts, Class<P> clazz)
      Constructor.
      Parameters:
      pts - collection of points to store in the tree.
      clazz - class of point implementation to use.

  • Method Details

    • distance

      public double distance(int jpt, int kpt)
      Gets distance between points located at provided positions on input collection.
      Parameters:
      jpt - index of 1st point.
      kpt - index of 2nd point.
      Returns:
      distance between points or BIG if indices are equal.

    • locateBoxIndex

      public int locateBoxIndex(P pt)
      Gets position of smallest box containing provided point in the input list of points.
      Parameters:
      pt - point to locate its containing box. Does not need to be contained in input collection.
      Returns:
      position of smallest box containing the point.

    • locateBox

      public KDTree.BoxNode<P> locateBox(P pt)
      Gets smallest box containing provided point in the input list of points.
      Parameters:
      pt - point to locate its containing box. Does not need to be contained in input collection.
      Returns:
      smallest box containing the point.

    • nearestIndex

      public int nearestIndex(P pt)
      Index in provided input list of points of closest point to provided one.
      Parameters:
      pt - point to check against. Does not need to be contained in input collection.
      Returns:
      position of closest point.

    • nearestPoint

      public P nearestPoint(P pt)
      Closest point to provided one.
      Parameters:
      pt - point to be checked. Does not need to be contained in input collection.
      Returns:
      closest point.

    • nNearest

      public void nNearest(int jpt, int[] nn, double[] dn, int n)
      Gets n nearest point indices to a given one in the input collection.
      Parameters:
      jpt - index of point to search nearest ones for.
      nn - array containing resulting indices of nearest points up to the number of found points.
      dn - array containing resulting distances to nearest points up to the number of found points.
      n - number of nearest points to find.
      Throws:
      IllegalArgumentException - if number of nearest points is invalid or if length of arrays containing results are not valid either.

    • nNearest

      public void nNearest(P pt, int[] nn, double[] dn, int n)
      Gets n nearest point indices to a given point in the input collection.
      Parameters:
      pt - point to search nearest ones for.
      nn - array containing resulting indices of nearest points up to the number of found points.
      dn - array containing resulting distances to nearest points up to the number of found points.
      n - number of nearest points to find.
      Throws:
      IllegalArgumentException - if number of nearest points is invalid or if length of arrays containing results are not valid either.

    • nNearest

      public void nNearest(int jpt, P[] pn, double[] dn, int n)
      Gets n nearest points to a given point index in the input collection.
      Parameters:
      jpt - index of point to search nearest ones for.
      pn - array containing nearest points up to the number of found points.
      dn - array containing resulting distances to nearest points up to the number of found points.
      n - number of nearest points to find.
      Throws:
      IllegalArgumentException - if number of nearest points is invalid or if length of arrays containing results are not valid either.

    • nNearest

      public void nNearest(P pt, P[] pn, double[] dn, int n)
      Gets n nearest points to a given point in the input collection.
      Parameters:
      pt - point to search nearest ones for.
      pn - array containing nearest points up to the number of found points.
      dn - array containing resulting distances to nearest points up to the number of found points.
      n - number of nearest points to find.
      Throws:
      IllegalArgumentException - if number of nearest points is invalid or if length of arrays containing results are not valid either.

    • locateNear

      public int locateNear(P pt, double r, int[] list, int nmax)
      Locates some near points to provided one up to a certain radius of search. This method only returns up to nmax results, which means that not all points within required radius are returned if more points than provided nmax value are within such radius.
      Parameters:
      pt - point to search nearby.
      r - radius of search.
      list - list where indices of found points are stored up to the number of found points.
      nmax - maximum number of points to search.
      Returns:
      number of found points.
      Throws:
      IllegalArgumentException - if radius is negative or maximum number of points to search is zero or negative, or list where indices are stored is not large enough.

    • locateNear

      public int locateNear(P pt, double r, P[] plist, int nmax)
      Locates near points to provided one up to a certain radius of search defined in a bounding box.
      Parameters:
      pt - point to search nearby.
      r - radius of search defining a bounding box.
      plist - list where found points are stored up to the number of found points.
      nmax - maximum number of points to search.
      Returns:
      number of found points.
      Throws:
      IllegalArgumentException - if radius is negative or maximum number of points to search is zero or negative, or list where points are stored is not large enough.

    • getDimensions

      public abstract int getDimensions()
      Gets number of dimensions supported by this k-D tree implementation on provided list of points.
      Returns:
      number of dimensions.

    • createPoint

      protected abstract P createPoint(double value)
      Creates a point.
      Parameters:
      value - value to be set on point coordinates.
      Returns:
      created point.

    • copyPoint

      protected abstract P copyPoint(P point)
      Copies a point.
      Parameters:
      point - point to be copied.
      Returns:
      copied point.

    • locate

      private int locate(int jpt)
      Gets position of point on input collection for provided internal boxes position.
      Parameters:
      jpt - internal position in the boxes.
      Returns:
      position in the input collection of points.

    • selecti

      private static int selecti(int k, int indxOffset, int[] indx, int n, int arrOffset, double[] arr)
      Makes a selection so that we obtain ordered index at provided k position so that distances are ordered in such a way that resulting array arr contains distances as follows: arr[indx[0 .. k-1]] <= arr[indx[k]] <= arr[indx[k+1 .. n]]. So that positions between 0 and k-1 are not in any particular order but is less than k position, and positions between k+1 and n neither have any particular order but is more than k position.
      Parameters:
      k - sorted position to retrieve.
      indxOffset - offset where indx search starts.
      indx - array to be sorted (i.e. selected).
      n - length of arrays.
      arrOffset - offset of distances array. This is usually equal to indxOffset.
      arr - resulting array containing distances to each selected point.
      Returns:
      index of selected point.

    • siftDown

      private static void siftDown(double[] heap, int[] ndx, int nn)
      Moves things around.
      Parameters:
      heap - array of distances.
      ndx - array of indices.
      nn - number of indices to move.

    • swap

      private static void swap(int[] a, int posA, int[] b, int posB)
      Swaps values.
      Parameters:
      a - 1st array containing values to swap.
      posA - position to be swapped on 1st array.
      b - 2nd array containing values to swap.
      posB - position to be swapped on 2nd array.