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

Class PeanoSpatialSorter

java.lang.Object

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)",
           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 and Description
static class	PeanoSpatialSorter.Parameterizer Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
static PeanoSpatialSorter	STATIC Static instance.

Constructor Summary

Constructors

Constructor and Description
PeanoSpatialSorter() Constructor, use STATIC instead.

Method Summary

Modifier and Type	Method and 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

Methods inherited from interface de.lmu.ifi.dbs.elki.math.spacefillingcurves.SpatialSorter

computeMinMax, sort

Field Detail

STATIC

public static final PeanoSpatialSorter STATIC

Static instance.

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