Package elki.math.spacefillingcurves
Class HilbertSpatialSorter
- java.lang.Object
-
- 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 Description private static class
HilbertSpatialSorter.HilbertRef
Object used in spatial sorting, combining the spatial object and the object ID.static class
HilbertSpatialSorter.Par
Parameterization class.
-
Field Summary
Fields Modifier and Type Field Description static HilbertSpatialSorter
STATIC
Static instance.
-
Constructor Summary
Constructors Constructor Description HilbertSpatialSorter()
Constructor, useSTATIC
instead.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method 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 elki.math.spacefillingcurves.SpatialSorter
sort
-
-
-
-
Field Detail
-
STATIC
public static final HilbertSpatialSorter STATIC
Static instance.
-
-
Constructor Detail
-
HilbertSpatialSorter
public HilbertSpatialSorter()
Constructor, useSTATIC
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 interfaceSpatialSorter
- Parameters:
objs
- the spatial objects to be sortedstart
- First index to sort (e.g., 0)end
- End of range (e.g.,site()
)minmax
- Array with dim pairs of (min, max) of value rangesdims
- Dimensions to sort by, for indexing vectors andminmax
.
-
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 coordinatesbitsperdim
- 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 coordinatesbitsperdim
- 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 coordinatesbitsperdim
- 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 coordinatesbitsperdim
- 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 coordinatesiter
- 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 coordinatesiter
- 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 coordinatesiter
- 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 coordinatesiter
- Bit position (from highest position)- Returns:
- One bit per dimension
-
-