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

Class HilbertSpatialSorter

java.lang.Object

de.lmu.ifi.dbs.elki.math.spacefillingcurves.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

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	HilbertSpatialSorter.HilbertRef Object used in spatial sorting, combining the spatial object and the object ID.
static class	HilbertSpatialSorter.Parameterizer Parameterization class.

Field Summary

Fields

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

Constructor Summary

Constructors

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

Method Summary

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

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

computeMinMax, sort

Field Detail

STATIC

public static final HilbertSpatialSorter STATIC

Static instance.

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