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)

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, BitSet 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,
                                           BitSet 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