1 // Copyright (C) 2007-2008 CEA/DEN, EDF R&D
3 // This library is free software; you can redistribute it and/or
4 // modify it under the terms of the GNU Lesser General Public
5 // License as published by the Free Software Foundation; either
6 // version 2.1 of the License.
8 // This library is distributed in the hope that it will be useful,
9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 // Lesser General Public License for more details.
13 // You should have received a copy of the GNU Lesser General Public
14 // License along with this library; if not, write to the Free Software
15 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
19 #ifndef __BBTREE_TXX__
20 #define __BBTREE_TXX__
28 template <int dim, class ConnType = int>
39 typename std::vector<ConnType> _elems;
44 static const int MIN_NB_ELEMS=15;
45 static const int MAX_LEVEL=20;
49 Constructor of the bounding box tree
50 \param bbs pointer to the [xmin1 xmax1 ymin1 ymax1 xmin2 xmax2 ...] array containing the bounding boxes that are to be indexed.
51 \param elems array to the indices of the elements contained in the BBTree
52 \param level level in the BBTree recursive structure
53 \param nbelems nb of elements in the BBTree
54 \param epsilon precision to which points are decided to be coincident
56 Parameters \a elems and \a level are used only by BBTree itself for creating trees recursively. A typical use is therefore :
59 double* bbs= new double[2*2*nbelems];
62 BBTree<2> tree = new BBTree<2>(elems,0,0,nbelems,1e-12);
66 BBTree(double* bbs, ConnType* elems, int level, ConnType nbelems, double epsilon=1E-12):
67 _left(0), _right(0), _level(level), _bb(bbs), _terminal(false),_nbelems(nbelems),_epsilon(epsilon)
69 if (nbelems < MIN_NB_ELEMS || level> MAX_LEVEL)
74 double* nodes=new double [nbelems];
75 _elems.resize(nbelems);
76 for (ConnType i=0; i<nbelems; i++)
85 nodes[i]=bbs[elem*dim*2+(level%dim)*2];
87 if (_terminal) { delete[] nodes; return;}
89 std::nth_element<double*>(nodes, nodes+nbelems/2, nodes+nbelems);
90 double median = *(nodes+nbelems/2);
92 // std:: cout << *median <<std::endl;
94 std::vector<ConnType> new_elems_left;
95 std::vector<ConnType> new_elems_right;
97 new_elems_left.reserve(nbelems/2+1);
98 new_elems_right.reserve(nbelems/2+1);
99 double max_left = -std::numeric_limits<double>::max();
100 double min_right= std::numeric_limits<double>::max();
101 for (int i=0; i<nbelems;i++)
108 double max=bbs[elem*dim*2+(level%dim)*2+1];
109 double min = bbs[elem*dim*2+(level%dim)*2];
113 new_elems_right.push_back(elem);
114 if (min<min_right) min_right = min;
119 new_elems_left.push_back(elem);
120 if (max>max_left) max_left = max;
125 _max_left=max_left+_epsilon;
126 _min_right=min_right-_epsilon;
127 _left=new BBTree(bbs, &(new_elems_left[0]), level+1, new_elems_left.size(),_epsilon);
128 _right=new BBTree(bbs, &(new_elems_right[0]), level+1, new_elems_right.size(),_epsilon);
136 if (_left!=0) delete _left;
137 if (_right!=0) delete _right;
142 /*! returns in \a elems the list of elements potentially intersecting the bounding box pointed to by \a bb
144 \param bb pointer to query bounding box
145 \param elems list of elements (given in 0-indexing that is to say in \b C \b mode) intersecting the bounding box
148 void getIntersectingElems(const double* bb, std::vector<ConnType>& elems) const
150 // terminal node : return list of elements intersecting bb
153 for (int i=0; i<_nbelems; i++)
155 const double* const bb_ptr=_bb+_elems[i]*2*dim;
156 bool intersects = true;
157 for (int idim=0; idim<dim; idim++)
159 if (bb_ptr[idim*2]-bb[idim*2+1]>-_epsilon|| bb_ptr[idim*2+1]-bb[idim*2]<_epsilon)
164 elems.push_back(_elems[i]);
171 double min = bb[(_level%dim)*2];
172 double max = bb[(_level%dim)*2+1];
173 if (max < _min_right)
175 _left->getIntersectingElems(bb, elems);
180 _right->getIntersectingElems(bb,elems);
183 _left->getIntersectingElems(bb,elems);
184 _right->getIntersectingElems(bb,elems);
188 /*! returns in \a elems the list of elements potentially containing the point pointed to by \a xx
189 \param xx pointer to query point coords
190 \param elems list of elements (given in 0-indexing) intersecting the bounding box
193 void getElementsAroundPoint(const double* xx, std::vector<ConnType>& elems) const
195 // terminal node : return list of elements intersecting bb
198 for (ConnType i=0; i<_nbelems; i++)
200 const double* const bb_ptr=_bb+_elems[i]*2*dim;
201 bool intersects = true;
202 for (int idim=0; idim<dim; idim++)
204 if (bb_ptr[idim*2]-xx[idim]>_epsilon|| bb_ptr[idim*2+1]-xx[idim]<-_epsilon)
209 elems.push_back(_elems[i]);
216 if (xx[_level%dim] < _min_right)
218 _left->getElementsAroundPoint(xx, elems);
221 if (xx[_level%dim]> _max_left)
223 _right->getElementsAroundPoint(xx,elems);
226 _left->getElementsAroundPoint(xx,elems);
227 _right->getElementsAroundPoint(xx,elems);
234 if (_terminal) return _nbelems;
235 return _left->size()+_right->size();