Class BinarySplitSpatialSorter

  • All Implemented Interfaces:
    SpatialSorter

    @Reference(authors="J. L. Bentley",
               title="Multidimensional binary search trees used for associative searching",
               booktitle="Communications of the ACM 18(9)",
               url="https://doi.org/10.1145/361002.361007",
               bibkey="DBLP:journals/cacm/Bentley75")
    public class BinarySplitSpatialSorter
    extends java.lang.Object
    implements SpatialSorter
    Spatially sort the data set by repetitive binary splitting, circulating through the dimensions. This is essentially the bulk-loading proposed for the k-d-tree, as it will produce a perfectly balanced k-d-tree. The resulting order is the sequence in which objects would then be stored in the k-d-tree.

    Note that when using this for bulk-loading an R-tree, the result will not be a k-d-tree, not even remotely similar, as the splits are not preserved.

    Reference (for the bulk-loading):

    J. L. Bentley
    Multidimensional binary search trees used for associative searching
    Communications of the ACM 18(9)

    Since:
    0.5.0
    Author:
    Erich Schubert
    • Constructor Detail

      • BinarySplitSpatialSorter

        public BinarySplitSpatialSorter()
        Constructor, use STATIC instead!
    • Method Detail

      • sort

        public void sort​(java.util.List<? extends SpatialComparable> objs,
                         int start,
                         int end,
                         double[] minmax,
                         int[] dims)
        Description copied from interface: SpatialSorter
        Sort part of the list (start to end).
        Specified by:
        sort in interface SpatialSorter
        Parameters:
        objs - the spatial objects to be sorted
        start - First index to sort (e.g., 0)
        end - End of range (e.g., site())
        minmax - Array with dim pairs of (min, max) of value ranges
        dims - Dimensions to sort by, for indexing vectors and minmax.
      • binarySplitSort

        private void binarySplitSort​(java.util.List<? extends SpatialComparable> objs,
                                     int start,
                                     int end,
                                     int depth,
                                     int numdim,
                                     int[] dims,
                                     BinarySplitSpatialSorter.Sorter comp)
        Sort the array using a binary split in dimension curdim, then recurse with the next dimension.
        Parameters:
        objs - List of objects
        start - Interval start
        end - Interval end (exclusive)
        depth - Recursion depth
        numdim - Number of dimensions
        dims - Dimension indexes to sort by.
        comp - Comparator to use