KNN_Grid< T > Class Template Reference

#include <KNN_Grid.h>

Inheritance diagram for KNN_Grid< T >:

Collaboration diagram for KNN_Grid< T >:

Classes
class	KNNnbr

Public Member Functions
	KNN_Grid (Point3D m, Point3D M, int long_dim)
	KNN_Grid (Point3D m, Point3D M, int x_dim, int y_dim, int z_dim)
int	insert (T &item, Point3D &p)
int	insertRange (T &item, Point3D &p, Point3D &q, Point3D &r)
void	clear ()
unsigned int	k_nearest (Point3D &p, int k, vector< T > &nbrs)
vector< T > *	get_cell_range (Point3D &p, Point3D &q)
vector< T > *	get_cell (Point3D &p)
vector< T > *	get_cell (UniformGrid::Index &p)
	KNN_Grid (Point3D m, Point3D M, int long_dim)
	KNN_Grid (Point3D m, Point3D M, int x_dim, int y_dim, int z_dim)
int	insert (T &item, Point3D &p)
int	insertRange (T &item, Point3D &p, Point3D &q, Point3D &r)
void	clear ()
unsigned int	k_nearest (Point3D &p, int k, vector< T > &nbrs)
vector< T > *	get_cell_range (Point3D &p, Point3D &q)
vector< T > *	get_cell (Point3D &p)
vector< T > *	get_cell (UniformGrid::Index &p)

Private Types
typedef vector< T >	SpaceCell
typedef unsigned int	index_t
typedef NVec< 3, index_t >	Index
typedef vector< T >	SpaceCell
typedef unsigned int	index_t
typedef NVec< 3, index_t >	Index

Private Attributes
Point3D	bbmin
Point3D	bbmax
int	cell_dim [3]
float	cellsz [3]
SparseGrid< SpaceCell > *	grid

Detailed Description

template<typename T>
class KNN_Grid< T >

Definition at line 164 of file Rocon/include/KNN_Grid.h.

Member Typedef Documentation

typedef NVec<3,index_t> Index

private

Definition at line 190 of file Rocon/include/KNN_Grid.h.

typedef NVec<3,index_t> Index

private

Definition at line 190 of file Rocprop/include/KNN_Grid.h.

typedef unsigned int index_t

private

Definition at line 189 of file Rocprop/include/KNN_Grid.h.

typedef unsigned int index_t

private

Definition at line 189 of file Rocon/include/KNN_Grid.h.

typedef vector< T > SpaceCell

private

Definition at line 188 of file Rocprop/include/KNN_Grid.h.

typedef vector< T > SpaceCell

private

Definition at line 188 of file Rocon/include/KNN_Grid.h.

Constructor & Destructor Documentation

KNN_Grid ( Point3D  m, Point3D  M, int  long_dim  )

inline

Definition at line 203 of file Rocon/include/KNN_Grid.h.

    :bbmin(m),bbmax(M)
  {
    //Construct a grid with square elements
    Point3D box_len = bbmax-bbmin;
    int max_dim;
    // Find max length dimension of the grid
    if ( box_len[0] > box_len[1])
      max_dim = 0;
    else
      max_dim = 1;
    if (box_len[2]>box_len[max_dim])
      max_dim = 2;
    
    cellsz[max_dim] = box_len[max_dim]/((float) long_dim);
    for(int i=0; i<3;i++){
      cellsz[i] = cellsz[max_dim];
      cell_dim[i] = (int)ceil(box_len[0]/cellsz[max_dim]); // ** maybe box_len[i] **
      bbmax[i] = bbmin[i] + ((float) cell_dim[i]) * cellsz[i];  
    }
    grid = new SparseGrid< SpaceCell >(cell_dim[0],cell_dim[1],cell_dim[2]);
    grid->set_extent(bbmin,bbmax);      
        //cout << "Grid Extent \n";     
        
  }

KNN_Grid ( Point3D  m, Point3D  M, int  x_dim, int  y_dim, int  z_dim  )

inline

Definition at line 229 of file Rocon/include/KNN_Grid.h.

    :bbmin(m),bbmax(M)
  {
    cell_dim[0]=x_dim;cell_dim[1]=y_dim;cell_dim[2]=z_dim;
    grid = new SparseGrid< SpaceCell >(cell_dim[0],cell_dim[1],cell_dim[2]);
    grid->set_extent(bbmin,bbmax); 
  }

KNN_Grid ( Point3D  m, Point3D  M, int  long_dim  )

inline

Definition at line 203 of file Rocprop/include/KNN_Grid.h.

    :bbmin(m),bbmax(M)
  {
    //Construct a grid with square elements
    Point3D box_len = bbmax-bbmin;
    int max_dim;
    // Find max length dimension of the grid
    if ( box_len[0] > box_len[1])
      max_dim = 0;
    else
      max_dim = 1;
    if (box_len[2]>box_len[max_dim])
      max_dim = 2;
    
    cellsz[max_dim] = box_len[max_dim]/((float) long_dim);
    for(int i=0; i<3;i++){
      cellsz[i] = cellsz[max_dim];
      cell_dim[i] = (int)ceil(box_len[0]/cellsz[max_dim]); // ** maybe box_len[i] **
      bbmax[i] = bbmin[i] + ((float) cell_dim[i]) * cellsz[i];  
    }
    grid = new SparseGrid< SpaceCell >(cell_dim[0],cell_dim[1],cell_dim[2]);
    grid->set_extent(bbmin,bbmax);      
        //cout << "Grid Extent \n";     
        
  }

KNN_Grid ( Point3D  m, Point3D  M, int  x_dim, int  y_dim, int  z_dim  )

inline

Definition at line 229 of file Rocprop/include/KNN_Grid.h.

    :bbmin(m),bbmax(M)
  {
    cell_dim[0]=x_dim;cell_dim[1]=y_dim;cell_dim[2]=z_dim;
    grid = new SparseGrid< SpaceCell >(cell_dim[0],cell_dim[1],cell_dim[2]);
    grid->set_extent(bbmin,bbmax); 
  }

Member Function Documentation

void clear ( )

inline

Definition at line 288 of file Rocon/include/KNN_Grid.h.

              {
    delete grid;
    grid = new SparseGrid< SpaceCell >(cell_dim[0],cell_dim[1],cell_dim[2]);
    grid->set_extent(bbmin,bbmax);
  }

void clear ( )

inline

Definition at line 288 of file Rocprop/include/KNN_Grid.h.

              {
    delete grid;
    grid = new SparseGrid< SpaceCell >(cell_dim[0],cell_dim[1],cell_dim[2]);
    grid->set_extent(bbmin,bbmax);
  }

vector<T>* get_cell ( Point3D &  p )

inline

Definition at line 370 of file Rocon/include/KNN_Grid.h.

                                  {
    return grid->locate_only(p);
  }

vector<T>* get_cell ( Point3D &  p )

inline

Definition at line 370 of file Rocprop/include/KNN_Grid.h.

                                  {
    return grid->locate_only(p);
  }

vector<T>* get_cell ( UniformGrid::Index &  p )

inline

Definition at line 374 of file Rocprop/include/KNN_Grid.h.

                                           {
    for(int i=0;i<3;i++)
                if ((p[i] < 0) || (p[i] >= cell_dim[i]))
                        return NULL;
        //cerr << "i get in here\n";
    return grid->locate_index_only(p);
  }

vector<T>* get_cell ( UniformGrid::Index &  p )

inline

Definition at line 374 of file Rocon/include/KNN_Grid.h.

                                           {
    for(int i=0;i<3;i++)
      if ((p[i] < 0) || (p[i] >= static_cast<unsigned int>(cell_dim[i])))
                        return NULL;
        //cerr << "i get in here\n";
    return grid->locate_index_only(p);
  }

vector<T>* get_cell_range ( Point3D &  p, Point3D &  q  )

inline

Definition at line 335 of file Rocon/include/KNN_Grid.h.

                                                  {
        vector<T> * ret = new vector<T>;
        vector<T> * temp = NULL;
        
        Index a = grid->compute_index(p);
        Index b = grid->compute_index(q);
        // cout << "A: "<< a[0]<< ", "<< a[1]<< ", "<< a[2]<< "\n";
        // cout << "B: "<< b[0]<< ", "<< b[1]<< ", "<< b[2]<< "\n";
        Index min,max;
        
        for(int i=0;i<3;++i)
        {
                min[i] = (a[i]>b[i])?b[i]:a[i];
                max[i] = (a[i]>b[i])?a[i]:b[i];
        }

        for(unsigned int i=min[0]; i<=max[0];++i)
        {
                for(unsigned int j=min[1]; j<=max[1]; ++j)
                {
                        for(unsigned int k=min[2]; k<=max[2]; ++k)
                        {
                                Index p(i,j,k);
                                //cout<<"Index x: "<< i <<" y:"<< j <<" z:"<< k <<"\n";
                                temp = get_cell(p);
                                if(temp!=NULL){
                                        //cout<< "temp size: " << temp->size() <<"\n";
                                        ret->insert(ret->begin(), temp->begin(), temp->end());
                                }
                        }
                }
        }
        return ret;
  }

vector<T>* get_cell_range ( Point3D &  p, Point3D &  q  )

inline

Definition at line 335 of file Rocprop/include/KNN_Grid.h.

                                                  {
        vector<T> * ret = new vector<T>;
        vector<T> * temp = NULL;
        
        Index a = grid->compute_index(p);
        Index b = grid->compute_index(q);
        // cout << "A: "<< a[0]<< ", "<< a[1]<< ", "<< a[2]<< "\n";
        // cout << "B: "<< b[0]<< ", "<< b[1]<< ", "<< b[2]<< "\n";
        Index min,max;
        
        for(int i=0;i<3;++i)
        {
                min[i] = (a[i]>b[i])?b[i]:a[i];
                max[i] = (a[i]>b[i])?a[i]:b[i];
        }

        for(int i=min[0]; i<=max[0];++i)
        {
                for(int j=min[1]; j<=max[1]; ++j)
                {
                        for(int k=min[2]; k<=max[2]; ++k)
                        {
                                Index p(i,j,k);
                                //cout<<"Index x: "<< i <<" y:"<< j <<" z:"<< k <<"\n";
                                temp = get_cell(p);
                                if(temp!=NULL){
                                        //cout<< "temp size: " << temp->size() <<"\n";
                                        ret->insert(ret->begin(), temp->begin(), temp->end());
                                }
                        }
                }
        }
        return ret;
  }

int insert ( T &  item, Point3D &  p  )

inline

Definition at line 237 of file Rocprop/include/KNN_Grid.h.

  {
    SpaceCell * cell = grid->locate(p);
    cell->push_back(item);
        //cout << "Size: "<< cell->size() << "\n" ;
    return cell->size();
  }

int insert ( T &  item, Point3D &  p  )

inline

Definition at line 237 of file Rocon/include/KNN_Grid.h.

  {
    SpaceCell * cell = grid->locate(p);
    cell->push_back(item);
        //cout << "Size: "<< cell->size() << "\n" ;
    return cell->size();
  }

int insertRange ( T &  item, Point3D &  p, Point3D &  q, Point3D &  r  )

inline

Definition at line 245 of file Rocon/include/KNN_Grid.h.

                                                               {
        int count = 0;
        
        Index min,max;
        
        Index a = grid->compute_index(p);
        Index b = grid->compute_index(q);
        Index c = grid->compute_index(r);
        
        for(int i=0;i<3;++i)
        {
                min[i] = (a[i]>b[i])?b[i]:a[i];
                max[i] = (a[i]>b[i])?a[i]:b[i];
        }

        for(int i=0;i<3;++i)
        {
                min[i] = (min[i]>c[i])?c[i]:min[i];
                max[i] = (max[i]>c[i])?max[i]:c[i];
        }

        for(unsigned int i=min[0]; i<=max[0]; ++i)
        {
                for(unsigned int j=min[1]; j<=max[1]; ++j)
                {
                        for(unsigned int k=min[2]; k<=max[2]; ++k)
                        {
                                Index x(i,j,k);
                                SpaceCell * cell = grid->locate_index(x);
                                typename vector<T>::iterator temp ;
                                //temp = find(cell->begin(), cell->end(), item);
                                //if(temp == cell->end() || cell->size() == 0)
                                //{
                                        cell->push_back(item);
                                        count ++;//= cell->size();
                                //}
                        }
                }
        }
        
        return count;
  }

int insertRange ( T &  item, Point3D &  p, Point3D &  q, Point3D &  r  )

inline

Definition at line 245 of file Rocprop/include/KNN_Grid.h.

                                                               {
        int count = 0;
        
        Index min,max;
        
        Index a = grid->compute_index(p);
        Index b = grid->compute_index(q);
        Index c = grid->compute_index(r);
        
        for(int i=0;i<3;++i)
        {
                min[i] = (a[i]>b[i])?b[i]:a[i];
                max[i] = (a[i]>b[i])?a[i]:b[i];
        }

        for(int i=0;i<3;++i)
        {
                min[i] = (min[i]>c[i])?c[i]:min[i];
                max[i] = (max[i]>c[i])?max[i]:c[i];
        }

        for(int i=min[0]; i<=max[0]; ++i)
        {
                for(int j=min[1]; j<=max[1]; ++j)
                {
                        for(int k=min[2]; k<=max[2]; ++k)
                        {
                                Index x(i,j,k);
                                SpaceCell * cell = grid->locate_index(x);
                                typename vector<T>::iterator temp ;
                                //temp = find(cell->begin(), cell->end(), item);
                                //if(temp == cell->end() || cell->size() == 0)
                                //{
                                        cell->push_back(item);
                                        count ++;//= cell->size();
                                //}
                        }
                }
        }
        
        return count;
  }

unsigned int k_nearest ( Point3D &  p, int  k, vector< T > &  nbrs  )

inline

Definition at line 294 of file Rocprop/include/KNN_Grid.h.

                                                             {
    KNNnbr pnew;
    priority_queue<KNNnbr> pts;
    vector< T > * cell_pts = NULL;
 
    UniformGrid::Index grid_coord = grid->compute_index(p);
    for(int x = grid_coord[0] - 2; x<grid_coord[0]+2;x++)
      for(int y = grid_coord[1] - 2; y<grid_coord[1]+2;y++)
        for(int z = grid_coord[2] - 2; z<grid_coord[2]+2;z++)
          {
            //get cell points
            UniformGrid::Index i(x,y,z); 
            //cerr << "Checking cell: [" << x <<  " , " << y << " , " 
            // << z << "]" << endl; 
            cell_pts = get_cell(i);
            if (cell_pts != NULL)
              {
                for(int j=0;j<cell_pts->size();j++)
                  {
                    pnew.distance = euclid_distance((*cell_pts)[j].coord,p);
                    pnew.item = (*cell_pts)[j];
                    pts.push(pnew);
                // insert candidates into queue
                  }
              }
          }
    int j=0;
    int ptnum = pts.size();
    nbrs.clear();
    while( (j<k) && (!pts.empty()))
      {
        for(int j=0; j<k;j++)
          {
            KNNnbr n = pts.top();
            nbrs.push_back(n.item);
            pts.pop();
          }
      }
    return ptnum;
  }

unsigned int k_nearest ( Point3D &  p, int  k, vector< T > &  nbrs  )

inline

Definition at line 294 of file Rocon/include/KNN_Grid.h.

                                                             {
    KNNnbr pnew;
    priority_queue<KNNnbr> pts;
    vector< T > * cell_pts = NULL;
 
    UniformGrid::Index grid_coord = grid->compute_index(p);
    for(int x = grid_coord[0] - 2; x<grid_coord[0]+2;x++)
      for(int y = grid_coord[1] - 2; y<grid_coord[1]+2;y++)
        for(int z = grid_coord[2] - 2; z<grid_coord[2]+2;z++)
          {
            //get cell points
            UniformGrid::Index i(x,y,z); 
            //cerr << "Checking cell: [" << x <<  " , " << y << " , " 
            // << z << "]" << endl; 
            cell_pts = get_cell(i);
            if (cell_pts != NULL)
              {
                for(int j=0;j<cell_pts->size();j++)
                  {
                    pnew.distance = euclid_distance((*cell_pts)[j].coord,p);
                    pnew.item = (*cell_pts)[j];
                    pts.push(pnew);
                // insert candidates into queue
                  }
              }
          }
    int j=0;
    int ptnum = pts.size();
    nbrs.clear();
    while( (j<k) && (!pts.empty()))
      {
        for(int j=0; j<k;j++)
          {
            KNNnbr n = pts.top();
            nbrs.push_back(n.item);
            pts.pop();
          }
      }
    return ptnum;
  }

Member Data Documentation

Point3D bbmax

private

Definition at line 196 of file Rocon/include/KNN_Grid.h.

Point3D bbmin

private

Definition at line 195 of file Rocon/include/KNN_Grid.h.

int cell_dim

private

Definition at line 197 of file Rocon/include/KNN_Grid.h.

float cellsz

private

Definition at line 198 of file Rocon/include/KNN_Grid.h.

SparseGrid< SpaceCell > * grid

private

Definition at line 200 of file Rocon/include/KNN_Grid.h.

---

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

• Rocon/include/KNN_Grid.h
• Rocprop/include/KNN_Grid.h