GeomHash

The template defines a geometric hash table class. The class is declared using a key type with which the data type instances are inserted and accessed. The geometric hash table may be instantiated using any dimension and grid-size.

Quick Index

AUTHORS

CHANGES LOG

GOALS

USAGE

Class Summary

class GeomHash :
, DataT, BucketT>

{

public:
explicit	GeomHash(const unsigned short d , const float cs );
explicit	GeomHash(const unsigned short d, const vector< float>& cs);
	~GeomHash() ;
	GeomHash(const GeomHash< KeyT,DataT,BucketT>&);
void	insert(const KeyT& key, const DataT& data);
void	query(const KeyT& key, const float radius, Result& result) const;
void	query(const KeyT& key, const float radius, const NormType ballType, Result& result) const;
void	query(const KeyT& key, const vector< float>& radii, Result& result) const;
void	query(const KeyT& key, Result& result) const;
void	query(Result& result, bool includeEmpty ) const;
BucketsPointerList *	getBuckets(bool includeEmpty ) const;
const Bucket*	bucket(const KeyT& key) const;
void	erase();
void	setInsertSpeed(const float speed);
unsigned short	dimension() const;
float	resolution(unsigned short axis ) const;
float	insertSpeed() const;
protected:

}; // GeomHash

Back to the top of GeomHash

AUTHORS

Meir Fuchs (meirfux@math.tau.ac.il). Zipi Fligelman (zipo@math.tau.ac.il).

Back to the top of GeomHash

CHANGES LOG

27/02/02 - Dina Duhovny & Oranit Shem-Tov: - GeomHashParams - We refer to the dimension attribute as the dimension of the overall geometric hash. Previously, this attribute was reffered to as the index of the last axis (i.e. dimension-1). Axis explanation by an example: Assume a 2D geometric hash. It's axes are numbered as 0 (the x-axis) & 1 (the y-axis). - Defining cube size for each axis. Previously, there was only one value for all the axis. It is usefull for storing data and a key, composed of several components, each one of them has a different scale. For example, a 4D key, composed of a 3D coordinates and a type. - Defining query ranges - for querying, within a different radius for each axis.
8/8/99 - Ram Nathaniel:
Add bucket iteration - method vector *getBuckets() const;
7/11/99 - Zipi Fligelman Changed the method by Ram and added parameter at the whole table query In the full table query there is a flag that by default is set to false, that means you collect only non empty buckets. But when it is set to true non-empty buckets are also collected. The same is true for the method getBuckets. That returns a vector of const Bucket * with all the buckets The empty backets are returned only if the flag is set to true.
15/5/03 - M. Shatsky Copy constructor is added

Back to the top of GeomHash

GOALS

GeomHash defines a high performance geometric hash table with an intuitive interface. The class can be defined for any key type that supports the [] operator for any data type. The hash table can be instantiated using any dimension and any cube or grid size. It is possible to specify different cube size for each axis. The query function also may be called with a set of radii, one for each axis. User may also decide how the data elements are collected in each bucket by determining the container used in each bucket.

GeomHash actually is a wrap for the HashLink class which does most of the work of hash table traversal, insertion and querying. The user need not know anything about HashLink to use the hash table.

Geometric hash table results are returned using an STL-like container class called HashResult. This class and its accompanying iterator class HashIterator are used to collect hash table query results and to iterate through the result elements.

Back to the top of GeomHash

USAGE

Instantiation and declaration are done using a key type and a data type. The key type must support the [] operator. For example an array of floats or a Vector3 for 3 dimensional hash tables. User may also choose to determine the bucket type. By default the bucket type is a vector. The user may decide on other STL containers or write one of his own. The bucket type must support the push_back, begin, end, size methods and the iterator and const_iterator typedefs.

Instantiation may include a grid size and a dimension. Here is an example using Vector3's as the keys, integers as the data stored in the hash table, 3 is the dimension and 1.3 is the cube size of the grid.

    GeomHash<Vector3, int> gHash(3, 1.3);

Members may be inserted using the insert command. The insert command recieves a key and a data element to be inserted into the proper bucket in the hash table.

    gHash.insert(Vector3(1.2, 2.3, 3.4), -1);

When querying a geometric hash table one searches for data that was inserted into the hash table using keys that were close to the query key. A radius may be given to the query defining how far the neighboring points should be. The query returns all points within that distance but will return other points that lie in neighboring grid cubes. If you wish to extract points that are within a given euclidean radius you'll have to sift through the query results.

Before running a query one must declare a HashResult container in which the results will be collected. The container is sent with the query request and results are found in the container after the query is done.

An example of querying the hash table with a key and sifting through the data to find the data's that are within a euclidean radius of the key is given. The example assumes 10000 points are given inside a Vector3 array called points and a query point is given in Vector3 q.

  float radius=1.0;
  GeomHash<Vector3, int> gHash(3, 2*radius);  // grid cube size is 2*radius
  for (int i=0; i<10000; i++)   // insert 10000 points
    gHash.insert(points[i], i);
  
  Vector3 q(1,1,1);
  HashResult<int> result;
  gHash.query(q, radius, result);  // radius = half of cube size.
  
  // traverse list STL iterator style.
  HashResult<int>::iterator it;
  for (it = result.begin(); it != result.end(); it++)
    if (q | points[*it]) <= radius
      cout << *it << " : " << points[*it] << '\n';

In case of more complex key, the user can specify the cube size of every axis. For example, in case of transformation: each transformation can be represented as 3 rotation parameters and 3 translation parameters. The rotation parameters are values between -PI and PI, while the translational parameters are not limited. The user may want smaller bin size for rotation then for translation.

  vector<float> radii(6);
  radii[0]=radii[1]=radii[2]=0.1;
  radii[3]=radii[4]=radii[5]=2.0;
  GeomHash<Transformation,int> gHash(6, radii);

  The same idea works in query:
  HashResult<int> result;
  gHash.query(t, radii, result);

Back to the top of GeomHash

explicit GeomHash(const unsigned short d , const float cs );

The hash-table is instantiated by a given dimension (defualt 1) and a given cube-size (default 1.0).

  explicit GeomHash(const unsigned short d=1, const float cs=1.0);

Back to the top of GeomHash

explicit GeomHash(const unsigned short d, const vector< float>& cs);

The hash-table is instantiated by a given dimension and // a given cube size for each dimension.

  explicit GeomHash(const unsigned short d, const vector< float>& cs);

Back to the top of GeomHash

~GeomHash() ;

Destructor. Frees all hash table memory.

  ~GeomHash()                          
;

Function is currently defined inline.

Back to the top of GeomHash

GeomHash(const GeomHash< KeyT,DataT,BucketT>&);

Copy constructor

  GeomHash(const GeomHash< KeyT,DataT,BucketT>&);

Back to the top of GeomHash

void insert(const KeyT& key, const DataT& data);

Data elements can be inserted according to keys using the insert method. The key determines in which d-dimensional cube the data is inserted.

  void insert(const KeyT& key, const DataT& data);

Back to the top of GeomHash

void query(const KeyT& key, const float radius, Result& result) const;

Searches for all data elements lying in radius neighborhood to key. Note that query will return all points lying within a given radius but may also return extra points that were not inserted with keys that are within a radius to the query key. Moreover, the default norm is the infinite norm All results are collected using a results container of type HashResult.

  void query(const KeyT& key, const float radius, Result& result) const;

Back to the top of GeomHash

void query(const KeyT& key, const float radius, const NormType ballType, Result& result) const;

Searches for all data elements according to a given key. The user may specify the type of the norm: Euclidean, Manhattan or Infinite. Note that query will return all points lying within a given radius but may also return extra points that were not inserted with keys that are within a radius to the query key. All results are collected using a results container of type HashResult.

  void query(const KeyT& key, const float radius, const NormType ballType, 
             Result& result) const;

Back to the top of GeomHash

void query(const KeyT& key, const vector< float>& radii, Result& result) const;

Searches for all data elements according to a given key and a set of radii. the size of the radii vector must be equal to dimension. Each axis is searches with a radius specified for it. This query may return extra points as well.

  void query(const KeyT& key, const vector< float>& radii, Result& result) const;

Back to the top of GeomHash

void query(const KeyT& key, Result& result) const;

Searches for all data elements lying in radius=cube size neighborhood to key. The query will return all data's that were inserted with keys whose distance to the query key is less then radius. More data elements may be returned due to the grid structure of the hash table. All results are collected using a results container of type HashResult.

  void query(const KeyT& key, Result& result) const;

Back to the top of GeomHash

void query(Result& result, bool includeEmpty ) const;

Query the hash table with an infinite radius. Calling this method results in a hash table results container which points to all hash table elements. There is a choice whether to collect only non empty buckets (ehich is also the default), but if one wished to check for sparsity of the table you can set the includeEmpty to true and receive all the empty buckets. Notice that travesing the result must be done with caution mind the NULLs ....

  void query(Result& result, bool includeEmpty=false) const;

Back to the top of GeomHash

BucketsPointerList *getBuckets(bool includeEmpty ) const;

Return a vector of all the buckets currently used in the Hash. This is usefull for traversing the hash one bucket at a time, and also usefull for creating a set of all the buckets now in use for follow up checks. There is a flag that can be set if you want to add all the empty buckets in the last dimesion and thus check the change in the sparsity of the table.(The Hash class never changes the buckets but only copy a constant version of the pointers so that even after insertions and deletions in the Hash the vector will indicate the same set of buckets).

  BucketsPointerList *getBuckets(bool includeEmpty=false) const;

Back to the top of GeomHash

const Bucket* bucket(const KeyT& key) const;

Returns a pointer to a bucket at the location given by key. If no such bucket exists a NULL pointer is returned.

  const Bucket* bucket(const KeyT& key) const;

Back to the top of GeomHash

void erase();

frees all memory used by hash table elements.

  void erase();

Back to the top of GeomHash

void setInsertSpeed(const float speed);

Sets the hash table insertion speed. This parameter determines how large the hash table arrays are made when an array resize is forced. When this parameter is set to 0, arrays will be resized to be slightly larger then what is currently needed by the hash table. If the parameter is set to > 0, resizes will be more generous. Array sizes will grow causing a decrease in the number of resize operations and hence an increase in insertion speed.

This feature should be useful for large but sparsely populated hash tables In densely populated hash tables, a gain in speed should be noticed only with the first insertions. Once the table is populated resize operations are rare and hence the speed gain is limited.

Note that raising the parameter too high could actually cause the insertion operations to slow down because of the overhead of managing a large hash table. This parameter should probably not exceed 4.0.

  void setInsertSpeed(const float speed);

Back to the top of GeomHash

unsigned short dimension() const;

returns hash table dimension

  unsigned short dimension() const;

Back to the top of GeomHash

float resolution(unsigned short axis ) const;

returns hash table resolution or cube size.

  float resolution(unsigned short axis=0) const;

Back to the top of GeomHash

float insertSpeed() const;

Returns hash table insertion speed. See setInsertSpeed.

  float insertSpeed() const;

Back to the top of GeomHash

All Members

public:
explicit	GeomHash(const unsigned short d , const float cs );
explicit	GeomHash(const unsigned short d, const vector< float>& cs);
void	insert(const KeyT& key, const DataT& data);
void	query(const KeyT& key, const float radius, Result& result) const;
void	query(const KeyT& key, const float radius, const NormType ballType, Result& result) const;
void	query(const KeyT& key, const vector< float>& radii, Result& result) const;
void	query(const KeyT& key, Result& result) const;
void	query(Result& result, bool includeEmpty ) const;
BucketsPointerList *	getBuckets(bool includeEmpty ) const;
const Bucket*	bucket(const KeyT& key) const;
void	erase();
void	setInsertSpeed(const float speed);
unsigned short	dimension() const;
float	resolution(unsigned short axis ) const;
float	insertSpeed() const;
protected:

Back to the top of GeomHash

Ancestors

Class does not inherit from any other class.

Back to the top of GeomHash

Descendants

Class is not inherited by any others.

Back to the top of GeomHash

Generated from source by the Cocoon utilities on Sun Nov 15 13:35:25 2009 .

Report problems to jkotula@unimax.com