Package net.imglib2.kdtree

Class KDTreePositions

  • Direct Known Subclasses:
    KDTreePositions.Flat, KDTreePositions.Nested
    public abstract class KDTreePositions
extends java.lang.Object
    Stores the positions of the nodes in a KDTree and provides access to them.

    Currently, there are two implementations:

    • KDTreePositions.Nested stores the positions as a double[][] where positions[d][i] is dimension d of the i-th point. This allows for a total of 2^31-8 nodes but doesn't keep the positions contiguous in memory.
    • KDTreePositions.Flat stores the positions as a double[] where positions[d + i*n] is dimension d of the i-th point, with n the number of dimensions. This means that the positions are contiguous in memory but the number of nodes is limited to (2^31-8)/n.
    asNestedArray() returns positions in nested double[][] (which is created if class is KDTreePositions.Flat). asFlatArray() returns flat double[] if class is KDTreePositions.Flat, otherwise null.

    • Field Detail

      • numDimensions

        final int numDimensions

      • numPoints

        final int numPoints

    • Constructor Detail

      • KDTreePositions

        KDTreePositions​(int numDimensions,
                int numPoints)

    • Method Detail

      • get

        public abstract double get​(int i,
                           int d)
        Get the coordinates of the node i in dimension d.
        Returns:
        the coordinate

      • asFlatArray

        public abstract double[] asFlatArray()
        Get positions of points in the tree as a flat double[] array where positions[d + i*n] is dimension d of the i-th point.

        For serialisation and usage by the tree.

        Internal storage may be a NESTED double[][] array. In this case, flatPositions() returns null.

      • asNestedArray

        public abstract double[][] asNestedArray()
        Get positions of points in the tree as a nested double[][] array where positions[d][i] is dimension d of the i-th point.

        For serialisation and usage by the tree.

        Internal storage may be flattened into single double[] array. In this case, the nested double[][] array is created here.

      • createBoundingBox

        abstract RealInterval createBoundingBox()

      • layout

        public abstract KDTreePositions.PositionsLayout layout()
        Get the internal layout of positions.

        Positions are stored in either FLAT or NESTED layout. With NESTED layout, positions are stored as a nested double[][] array where positions[d][i] is dimension d of the i-th point. With FLAT layout, positions are stored as a flat double[] array, where positions[d + i*n] is dimension d of the i-th point, with n the number of dimensions.

      • numDimensions

        public int numDimensions()
        Returns:
        dimensionality of points in the tree

      • numPoints

        public int numPoints()
        Returns:
        number of points in the tree

      • createNested

        public static KDTreePositions createNested​(double[][] positions)
        Create KDTreePositions with NESTED layout().

      • createFlat

        public static KDTreePositions createFlat​(double[] positions,
                                         int numDimensions)
        Create KDTreePositions with FLAT layout().