DGtal::Morton< THashKey, TPoint > Class Template Reference

#include <Morton.h>

Inheritance diagram for DGtal::Morton< THashKey, TPoint >:

Public Types
typedef THashKey	HashKey
typedef TPoint	Point
typedef Point::Coordinate	Coordinate

Public Member Functions
	BOOST_CONCEPT_ASSERT ((CUnsignedInteger< THashKey >))
	BOOST_CONCEPT_ASSERT ((CInteger< Coordinate >))
	Morton ()
void	interleaveBits (const Point &aPoint, HashKey &output) const
HashKey	keyFromCoordinates (const std::size_t treeDepth, const Point &coordinates) const
void	coordinatesFromKey (const HashKey key, Point &coordinates) const
HashKey	parentKey (const HashKey key) const
void	brotherKeys (const HashKey key, HashKey *result) const
void	childrenKeys (const HashKey key, HashKey *result) const

Static Public Attributes
static const Dimension	dimension = Point::dimension

---

Detailed Description

template<typename THashKey, typename TPoint>
class DGtal::Morton< THashKey, TPoint >

Aim: Implements the binary Morton code construction in nD.

Description of template class 'Morton'

Given a point in nD \((x_1,\ldots, x_n)\), a Morton code consists in interleaving bits of \(x_i\) coordinate values (plus a prefix for the HashTree construction.

Main methods in this class are keyFromCoordinates to generate a key and CoordinatesFromKey to generate a point from a code.

Template Parameters:

THashKey	type to store the morton code (should have enough capacity to store the interleaved binary word).
TPoint	type of points.

See also:

testImageContainerByHashTree.cpp

Definition at line 76 of file Morton.h.

---

Member Typedef Documentation

template<typename THashKey, typename TPoint>

typedef Point::Coordinate DGtal::Morton< THashKey, TPoint >::Coordinate

Definition at line 81 of file Morton.h.

template<typename THashKey, typename TPoint>

typedef THashKey DGtal::Morton< THashKey, TPoint >::HashKey

Definition at line 79 of file Morton.h.

template<typename THashKey, typename TPoint>

typedef TPoint DGtal::Morton< THashKey, TPoint >::Point

Definition at line 80 of file Morton.h.

---

Constructor & Destructor Documentation

template<typename HashKey , typename Point >

DGtal::Morton< HashKey, Point >::Morton

(

)

Constructor

Definition at line 40 of file Morton.ih.

  {
    // @todo precomputation of the dilate masks
    //myDilateMasks[0] = 25;
  }

---

Member Function Documentation

template<typename THashKey, typename TPoint>

DGtal::Morton< THashKey, TPoint >::BOOST_CONCEPT_ASSERT

(

(CUnsignedInteger< THashKey >)

)

template<typename THashKey, typename TPoint>

DGtal::Morton< THashKey, TPoint >::BOOST_CONCEPT_ASSERT

(

(CInteger< Coordinate >)

)

template<typename HashKey , typename Point >

void DGtal::Morton< HashKey, Point >::brotherKeys	(	const HashKey	key,
		HashKey *	result
	)		const

Computes the brother keys (ie the keys having the same parent) of the key passed in parameter.

Parameters:

key	The key.
result	Will contain the resulting brother keys.

Definition at line 98 of file Morton.ih.

    {
      //generate a mask of the form 1..111000 with dimension "0"
      HashKey mask  = ( static_cast<HashKey> ( ~0 ) << dimension );
      std::size_t j = 0;
      for ( std::size_t i = 0; i < POW<2,dimension>::VALUE; ++i )
        {
          HashKey key2 = ( key & mask ) |i;
          if ( key2 != key )
            {
              result[j] = key2;
              ++j;
            }
        }
    }

template<typename HashKey , typename Point >

void DGtal::Morton< HashKey, Point >::childrenKeys	(	const HashKey	key,
		HashKey *	result
	)		const

Computes the children keys of the key passed in parameter.

Parameters:

key	The key.
result	Will contain the resulting children keys.

Definition at line 82 of file Morton.ih.

Referenced by DGtal::ImageContainerByHashTree< TDomain, TValue, THashKey >::blendChildren(), DGtal::ImageContainerByHashTree< TDomain, TValue, THashKey >::checkIntegrity(), DGtal::Display2DFactory::drawImageRecursive(), DGtal::ImageContainerByHashTree< TDomain, TValue, THashKey >::printTree(), and DGtal::ImageContainerByHashTree< TDomain, TValue, THashKey >::recursiveRemoveNode().

    {
      HashKey keycopy = key;

      keycopy <<= dimension;
      //generate a mask of the form 1..111000 with dimension "0"
      HashKey mask  = ( static_cast<HashKey> ( ~0 ) << dimension );
      for ( std::size_t i = 0;
            i < POW<2,dimension>::VALUE;
            ++i )
        {
          result[i] = ( keycopy & mask ) |i;
        }
    }

template<typename HashKey , typename Point >

void DGtal::Morton< HashKey, Point >::coordinatesFromKey	(	const HashKey	key,
		Point &	coordinates
	)		const

Computes the coordinates correspponding to a key.

Parameters:

key	The key.
coordinates	Will contain the resulting coordinates.

Definition at line 115 of file Morton.ih.

    {
      HashKey akey = key;
      //remove the first bit equal 1
      for ( int i = ( sizeof ( HashKey ) <<3 )-1; i >= 0; --i )
        if ( akey & Bits::mask<HashKey> ( i ) )
          {
            akey &= ~Bits::mask<HashKey> ( i );
            break;
          }

      //deinterleave the bits
      for ( std::size_t i = 0; i < dimension; ++i )
                {
                        coordinates[(Dimension)i] = 0;

                        for ( std::size_t bitPos = 0; bitPos < ( sizeof ( HashKey ) <<3 ) / dimension; ++bitPos )
                        {
                                if ( akey & Bits::mask<HashKey> ( (unsigned int)(bitPos*dimension+i) ) )
                                {
                                        coordinates[(Dimension)i] |= Bits::mask<HashKey> ( (unsigned int)bitPos );
                                }
                        }
                }
    }

template<typename HashKey , typename Point >

void DGtal::Morton< HashKey, Point >::interleaveBits	(	const Point &	aPoint,
		HashKey &	output
	)		const

Interleave the bits of the nbIn inputs.

Parameters:

input	an array of the nbIn values to mix in.
output	The result

Definition at line 48 of file Morton.ih.

    {
      //number of bits of the input integers (casted according to the hashkeysize)
      // max of this with sizeof(Coordinate)*8
      unsigned  int coordSize = ( sizeof ( HashKey ) <<3 ) / dimension;

      output = 0;
      for ( unsigned int i = 0; i < coordSize; ++i )
        for ( unsigned int n = 0; n < dimension; ++n )
          {
            if ( ( aPoint[n] ) & ( static_cast<Coordinate> ( 1 ) << i ) )
              output |= static_cast<Coordinate> ( 1 ) << (( i*dimension ) +n);
          }
    }

template<typename HashKey , typename Point >

HashKey DGtal::Morton< HashKey, Point >::keyFromCoordinates	(	const std::size_t	treeDepth,
		const Point &	coordinates
	)		const

Returns the key corresponding to the coordinates passed in the parameters.

Parameters:

treeDepth	The depth at which the coordinates are to be read (usualy corresponds to the deepest leave).
coordinates	An array containing the coordinates to convert into a key.

Definition at line 65 of file Morton.ih.

    {
      HashKey result = 0;

      interleaveBits ( coordinates, result );
      // by convention, the root node has the key 0..01
      // it makes it easy to determine the depth of a node by it's key (looking
      // at the position of the most significant bit that is equal to 1)
      result |= ( static_cast<HashKey> ( 1 ) << dimension*treeDepth );

      return result;
    }

template<typename THashKey, typename TPoint>

HashKey DGtal::Morton< THashKey, TPoint >::parentKey ( const HashKey  key ) const

inline

Returns the parent key of a key passed in parameter.

Parameters:

key

The key.

Definition at line 125 of file Morton.h.

    {
      return key >> dimension;
    }

---

Field Documentation

template<typename THashKey, typename TPoint>

const Dimension DGtal::Morton< THashKey, TPoint >::dimension = Point::dimension

static

Definition at line 82 of file Morton.h.

Referenced by DGtal::Morton< HashKey, Point >::parentKey().

---

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

• Morton.h
• Morton.ih