Package elki.math.spacefillingcurves

Class PeanoSpatialSorter

  • All Implemented Interfaces:
    SpatialSorter
    @Reference(authors="G. Peano",
           title="Sur une courbe, qui remplit toute une aire plane",
           booktitle="Mathematische Annalen 36(1)",
           url="http://resolver.sub.uni-goettingen.de/purl?GDZPPN002252376",
           bibkey="journals/mathann/Peano1890")
public class PeanoSpatialSorter
extends java.lang.Object
implements SpatialSorter
    Bulk-load an R-tree index by presorting the objects with their position on the Peano curve.

    The basic shape of this space-filling curve looks like this: 

       3---4   9
   |   |   |
   2   5   8
   |   |   |
   1   6---7
    Which then expands to the next level as: 
       +-+ +-+ +-+ +-+ E
   | | | | | | | | |
   | +-+ +-+ | | +-+
   |         | |
   | +-+ +-+ | | +-+
   | | | | | | | | |
   +-+ | | +-+ +-+ |
       | |         |
   +-+ | | +-+ +-+ |
   | | | | | | | | |
   S +-+ +-+ +-+ +-+
    and so on.

    Reference:

    G. Peano
    Sur une courbe, qui remplit toute une aire plane
    Mathematische Annalen 36(1)

    Since:
    0.5.0
    Author:
    Erich Schubert

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      static class  PeanoSpatialSorter.Par
      Parameterization class.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected void peanoSort​(java.util.List<? extends SpatialComparable> objs, int start, int end, double[] mms, int[] dims, int depth, long[] bits, boolean desc)
      Sort by Peano curve.
      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

      • PeanoSpatialSorter

        public PeanoSpatialSorter()
        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.

      • peanoSort

        protected void peanoSort​(java.util.List<? extends SpatialComparable> objs,
                         int start,
                         int end,
                         double[] mms,
                         int[] dims,
                         int depth,
                         long[] bits,
                         boolean desc)
        Sort by Peano curve.
        Parameters:
        objs - Objects
        start - Start index
        end - End
        mms - Minmax values
        dims - Dimensions index
        depth - Dimension
        bits - Bit set for inversions
        desc - Current ordering