cgma
GridSearchTree.cpp
Go to the documentation of this file.
00001 #include <math.h>
00002 #include "GridSearchTree.hpp"
00003 
00004 double dist (CubitPoint * a, CubitPoint * b){
00005   return sqrt((a->x() - b->x())*(a->x() - b->x()) + (a->y() - b->y())*(a->y() - b->y()) + (a->z() - b->z())*(a->z() - b->z()) );
00006 }
00007 
00008 CubitPoint * GridSearchTree::fix(CubitPoint * data) {
00009   
00010   long i, j, k;
00011   double x, y, z;
00012 
00013   x=data->x();
00014   y=data->y();
00015   z=data->z();
00016   
00017   // get the coordinates of the box containing the point
00018   i=(long)(x/(2*epsilon));
00019   j=(long)(y/(2*epsilon));
00020   k=(long)(z/(2*epsilon));
00021   
00022 
00023   if (x<0) i--;
00024   if (y<0) j--;
00025   if (z<0) k--;
00026 
00027 
00028   int ofi;
00029   int ofj;
00030   int ofk;
00031   int ii;
00032 
00033   // calculate the i, j, k offset for the seven neighboring boxes to be searched
00034   if (fabs(x-i*2*epsilon) < epsilon) ofi = -1; else ofi = 1;
00035   if (fabs(y-j*2*epsilon) < epsilon) ofj = -1; else ofj = 1;
00036   if (fabs(z-k*2*epsilon) < epsilon) ofk = -1; else ofk = 1;
00037 
00038   // mindist holds the distance to the current closest point
00039   double mindist=2*epsilon;
00040   // curdist holds the distance to the current point
00041   double curdist;
00042   // closest is the current closest point
00043   CubitPoint * closest = NULL;
00044   // curpoint is the current point
00045   CubitPoint * curpoint;
00046 
00047   // construct grid cell ( box ) 
00048   GridSearchTreeNode * curnode = new GridSearchTreeNode(i+ofi,j+ofj,k+ofk);
00049   // attempt to find it in the tree
00050   pos = nodemap.find(curnode);
00051   if (pos!=nodemap.end()) 
00052   {
00053     // if cell is in the tree search its list for close points
00054     DLIList<CubitPoint*> curlist = (*pos).first->get_list();
00055     for (ii= curlist.size(); ii>0; ii--) 
00056     {
00057       curpoint = curlist.get_and_step();
00058       curdist = dist(data, curpoint);
00059       if (curdist<mindist) 
00060       {
00061         closest = curpoint;
00062         mindist=curdist;
00063       }
00064     }
00065   }
00066   delete curnode;
00067   
00068   // construct grid cell ( box ) 
00069   curnode = new GridSearchTreeNode(i+ofi,j+ofj,k);
00070   // attempt to find it in the tree
00071   pos = nodemap.find(curnode);
00072   if (pos!=nodemap.end()) 
00073   {
00074     // if cell is in the tree search its list for close points
00075     DLIList<CubitPoint*> curlist = (*pos).first->get_list();
00076     for (ii= curlist.size(); ii>0; ii--) 
00077     {
00078       curpoint = curlist.get_and_step();
00079       curdist = dist(data, curpoint);
00080       if (curdist<mindist) 
00081       {
00082         closest = curpoint;
00083         mindist=curdist;
00084       }
00085     }
00086   }
00087   delete curnode;
00088   
00089   curnode = new GridSearchTreeNode(i+ofi,j,k+ofk);
00090   pos = nodemap.find(curnode);
00091   if (pos!=nodemap.end()) 
00092   {
00093     DLIList<CubitPoint*> curlist = (*pos).first->get_list();
00094     for (ii= curlist.size(); ii>0; ii--) 
00095     {
00096       curpoint = curlist.get_and_step();
00097       curdist = dist(data, curpoint);
00098       if (curdist<mindist) 
00099       {
00100         closest = curpoint;
00101         mindist=curdist;
00102       }
00103     }
00104   }
00105   delete curnode;
00106   
00107   curnode = new GridSearchTreeNode(i+ofi,j,k);
00108   pos = nodemap.find(curnode);
00109   if (pos!=nodemap.end()) 
00110   {
00111     DLIList<CubitPoint*> curlist = (*pos).first->get_list();
00112     for (ii= curlist.size(); ii>0; ii--) 
00113     {
00114       curpoint = curlist.get_and_step();
00115       curdist = dist(data, curpoint);
00116       if (curdist<mindist) 
00117       {
00118         closest = curpoint;
00119         mindist=curdist;
00120       }
00121     }
00122   }
00123   delete curnode;
00124   
00125   curnode = new GridSearchTreeNode(i,j+ofj,k+ofk);
00126   pos = nodemap.find(curnode);
00127   if (pos!=nodemap.end()) 
00128   {
00129     DLIList<CubitPoint*> curlist = (*pos).first->get_list();
00130     for (ii= curlist.size(); ii>0; ii--) 
00131     {
00132       curpoint = curlist.get_and_step();
00133       curdist = dist(data, curpoint);
00134       if (curdist<mindist) 
00135       {
00136         closest = curpoint;
00137         mindist=curdist;
00138       }
00139     }
00140   }
00141   delete curnode;
00142   
00143   curnode = new GridSearchTreeNode(i,j+ofj,k);
00144   pos = nodemap.find(curnode);
00145   if (pos!=nodemap.end()) 
00146   {
00147     DLIList<CubitPoint*> curlist = (*pos).first->get_list();
00148     for (ii= curlist.size(); ii>0; ii--) 
00149     {
00150       curpoint = curlist.get_and_step();
00151       curdist = dist(data, curpoint);
00152       if (curdist<mindist) 
00153       {
00154         closest = curpoint;
00155         mindist=curdist;
00156       }
00157     }
00158   }
00159   delete curnode;
00160   
00161   curnode = new GridSearchTreeNode(i,j,k+ofk);
00162   pos = nodemap.find(curnode);
00163   if (pos!=nodemap.end()) 
00164   {
00165     DLIList<CubitPoint*> curlist = (*pos).first->get_list();
00166     for (ii= curlist.size(); ii>0; ii--) 
00167     {
00168       curpoint = curlist.get_and_step();
00169       curdist = dist(data, curpoint);
00170       if (curdist<mindist) 
00171       {
00172         closest = curpoint;
00173         mindist=curdist;
00174       }
00175     }
00176   }
00177   delete curnode;
00178   
00179 
00180   curnode = new GridSearchTreeNode(i,j,k);
00181   pos = nodemap.find(curnode);
00182   if (pos!=nodemap.end()) 
00183   { 
00184     DLIList<CubitPoint*> curlist = (*pos).first->get_list();
00185     for (ii= curlist.size(); ii>0; ii--) 
00186     {
00187       curpoint = curlist.get_and_step();
00188       curdist = dist(data, curpoint);
00189       if (curdist<mindist) 
00190       {
00191         closest = curpoint;
00192         mindist=curdist;
00193       }
00194     }
00195   }
00196 
00197   // if closest point is within epsilon distance return the closest point
00198   if (mindist<=epsilon) 
00199   {
00200     delete curnode;
00201     return closest;
00202   }
00203   else 
00204   {          
00205     // add current point and cell to tree
00206     if (pos==nodemap.end()) 
00207     {
00208       curnode->add(data);
00209       nodemap.insert(gmap::value_type(curnode, 1));
00210     }
00211     else 
00212     {
00213       (*pos).first->add(data);
00214       delete curnode;
00215     }
00216     
00217     return data;
00218   }
00219 }
00220 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines