de.lmu.ifi.dbs.elki.math.spacefillingcurves

Class PeanoSpatialSorter

java.lang.Object

de.lmu.ifi.dbs.elki.math.spacefillingcurves.AbstractSpatialSorter

de.lmu.ifi.dbs.elki.math.spacefillingcurves.PeanoSpatialSorter

All Implemented Interfaces:

SpatialSorter

@Reference(authors="G. Peano",
           title="Sur une courbe, qui remplit toute une aire plane",
           booktitle="Mathematische Annalen, 36(1)")
public class PeanoSpatialSorter
extends AbstractSpatialSorter

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)

Author:

Erich Schubert

Constructor Summary

Constructors

Constructor and Description
PeanoSpatialSorter() Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected <T extends SpatialComparable> void	peanoSort(List<T> objs, int start, int end, double[] mms, int[] dims, int depth, long[] bits, boolean desc) Sort by Peano curve.
<T extends SpatialComparable> void	sort(List<T> objs, int start, int end, double[] minmax, int[] dims) Sort part of the list (start to end).

Methods inherited from class de.lmu.ifi.dbs.elki.math.spacefillingcurves.AbstractSpatialSorter

computeMinMax, pivotizeList1D, sort

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

PeanoSpatialSorter

public PeanoSpatialSorter()

Constructor.

Method Detail

sort

public <T extends SpatialComparable> void sort(List<T> objs,
                                      int start,
                                      int end,
                                      double[] minmax,
                                      int[] dims)

Description copied from interface: SpatialSorter

Sort part of the list (start to end).

Type Parameters:

T - actual type we sort

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 <T extends SpatialComparable> void peanoSort(List<T> 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