HilbertCurveMap Class Reference

This class implements the mapping of a Hilbert curve in the \(d\)-dimensional unit hypercube \([0,1)^d\). More...

Public Member Functions
	HilbertCurveMap (int d, int m)
	Constructs a HilbertCurveMap object that will use the first \(m\) bits of each of the first d coordinates to sort the points. More...
	HilbertCurveMap (int d)
	This constructor is similar to HilbertCurveMap(int,int), but the parameter \(m = \lfloor63/d\rfloor\). More...
int	dimension ()
	Returns the dimension of the unit hypercube.
int	getM ()
	Returns the number of bits \(m\) that is used to divide the axis of each coordinate.
void	indexToCoordinates (long r, int[] a)
	Takes as input the Hilbert index \(r\) of a subcube and returns in a[] its integer coordinates. More...
long	coordinatesToIndex (int a[])
	Takes as input in a[] the integer coordinates of a subcube and returns the corresponding Hilbert index \(r\).
void	pointToCoordinates (double[] p, int[] a)
	Takes in p[] a point with real-valued coordinates and places in a[] the integer coordinates of the corresponding subcube. More...

Package Functions
void	initTables ()

Package Attributes
int	dimension
int	m
int	maxnbits
int	maxlength
int []	p_to_s
int []	s_to_p
int []	p_to_J
int []	bit
int []	parity
int [][]	circshift
int [][]	bitof

Detailed Description

This class implements the mapping of a Hilbert curve in the \(d\)-dimensional unit hypercube \([0,1)^d\).

This mapping can be used for sorting algorithms.

This map (conceptually) divides the unit hypercube \([0,1)^d\) in \(2^{dm}\) subcubes of equal sizes, by dividing each axis in \(2^m\) equal parts, and uses the first \(m\) bits of each of the \(d\) coordinates to place each point in one of the subcubes. It then enumerates the subcubes in the same order as a Hilbert curve in \([0,1)^d\) would visit them, and orders the points accordingly. Each cube has an (integer) Hilbert index \(r\) from 0 to \(2^{dm}-1\) and the cubes (and points) are ordered according to this index. Two points that fall in the same subcube can be placed in an unspecified (arbitrary) order.

For the implementation of sorts based on the Hilbert curve (or Hilbert index), we identify and sort the subcubes by their Hilbert index, but it is also convenient to identify them (alternatively) with \(m\)-bit integer coordinates: The subcube with coordinates \((i_1,…,i_d)\) is defined as \(\prod_{j=0}^{d-1} [i_j 2^{-m},  (i_j+1) 2^{-m})\). Note that each interval is open on the right. That is, if we multiply the coordinates of a point in the subcube by \(2^m\) and truncate them to integers, we obtain the integer coordinates of the subcube. For example, if \(d=2\) and \(m=4\), we have \(2^8 = 256\) subcubes, whose integer coordinates go from 0 to 15, and the point \((0.1, 0.51)\) belongs to the subcube with integer coordinates \((1, 8)\).

For given \(d\) and \(m\), this class offers methods to compute the integer coordinates of the corresponding subcube from the real-valued coordinates of a point in \([0,1)^d\), as well as the Hilbert index of a subcube from its integer coordinates, and vice versa. The code that computes the latter correspondences is taken (with slight adaptations) from the hilbert.c program of Spencer W. Thomas, University of Michigan, 1991.

Constructor & Destructor Documentation

HilbertCurveMap() [1/2]

HilbertCurveMap	(	int	d,
		int	m
	)

Constructs a HilbertCurveMap object that will use the first \(m\) bits of each of the first d coordinates to sort the points.

In this implementation, one must have \(md \le63\).

Parameters

d	maximum dimension
m	number of bits used for each coordinate

HilbertCurveMap() [2/2]

HilbertCurveMap

(

int

d

)

This constructor is similar to HilbertCurveMap(int,int), but the parameter \(m = \lfloor63/d\rfloor\).

In this implementation, one must have \(md \le63\).

Parameters

d	maximum dimension

Member Function Documentation

indexToCoordinates()

void indexToCoordinates	(	long	r,
		int []	a
	)

Takes as input the Hilbert index \(r\) of a subcube and returns in a[] its integer coordinates.

WARNING: This method currently works only for \(m \le9\). It is not used for the sort.

pointToCoordinates()

void pointToCoordinates	(	double []	p,
		int []	a
	)

Takes in p[] a point with real-valued coordinates and places in a[] the integer coordinates of the corresponding subcube.

The two arrays are assumed to have length \(d\).

---

The documentation for this class was generated from the following file:

• HilbertCurveMap.java