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

Class HilbertSpatialSorter

java.lang.Object

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

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

All Implemented Interfaces:

SpatialSorter

@Reference(authors="D. Hilbert",
           title="\u00dcber die stetige Abbildung einer Linie auf ein Fl\u00e4chenst\u00fcck",
           booktitle="Mathematische Annalen, 38(3)")
public class HilbertSpatialSorter
extends AbstractSpatialSorter

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
Über die stetige Abbildung einer Linie auf ein Flächenstück
In: Mathematische Annalen, 38(3)

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	HilbertSpatialSorter.HilbertRef<T extends SpatialComparable> Object used in spatial sorting, combining the spatial object and the object ID.

Constructor Summary

Constructors

Constructor and Description
HilbertSpatialSorter() Constructor.

Method Summary

Methods

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.
<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

HilbertSpatialSorter

public HilbertSpatialSorter()

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.

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