Package net.imglib2

Class KDTree<T>

    • Field Detail

      • n

        protected final int n
        the number of dimensions.
      • size

        protected final long size
        the number of nodes in the tree.
      • min

        protected final double[] min
        minimum of each dimension.
      • max

        protected final double[] max
        maximum of each dimension.
    • Constructor Detail

      • KDTree

        public KDTree​(java.util.List<T> values,
                      java.util.List<L> positions)
        Construct a KDTree from the elements in the given list.

        Note that the constructor can be called with the same list for both values == positions if T extends RealLocalizable.

        Parameters:
        values - a list of values
        positions - a list of positions corresponding to the values
      • KDTree

        public KDTree​(IterableRealInterval<T> interval)
        Construct a KDTree from the elements of the given IterableRealInterval.
        Parameters:
        interval - elements in the tree are obtained by iterating this
    • Method Detail

      • verifyDimensions

        protected static <L extends RealLocalizable> boolean verifyDimensions​(java.util.List<L> positions,
                                                                              int n)
        Check whether all positions in the positions list have dimension n.
        Returns:
        true, if all positions have dimension n.
      • makeNode

        protected <L extends RealLocalizableKDTree.ValueNode<T> makeNode​(java.util.List<L> positions,
                                                                           int i,
                                                                           int j,
                                                                           int d,
                                                                           java.util.List<T> values,
                                                                           int[] permutation)
        Construct the tree by recursively adding nodes. The sublist of positions between indices i and j (inclusive) is split at the median element with respect to coordinates in the given dimension d. The median becomes the new node which is returned. The left and right partitions of the sublist are processed recursively and form the left and right subtrees of the node.
        Parameters:
        positions - list of positions
        i - start index of sublist to process
        j - end index of sublist to process
        d - dimension along which to split the sublist
        values - list of values corresponding to permuted positions
        permutation - the index of the values element at index k is permutation[k]
        Returns:
        a new node containing the subtree of the given sublist of positions.
      • makeNode

        protected <L extends RealLocalizableKDTree.ValueNode<T> makeNode​(java.util.ListIterator<L> first,
                                                                           java.util.ListIterator<L> last,
                                                                           int d,
                                                                           java.util.List<T> values,
                                                                           int[] permutation)
        Construct the tree by recursively adding nodes. The sublist of positions between iterators first and last is split at the median element with respect to coordinates in the given dimension d. The median becomes the new node which is returned. The left and right partitions of the sublist are processed recursively and form the left and right subtrees of the node.
        Parameters:
        first - first element of the sublist of positions
        last - last element of the sublist of positions
        d - dimension along which to split the sublist
        values - list of values corresponding to permuted positions
        permutation - the index of the values element at index k is permutation[k]
        Returns:
        a new node containing the subtree of the given sublist of positions.
      • makeNode

        protected <L extends RealLocalizableKDTree.ValueNode<T> makeNode​(java.util.List<L> elements,
                                                                           int i,
                                                                           int j,
                                                                           int d)
        See makeNode(List, int, int, int, List, int[]). Here, no values are attached to the nodes (or rather the positions are the values).
        Parameters:
        elements - list of elements (positions and values at the same time)
        i - start index of sublist to process
        j - end index of sublist to process
        d - dimension along which to split the sublist
      • makeNode

        protected <L extends RealLocalizableKDTree.ValueNode<T> makeNode​(java.util.ListIterator<L> first,
                                                                           java.util.ListIterator<L> last,
                                                                           int d)
        See makeNode(ListIterator, ListIterator, int, List, int[]). Here, no values are attached to the nodes (or rather the positions are the values).
        Parameters:
        first - first element of the sublist to process
        last - last element of the sublist to process
        d - dimension along which to split the sublist
      • makeSamplerNode

        protected KDTree.SamplerNode<T> makeSamplerNode​(java.util.List<RealCursor<T>> elements,
                                                        int i,
                                                        int j,
                                                        int d)
        Construct the tree by recursively adding nodes. The sublist of elements between indices i and j (inclusive) is split at the median element with respect to coordinates in the given dimension d. The median becomes the new node which is returned. The left and right partitions of the sublist are processed recursively and form the left and right subtrees of the node. (The elements of the list are RealCursors which provide coordinates and values.)
        Parameters:
        elements - list of elements (positions and values at the same time)
        i - start index of sublist to process
        j - end index of sublist to process
        d - dimension along which to split the sublist
        Returns:
        a new node containing the subtree of the given sublist of elements
      • getRoot

        public KDTreeNode<T> getRoot()
        Get the root node.
        Returns:
        the root node.
      • toString

        public java.lang.String toString​(KDTreeNode<T> left,
                                         java.lang.String indent)
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • realMin

        public double realMin​(int d)
        Description copied from interface: RealInterval
        Get the minimum in dimension d.
        Specified by:
        realMin in interface RealInterval
        Parameters:
        d - dimension
        Returns:
        minimum in dimension d.
      • realMin

        public void realMin​(double[] m)
        Description copied from interface: RealInterval
        Write the minimum of each dimension into double[].
        Specified by:
        realMin in interface RealInterval
      • realMax

        public double realMax​(int d)
        Description copied from interface: RealInterval
        Get the maximum in dimension d.
        Specified by:
        realMax in interface RealInterval
        Parameters:
        d - dimension
        Returns:
        maximum in dimension d.
      • realMax

        public void realMax​(double[] m)
        Description copied from interface: RealInterval
        Write the maximum of each dimension into double[].
        Specified by:
        realMax in interface RealInterval
      • iterationOrder

        public java.lang.Object iterationOrder()
        Description copied from interface: IterableRealInterval
        Returns the iteration order of this IterableRealInterval. If the returned object equals (Object.equals(Object)) the iteration order of another IterableRealInterval f then they can be copied by synchronous iteration. That is, having an Iterator on this and another Iterator on f, moving both in synchrony will point both of them to corresponding locations in their source domain. In other words, this and f have the same iteration order and means and the same number of elements.
        Specified by:
        iterationOrder in interface IterableRealInterval<T>
        Returns:
        the iteration order of this IterableRealInterval.
        See Also:
        FlatIterationOrder
      • iterator

        public KDTree.KDTreeCursor iterator()
        Specified by:
        iterator in interface java.lang.Iterable<T>
      • cursor

        public KDTree.KDTreeCursor cursor()
        Description copied from interface: IterableRealInterval

        Returns a RealCursor that iterates with optimal speed without calculating the location at each iteration step. Localization is performed on demand.

        Use this where localization is required rarely/ not for each iteration.

        Specified by:
        cursor in interface IterableRealInterval<T>
        Returns:
        fast iterating iterator
      • firstElement

        public T firstElement()
        Description copied from interface: IterableRealInterval
        Get the first element of this IterableRealInterval. This is a shortcut for cursor().next(). This can be used to create a new variable of type T using firstElement().createVariable(), which is useful in generic methods to store temporary results, e.g., a running sum over pixels in the IterableRealInterval.
        Specified by:
        firstElement in interface IterableRealInterval<T>
        Returns:
        the first element in iteration order.