-// Copyright (C) 2007-2008 CEA/DEN, EDF R&D
+// Copyright (C) 2007-2015 CEA/DEN, EDF R&D
//
-// This library is free software; you can redistribute it and/or
-// modify it under the terms of the GNU Lesser General Public
-// License as published by the Free Software Foundation; either
-// version 2.1 of the License.
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public
+// License as published by the Free Software Foundation; either
+// version 2.1 of the License, or (at your option) any later version.
//
-// This library is distributed in the hope that it will be useful,
-// but WITHOUT ANY WARRANTY; without even the implied warranty of
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
-// Lesser General Public License for more details.
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Lesser General Public License for more details.
//
-// You should have received a copy of the GNU Lesser General Public
-// License along with this library; if not, write to the Free Software
-// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+// You should have received a copy of the GNU Lesser General Public
+// License along with this library; if not, write to the Free Software
+// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
//
-// See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
+// See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
//
#ifndef __BBTREE_TXX__
#define __BBTREE_TXX__
#include <iostream>
#include <limits>
+#include <cmath>
template <int dim, class ConnType = int>
class BBTree
int _level;
double _max_left;
double _min_right;
- double* _bb;
+ const double *_bb;
typename std::vector<ConnType> _elems;
bool _terminal;
ConnType _nbelems;
\param elems array to the indices of the elements contained in the BBTree
\param level level in the BBTree recursive structure
\param nbelems nb of elements in the BBTree
- \param epsilon precision to which points are decided to be coincident
+ \param epsilon precision to which points are decided to be coincident. Epsilon can be positive or negative.
+ If \a epsilon is positive the request method will enlarge the computed bounding box (more matching elems return).
+ If negative the given bounding box will be tighten (less matching elems return).
Parameters \a elems and \a level are used only by BBTree itself for creating trees recursively. A typical use is therefore :
\code
\endcode
*/
- BBTree(double* bbs, ConnType* elems, int level, ConnType nbelems, double epsilon=1E-12):
+ BBTree(const double* bbs, ConnType* elems, int level, ConnType nbelems, double epsilon=1e-12):
_left(0), _right(0), _level(level), _bb(bbs), _terminal(false),_nbelems(nbelems),_epsilon(epsilon)
{
if (nbelems < MIN_NB_ELEMS || level> MAX_LEVEL)
}
- _max_left=max_left+_epsilon;
- _min_right=min_right-_epsilon;
- _left=new BBTree(bbs, &(new_elems_left[0]), level+1, new_elems_left.size(),_epsilon);
- _right=new BBTree(bbs, &(new_elems_right[0]), level+1, new_elems_right.size(),_epsilon);
+ _max_left=max_left+std::abs(_epsilon);
+ _min_right=min_right-std::abs(_epsilon);
+ ConnType *tmp;
+ tmp=0;
+ if(!new_elems_left.empty())
+ tmp=&(new_elems_left[0]);
+ _left=new BBTree(bbs, tmp, level+1, (int)new_elems_left.size(),_epsilon);
+ tmp=0;
+ if(!new_elems_right.empty())
+ tmp=&(new_elems_right[0]);
+ _right=new BBTree(bbs, tmp, level+1, (int)new_elems_right.size(),_epsilon);
}
_right->getIntersectingElems(bb,elems);
}
+ /*!
+ * This method is very close to getIntersectingElems except that it returns number of elems instead of elems themselves.
+ */
+ int getNbOfIntersectingElems(const double* bb)
+ {
+ // terminal node : return list of elements intersecting bb
+ int ret(0);
+ if (_terminal)
+ {
+ for (int i=0; i<_nbelems; i++)
+ {
+ const double* const bb_ptr=_bb+_elems[i]*2*dim;
+ bool intersects = true;
+ for (int idim=0; idim<dim; idim++)
+ {
+ if (bb_ptr[idim*2]-bb[idim*2+1]>-_epsilon|| bb_ptr[idim*2+1]-bb[idim*2]<_epsilon)
+ intersects=false;
+ }
+ if (intersects)
+ ret++;
+ }
+ return ret;
+ }
+ //non terminal node
+ double min = bb[(_level%dim)*2];
+ double max = bb[(_level%dim)*2+1];
+ if (max < _min_right)
+ return _left->getNbOfIntersectingElems(bb);
+ if (min> _max_left)
+ return _right->getNbOfIntersectingElems(bb);
+ return _left->getNbOfIntersectingElems(bb)+_right->getNbOfIntersectingElems(bb);
+ }
+
/*! returns in \a elems the list of elements potentially containing the point pointed to by \a xx
\param xx pointer to query point coords
