cgma
PointGridSearch.hpp
Go to the documentation of this file.
00001 //- Class: PointGridSearch
00002 //- Description:  The PointGridSearch class is used to maintain a "bucket sort" of
00003 //-               all points used for rapid high performance nearest
00004 //-               neighbor searches.  The object contains a 3-dimensional
00005 //-               array of point lists for each grid cell (i.e. box) containing
00006 //-               points that lie within the grid cell.  appropriate calls that
00007 //-               return point lists that lie in the
00008 //-               neighborhood of an input mesh entity are provided.
00009 //-
00010 //-               PointGridSearch is a simple neighborhood searcher that stores
00011 //-               CubitPoints in a data base broken up into small cubes about
00012 //-               the meshing region of interest.  PointGridSearch provides
00013 //-               functionality to return all points,
00014 //-               that lie within the proximity of a user specified
00015 //-               neighborhood.  The neighborhood is a cartesian bounding box
00016 //-               that can be defined by the user in one of many ways.  These
00017 //-               include:
00018 //-
00019 //-               1) a point (defined by a vector or a points coordinates) in
00020 //-                  which case the neighborhood is the grid cell that
00021 //-                  contains the point,
00022 //-
00023 //-               2) a bounding box that encloses two points (defined by
00024 //-                  vectors or nodal coordinates),
00025 //-
00026 //-               3) a bounding box that encloses a list of points
00027 //-
00028 //-               4) a bounding box that encloses a CubitFacet
00029 //-
00030 //-
00031 //-
00032 //- Owner: David White
00033 //- Checked by: 
00034 //- Modified From: GridSearch
00035 
00036 #ifndef POINT_GRID_SEARCH_HPP
00037 #define POINT_GRID_SEARCH_HPP
00038 
00039 #include "CubitPoint.hpp"
00040 #include "CubitVector.hpp"
00041 
00042 template <class X> class DLIList;
00043 class MemoryManager;
00044 
00045 class PointGridSearch
00046 {
00047 private:
00048 
00049   DLIList<CubitPoint*>** neighborhoodList;
00050     //
00051     //- array of CubitPoint lists for each grid cell
00052   double maxEdgeLength;
00053     //- max EdgeLength as found in constructor.
00054 
00055   void add_point_to_cell(CubitPoint* point, int i);
00056   void remove_point_from_cell(CubitPoint* point, int i);
00057     //
00058     //- functions that add or remove a point from neighborhoodList[i]
00059   
00060 protected:
00061    
00062   CubitVector gridRangeMinimum;
00063   CubitVector gridRangeMaximum;
00064   CubitVector gridCellWidth;
00065   CubitVector gridCellWidthInverse;
00066   int         numberGridCellsX;
00067   int         numberGridCellsY;
00068   int         numberGridCellsZ;
00069   int         numberGridCells;
00070     //
00071     //- search grid parameters
00072 
00073   CubitVector boundingRangeMinimum;
00074   CubitVector boundingRangeMaximum;
00075   int         boundingCellMinimumX;
00076   int         boundingCellMinimumY;
00077   int         boundingCellMinimumZ;
00078   int         boundingCellMaximumX;
00079   int         boundingCellMaximumY;
00080   int         boundingCellMaximumZ;
00081     //
00082     //- bounding box range and cell parameters
00083 
00084   int grid_cell_index(CubitPoint* point);
00085     //
00086     //- returns the cell index of the point
00087 
00088 
00089   virtual void cell_from_range();
00090     //
00091     //- evaluates the integer cell range given the double entity range
00092   
00093   void bounding_range(DLIList<CubitPoint*>& point_list);
00094   void bounding_range(DLIList<CubitFacet*>& facet_list);
00095   void bounding_range(CubitPoint* point);
00096   void bounding_range(const CubitVector& vec);
00097     //
00098     //- evaluates the bounding box entity range from the MRefEntity,
00099     //- point_list,
00100     //- point, or vector
00101 
00102   public:
00103 
00104     PointGridSearch( DLIList<CubitPoint*> *point_list,
00105                     DLIList<CubitFacet*> *facet_list,
00106                     float grid_scale = 2.0);
00107     PointGridSearch(DLIList <CubitPoint*> &point_list,
00108                     double grid_cell_size,
00109                     double grid_scale);
00110   
00111 
00112    virtual ~PointGridSearch();
00113     //
00114     //- grid search constructors and destructor
00115 
00116     CubitVector grid_range_minimum();
00117     CubitVector grid_range_maximum();
00118     CubitVector grid_cell_width();
00119     int         number_grid_cells_x();
00120     int         number_grid_cells_y();
00121     int         number_grid_cells_z();
00122     int         number_grid_cells();
00123     //
00124     //- returns grid parameters
00125 
00126     double      fraction_empty_cells();
00127     double      average_points_per_occupied_cell();
00128     int         total_points_in_grid_cells();
00129     //
00130     //- returns grid search data base information
00131 
00132     CubitVector bounding_range_minimum();
00133     CubitVector bounding_range_maximum();
00134     int         bounding_cell_minimum_x();
00135     int         bounding_cell_minimum_y();
00136     int         bounding_cell_minimum_z();
00137     int         bounding_cell_maximum_x();
00138     int         bounding_cell_maximum_y();
00139     int         bounding_cell_maximum_z();
00140     //
00141     //- returns bounding box range and cell parameters
00142 
00143     void add_point(CubitPoint* point);
00144     void remove_point(CubitPoint* point);
00145     //
00146     //- adds or removes points from the neighbor lists
00147 
00148     int in_grid(const CubitVector& position);
00149     //
00150     //- Determines whether the passed-in position is within the
00151     //- current grid. Returns CUBIT_TRUE or CUBIT_FALSE.
00152 
00153     void change_cell(CubitPoint* point);
00154     //
00155     //- changes a points cell (removes from old list and appends to new one)
00156     //- if it has changed
00157 
00158     void set_neighborhood_bounds(CubitVector& vec);
00159     void set_neighborhood_bounds(const CubitVector& center, double size);
00160     void set_neighborhood_bounds(CubitVector& center, double x,
00161                  double y, double z);
00162     void set_neighborhood_bounds(CubitVector& vec_1, CubitVector& vec_2);
00163     void set_neighborhood_bounds(CubitPoint* point, CubitVector& vec);
00164     void set_neighborhood_bounds(CubitPoint* point);
00165     void set_neighborhood_bounds(CubitPoint* point_1, CubitPoint* point_2);
00166     void set_neighborhood_bounds(DLIList<CubitPoint*>& point_list);
00167     void set_neighborhood_bounds(CubitFacet* facet);
00168     void set_neighborhood_bounds(DLIList<CubitFacet*>& facet_list);
00169     void set_neighborhood_bounds_max_edge(const CubitVector &center,
00170                                           double factor = 1.0);
00171     //
00172     //- evaluates the bounding box (entity range and cell range) from the
00173     //- input entity(ies)
00174 
00175     void get_neighborhood_points(DLIList<CubitPoint*> &point_list);
00176     void get_neighborhood_facets(DLIList<CubitFacet*> &facet_list);
00177     void get_neighborhood_points_sorted(DLIList<CubitPoint*> &point_list,
00178                                        const CubitVector& center,
00179                                        double cut_off);
00180     //
00181     //- returns lists of entities that occupy the cell range set by a previous
00182     //- bounding box call
00183 
00184 
00185 };
00186 
00187 inline CubitVector PointGridSearch::grid_range_minimum()  {return gridRangeMinimum;}
00188 inline CubitVector PointGridSearch::grid_range_maximum()  {return gridRangeMaximum;}
00189 inline CubitVector PointGridSearch::grid_cell_width()     {return gridCellWidth;}
00190 inline int         PointGridSearch::number_grid_cells_x() {return numberGridCellsX;}
00191 inline int         PointGridSearch::number_grid_cells_y() {return numberGridCellsY;}
00192 inline int         PointGridSearch::number_grid_cells_z() {return numberGridCellsZ;}
00193 inline int         PointGridSearch::number_grid_cells()   {return numberGridCells;}
00194 
00195 inline CubitVector PointGridSearch::bounding_range_minimum()
00196                                {return boundingRangeMinimum;}
00197 inline CubitVector PointGridSearch::bounding_range_maximum()
00198                                {return boundingRangeMaximum;}
00199 inline int         PointGridSearch::bounding_cell_minimum_x()
00200                                {return boundingCellMinimumX;} 
00201 inline int         PointGridSearch::bounding_cell_minimum_y()
00202                                {return boundingCellMinimumY;} 
00203 inline int         PointGridSearch::bounding_cell_minimum_z()
00204                                {return boundingCellMinimumZ;} 
00205 inline int         PointGridSearch::bounding_cell_maximum_x()
00206                                {return boundingCellMaximumX;} 
00207 inline int         PointGridSearch::bounding_cell_maximum_y()
00208                                {return boundingCellMaximumY;} 
00209 inline int         PointGridSearch::bounding_cell_maximum_z()
00210                                {return boundingCellMaximumZ;} 
00211 
00212 inline int         PointGridSearch::grid_cell_index(CubitPoint* point)
00213 {
00214   CubitVector range_vec = point->coordinates();
00215   range_vec -= gridRangeMinimum;
00216 
00217   int i = (int) (range_vec.x() * gridCellWidthInverse.x());
00218   int j = (int) (range_vec.y() * gridCellWidthInverse.y());
00219   int k = (int) (range_vec.z() * gridCellWidthInverse.z());
00220 
00221   return numberGridCellsX * (numberGridCellsY * k + j) + i;
00222 }
00223 
00224 inline void PointGridSearch::bounding_range(const CubitVector& vec)
00225 {
00226   if (vec.x() < boundingRangeMinimum.x())
00227     boundingRangeMinimum.x(vec.x());
00228   else if (vec.x() > boundingRangeMaximum.x())
00229     boundingRangeMaximum.x(vec.x());
00230 
00231   if (vec.y() < boundingRangeMinimum.y())
00232     boundingRangeMinimum.y(vec.y());
00233   else if (vec.y() > boundingRangeMaximum.y())
00234     boundingRangeMaximum.y(vec.y());
00235 
00236   if (vec.z() < boundingRangeMinimum.z())
00237     boundingRangeMinimum.z(vec.z());
00238   else if (vec.z() > boundingRangeMaximum.z())
00239     boundingRangeMaximum.z(vec.z());
00240 }
00241 
00242 inline void PointGridSearch::bounding_range(CubitPoint* point)
00243 {
00244   double xpos = point->x();
00245   double ypos = point->y();
00246   double zpos = point->z();
00247   
00248   if (xpos < boundingRangeMinimum.x())
00249     boundingRangeMinimum.x(xpos);
00250   else if (xpos > boundingRangeMaximum.x())
00251     boundingRangeMaximum.x(xpos);
00252 
00253   if (ypos < boundingRangeMinimum.y())
00254     boundingRangeMinimum.y(ypos);
00255   else if (ypos > boundingRangeMaximum.y())
00256     boundingRangeMaximum.y(ypos);
00257 
00258   if (zpos < boundingRangeMinimum.z())
00259     boundingRangeMinimum.z(zpos);
00260   else if (zpos > boundingRangeMaximum.z())
00261     boundingRangeMaximum.z(zpos);
00262 }
00263 
00264 #endif // GRID_SEARCH_BASE_HPP
00265 
00266     
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines