Class to compute a global index given a coordinate, based on the Hilbert Spacefilling Curve. More...

#include <Hilbert.hpp>

Public Member Functions
	Hilbert (const math::BoundingBox &bounding_box, Uint levels)

boost::uint64_t	operator() (const RealVector &point)
	Compute the hilbert code for a given point, checks for dimension. More...

boost::uint64_t	operator() (const RealVector &point, Real &relative_tolerance)

boost::uint64_t	operator() (const RealVector1 &point)
	Compute the hilbert code for a given point in 1D. More...

boost::uint64_t	operator() (const RealVector1 &point, Real &relative_tolerance)

boost::uint64_t	operator() (const RealVector2 &point)
	Compute the hilbert code for a given point in 2D. More...

boost::uint64_t	operator() (const RealVector2 &point, Real &relative_tolerance)

boost::uint64_t	operator() (const RealVector3 &point)
	Compute the hilbert code for a given point in 3D. More...

boost::uint64_t	operator() (const RealVector3 &point, Real &relative_tolerance)

boost::uint64_t	max_key () const

Private Types
enum	VertexLabel { A =0, B =1, C =2, D =3, E =4, F =5, G =6, H =7 }
	Vertex label type (8 vertices in 3D) More...

Private Member Functions
void	recursive_algorithm_1d (const Real &p)
	Recursive 1D algorithm. More...

void	recursive_algorithm_2d (const RealVector2 &p)
	Recursive 2D algorithm. More...

void	recursive_algorithm_3d (const RealVector3 &p)
	Recursive 3D algorithm. More...

Private Attributes
Uint	m_max_level
	maximum recursion level of the Hilbert space filling curve More...

boost::uint64_t	m_nb_keys
	maximum number of unique codes, computed by max_level More...

const math::BoundingBox &	m_bounding_box
	Bounding box, defining the space to be filled. More...

Uint	m_dim
	Dimension. More...

Uint	m_level
	Current recursion level. More...

boost::uint64_t	m_key
	Current key at recursion level. More...

Recursion allocation
Uint	m_quadrant
	Quadrant the coordinate lies in. (2D) More...

Uint	m_octant
	Octant the coordinate lies in. (3D) More...

Real	m_distance
	Distance between coordinate and a vertex. More...

Real	m_min_distance
	Minimum distance between coordinate and a vertex. More...

Uint	m_idx
	index More...

std::vector< Real >	m_box1
	box at recursion level. (1D) More...

std::vector< RealVector2, Eigen::aligned_allocator< RealVector2 > >	m_box2
	box at recursion level. (2D) More...

std::vector< RealVector2, Eigen::aligned_allocator< RealVector2 > >	m_tmp_box2
	temporary box at recursion level. (2D) More...

std::vector< RealVector3, Eigen::aligned_allocator< RealVector3 > >	m_box3
	box at recursion level. (2D) More...

std::vector< RealVector3, Eigen::aligned_allocator< RealVector3 > >	m_tmp_box3
	temporary box at recursion level. (3D) More...

Detailed Description

Class to compute a global index given a coordinate, based on the Hilbert Spacefilling Curve.

This algorithm is based on:

John J. Bartholdi and Paul Goldsman "Vertex-Labeling Algorithms for the Hilbert Spacefilling Curve"
It is adapted to return contiguous numbers of the boost::uint64_t type, instead of a Real [0,1]

Given a bounding box and number of hilbert levels, the bounding box can be divided in 2^(dim*levels) equally spaced cells. A given coordinate falling inside one of these cells, is assigned the 1-dimensional Hilbert-index of this cell. To make sure that 1 coordinate corresponds to only 1 Hilbert index, the number of levels have to be increased. In 1D, the levels cannot be higher than 32, if you want the indices to fit in "unsigned int" type of 32bit. In 2D, the levels cannot be higher than 15, if you want the indices to fit in "unsigned int" type of 32bit. In 3D, the levels cannot be higher than 10, if you want the indices to fit in "unsigned int" type of 32bit.

No attempt is made to provide the most efficient algorithm. There exist other open-source libraries with more efficient algorithms, such as libhilbert, but its GPL license is not compatible with the LGPL license.

Author: Willem Deconinck

Definition at line 43 of file Hilbert.hpp.

Member Enumeration Documentation

enum VertexLabel

private

Vertex label type (8 vertices in 3D)

Enumerator
A
B
C
D
E
F
G
H

Definition at line 99 of file Hilbert.hpp.

Constructor & Destructor Documentation

Hilbert	(	const math::BoundingBox &	bounding_box,
		Uint	levels
	)

Constructor Initializes the hilbert space filling curve with a given "space" and "levels"

Definition at line 23 of file Hilbert.cpp.

Member Function Documentation

boost::uint64_t max_key ( ) const

Return the maximum hilbert code possible with the initialized levels

Care has to be taken that this number is not larger than the precision of the type storing the hilbert codes.

Definition at line 141 of file Hilbert.cpp.

boost::uint64_t operator() ( const RealVector & point )

Compute the hilbert code for a given point, checks for dimension.

Definition at line 46 of file Hilbert.cpp.

boost::uint64_t operator()	(	const RealVector &	point,
		Real &	relative_tolerance
	)

Compute the hilbert code for a given point, checks for dimension

Parameters

[out] relative_tolerance cell-size of smallest level divided by bounding-box size

Definition at line 60 of file Hilbert.cpp.

boost::uint64_t operator() ( const RealVector1 & point )

Compute the hilbert code for a given point in 1D.

Definition at line 74 of file Hilbert.cpp.

boost::uint64_t operator()	(	const RealVector1 &	point,
		Real &	relative_tolerance
	)

Compute the hilbert code for a given point in 1D

Parameters

[out] relative_tolerance cell-size of smallest level divided by bounding-box size

Definition at line 85 of file Hilbert.cpp.

boost::uint64_t operator() ( const RealVector2 & point )

Compute the hilbert code for a given point in 2D.

Definition at line 93 of file Hilbert.cpp.

boost::uint64_t operator()	(	const RealVector2 &	point,
		Real &	relative_tolerance
	)

Compute the hilbert code for a given point in 2D

Parameters

[out] relative_tolerance cell-size of smallest level divided by bounding-box size

Definition at line 110 of file Hilbert.cpp.

boost::uint64_t operator() ( const RealVector3 & point )

Compute the hilbert code for a given point in 3D.

Definition at line 117 of file Hilbert.cpp.

boost::uint64_t operator()	(	const RealVector3 &	point,
		Real &	relative_tolerance
	)

Compute the hilbert code for a given point in 3D

Parameters

[out] relative_tolerance cell-size of smallest level divided by bounding-box size

Definition at line 134 of file Hilbert.cpp.

void recursive_algorithm_1d ( const Real & p )

private

Recursive 1D algorithm.

Definition at line 143 of file Hilbert.cpp.

void recursive_algorithm_2d ( const RealVector2 & p )

private

Recursive 2D algorithm.

Definition at line 173 of file Hilbert.cpp.

void recursive_algorithm_3d ( const RealVector3 & p )

private

Recursive 3D algorithm.

Definition at line 224 of file Hilbert.cpp.

Member Data Documentation

const math::BoundingBox& m_bounding_box

private

Bounding box, defining the space to be filled.

Definition at line 108 of file Hilbert.hpp.

std::vector<Real> m_box1

private

box at recursion level. (1D)

Definition at line 138 of file Hilbert.hpp.

std::vector<RealVector2,Eigen::aligned_allocator<RealVector2> > m_box2

private

box at recursion level. (2D)

Definition at line 141 of file Hilbert.hpp.

std::vector<RealVector3,Eigen::aligned_allocator<RealVector3> > m_box3

private

box at recursion level. (2D)

Definition at line 147 of file Hilbert.hpp.

Uint m_dim

private

Dimension.

Definition at line 111 of file Hilbert.hpp.

Real m_distance

private

Distance between coordinate and a vertex.

Definition at line 129 of file Hilbert.hpp.

Uint m_idx

private

index

Definition at line 135 of file Hilbert.hpp.

boost::uint64_t m_key

private

Current key at recursion level.

Definition at line 117 of file Hilbert.hpp.

Uint m_level

private

Current recursion level.

Definition at line 114 of file Hilbert.hpp.

Uint m_max_level

private

maximum recursion level of the Hilbert space filling curve

Definition at line 102 of file Hilbert.hpp.

Real m_min_distance

private

Minimum distance between coordinate and a vertex.

Definition at line 132 of file Hilbert.hpp.

boost::uint64_t m_nb_keys

private

maximum number of unique codes, computed by max_level

Definition at line 105 of file Hilbert.hpp.

Uint m_octant

private

Octant the coordinate lies in. (3D)

Definition at line 126 of file Hilbert.hpp.

Uint m_quadrant

private

Quadrant the coordinate lies in. (2D)

Definition at line 123 of file Hilbert.hpp.

std::vector<RealVector2,Eigen::aligned_allocator<RealVector2> > m_tmp_box2

private

temporary box at recursion level. (2D)

Definition at line 144 of file Hilbert.hpp.

std::vector<RealVector3,Eigen::aligned_allocator<RealVector3> > m_tmp_box3

private

temporary box at recursion level. (3D)

Definition at line 150 of file Hilbert.hpp.

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

cf3/math/Hilbert.hpp
cf3/math/Hilbert.cpp

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation