Class HilbertSpatialSorter

  • All Implemented Interfaces:
    SpatialSorter

    @Reference(authors="D. Hilbert",
               title="Ueber die stetige Abbildung einer Linie auf ein Fl\u00e4chenst\u00fcck",
               booktitle="Mathematische Annalen, 38(3)",
               url="http://resolver.sub.uni-goettingen.de/purl?GDZPPN002253135",
               bibkey="journals/mathann/Hilbert1891")
    public class HilbertSpatialSorter
    extends java.lang.Object
    implements SpatialSorter
    Sort object along the Hilbert Space Filling curve by mapping them to their Hilbert numbers and sorting them.

    Objects are mapped using 31 bits per dimension.

    Reference:

    D. Hilbert
    Ueber die stetige Abbildung einer Linie auf ein Flächenstück
    In: Mathematische Annalen, 38(3)

    Since:
    0.5.0
    Author:
    Erich Schubert
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      static long[] coordinatesToHilbert​(byte[] coords, int bitsperdim, int offset)
      Interleave one byte per dimension (using the "bitsperdim" highest bits) to a hilbert address.
      static long[] coordinatesToHilbert​(int[] coords, int bitsperdim, int offset)
      Interleave one int per dimension (using the "bitsperdim" highest bits) to a hilbert address.
      static long[] coordinatesToHilbert​(long[] coords, int bitsperdim, int offset)
      Interleave one long per dimension (using the "bitsperdim" highest bits) to a hilbert address.
      static long[] coordinatesToHilbert​(short[] coords, int bitsperdim, int offset)
      Interleave one short per dimension (using the "bitsperdim" highest bits) to a hilbert address.
      static long[] interleaveBits​(byte[] coords, int iter)
      Select the "iter" highest bit from each dimension.
      static long[] interleaveBits​(int[] coords, int iter)
      Select the "iter" highest bit from each dimension.
      static long[] interleaveBits​(long[] coords, int iter)
      Select the "iter" highest bit from each dimension.
      static long[] interleaveBits​(short[] coords, int iter)
      Select the "iter" highest bit from each dimension.
      void sort​(java.util.List<? extends SpatialComparable> objs, int start, int end, double[] minmax, int[] dims)
      Sort part of the list (start to end).
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • HilbertSpatialSorter

        public HilbertSpatialSorter()
        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.
      • coordinatesToHilbert

        public static long[] coordinatesToHilbert​(long[] coords,
                                                  int bitsperdim,
                                                  int offset)
        Interleave one long per dimension (using the "bitsperdim" highest bits) to a hilbert address.
        Parameters:
        coords - Original coordinates
        bitsperdim - Number of bits to use.
        offset - offset
        Returns:
        Hilbert address
      • coordinatesToHilbert

        public static long[] coordinatesToHilbert​(int[] coords,
                                                  int bitsperdim,
                                                  int offset)
        Interleave one int per dimension (using the "bitsperdim" highest bits) to a hilbert address.
        Parameters:
        coords - Original coordinates
        bitsperdim - Number of bits to use.
        offset - offset
        Returns:
        Hilbert address
      • coordinatesToHilbert

        public static long[] coordinatesToHilbert​(short[] coords,
                                                  int bitsperdim,
                                                  int offset)
        Interleave one short per dimension (using the "bitsperdim" highest bits) to a hilbert address.
        Parameters:
        coords - Original coordinates
        bitsperdim - Number of bits to use.
        offset - offset
        Returns:
        Hilbert address
      • coordinatesToHilbert

        public static long[] coordinatesToHilbert​(byte[] coords,
                                                  int bitsperdim,
                                                  int offset)
        Interleave one byte per dimension (using the "bitsperdim" highest bits) to a hilbert address.
        Parameters:
        coords - Original coordinates
        bitsperdim - Number of bits to use.
        offset - offset
        Returns:
        Hilbert address
      • interleaveBits

        public static long[] interleaveBits​(long[] coords,
                                            int iter)
        Select the "iter" highest bit from each dimension.
        Parameters:
        coords - Input coordinates
        iter - Bit position (from highest position)
        Returns:
        One bit per dimension
      • interleaveBits

        public static long[] interleaveBits​(int[] coords,
                                            int iter)
        Select the "iter" highest bit from each dimension.
        Parameters:
        coords - Input coordinates
        iter - Bit position (from highest position)
        Returns:
        One bit per dimension
      • interleaveBits

        public static long[] interleaveBits​(short[] coords,
                                            int iter)
        Select the "iter" highest bit from each dimension.
        Parameters:
        coords - Input coordinates
        iter - Bit position (from highest position)
        Returns:
        One bit per dimension
      • interleaveBits

        public static long[] interleaveBits​(byte[] coords,
                                            int iter)
        Select the "iter" highest bit from each dimension.
        Parameters:
        coords - Input coordinates
        iter - Bit position (from highest position)
        Returns:
        One bit per dimension