src/HYDROData/HYDROData_QuadtreeNode.cxx

   1 // Copyright (C) 2007-2014  CEA/DEN, EDF R&D, OPEN CASCADE
   2 //
   3 // Copyright (C) 2003-2007  OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
   4 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
   5 //
   6 // This library is free software; you can redistribute it and/or
   7 // modify it under the terms of the GNU Lesser General Public
   8 // License as published by the Free Software Foundation; either
   9 // version 2.1 of the License, or (at your option) any later version.
  10 //
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // Lesser General Public License for more details.
  15 //
  16 // You should have received a copy of the GNU Lesser General Public
  17 // License along with this library; if not, write to the Free Software
  18 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  19 //
  20 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  21 //
  22
  23 //  HYDRO HYDROData_QuadtreeNode : Quadtree with Nodes set (from SMESH module)
  24 //  inherites class HYDROData_Quadtree
  25 //  File      : HYDROData_QuadtreeNode.cxx
  26 //  Created   : Tue Jan 16 16:00:00 2007
  27 //  Author    : Nicolas Geimer & Aurelien Motteux (OCC)
  28 //  Module    : HYDROData
  29 //
  30 #include "HYDROData_QuadtreeNode.hxx"
  31
  32 #include <gp_Pnt.hxx>
  33
  34 //#define _DEVDEBUG_
  35 #include "HYDRO_trace.hxx"
  36
  37 using namespace std;
  38
  39 /*!
  40  * \brief Constructor : Build all the Quadtree using Compute()
  41  * \param theNodes - Set of nodes, the Quadtree is built from this nodes
  42  * \param maxLevel - Maximum level for the leaves
  43  * \param maxNbNodes - Maximum number of nodes, a leaf can contain
  44  * \param minBoxSize - Minimal size of the Quadtree Box
  45  */
  46 HYDROData_QuadtreeNode::HYDROData_QuadtreeNode(Nodes_3D* theNodes,
  47                                                const int maxLevel,
  48                                                const int maxNbNodes,
  49                                                const double minBoxSize) :
  50     HYDROData_Quadtree(new Limit(maxLevel, minBoxSize, maxNbNodes)), myNodes(theNodes), myPrecision(0.25)
  51 {
  52   //DEBTRACE("---------------------------- HYDROData_QuadtreeNode root constructor");
  53    if (myNodes)
  54     {
  55       //DEBTRACE(" --- start compute");
  56       compute();
  57       //DEBTRACE(" --- end compute");
  58     }
  59 }
  60
  61 /*!
  62  * \brief Constructor used to allocate a child
  63  */
  64 HYDROData_QuadtreeNode::HYDROData_QuadtreeNode() :
  65     HYDROData_Quadtree(), myNodes(0), myPrecision(0.25)
  66 {
  67   myNodes = new Nodes_3D();
  68 }
  69
  70 /*!
  71  * \brief virtual destructor: deletes myNodes
  72  */
  73 HYDROData_QuadtreeNode::~HYDROData_QuadtreeNode()
  74 {
  75   if (myNodes)
  76     {
  77       delete myNodes;
  78       myNodes = 0;
  79     }
  80 }
  81
  82 /*!
  83  * \brief Set the nodes and compute the quadtree,
  84  * when the nodes are not given to the public constructor (delayed compute)
  85  */
  86 void HYDROData_QuadtreeNode::setNodesAndCompute(Nodes_3D* theNodes)
  87 {
  88   myNodes = theNodes;
  89   if (myNodes)
  90     {
  91       DEBTRACE(" --- start compute");
  92       compute();
  93       DEBTRACE(" --- end compute : children & height " << this->nbChildren() << " " << this->getHeight());
  94       DEBTRACE("Bounding box min: " << this->myBox->CornerMin().X() << " "  << this->myBox->CornerMin().Y());
  95       DEBTRACE("Bounding box max: " << this->myBox->CornerMax().X() << " "  << this->myBox->CornerMax().Y());
  96     }
  97 }
  98
  99 /*!
 100  * \brief Return max number of nodes in a tree leaf
 101  */
 102 int HYDROData_QuadtreeNode::getMaxNbNodes() const
 103 {
 104   return ((Limit*) myLimit)->myMaxNbNodes;
 105 }
 106
 107 /*!
 108  * \brief Construct an empty HYDROData_QuadtreeNode used by HYDROData_Quadtree::buildChildren()
 109  */
 110 HYDROData_Quadtree* HYDROData_QuadtreeNode::newChild() const
 111 {
 112   return new HYDROData_QuadtreeNode();
 113 }
 114
 115 /*!
 116  * \brief Compute the first bounding box
 117  *
 118  * We take the max/min coord of the nodes
 119  */
 120 Bnd_B2d* HYDROData_QuadtreeNode::buildRootBox()
 121 {
 122   Bnd_B2d* box = new Bnd_B2d;
 123   Nodes_3D::iterator it = myNodes->begin();
 124   for (; it != myNodes->end(); it++)
 125     {
 126       const gpi_XYZ* n1 = *it;
 127       gp_XY p1(n1->X(), n1->Y());
 128       box->Add(p1);
 129     }
 130   if (myNodes->size() <= getMaxNbNodes())
 131     myIsLeaf = true;
 132
 133   return box;
 134 }
 135
 136 /*!
 137  * \brief Tells us if Node is inside the current box with the precision "precision"
 138  * \param Node - Node
 139  * \param precision - The box is enlarged with this precision
 140  * \retval bool - True if Node is in the box within precision
 141  */
 142 const bool HYDROData_QuadtreeNode::isInside(const gp_XY& p, const double precision)
 143 {
 144   if (precision <= 0.)
 145     return !(getBox()->IsOut(p));
 146   Bnd_B2d BoxWithPrecision = *getBox();
 147   BoxWithPrecision.Enlarge(precision);
 148   return !BoxWithPrecision.IsOut(p);
 149 }
 150
 151 /*!
 152  * \brief Set the data of the children
 153  * Shares the father's data with each of his child
 154  */
 155 void HYDROData_QuadtreeNode::buildChildrenData()
 156 {
 157   gp_XY min = getBox()->CornerMin();
 158   gp_XY max = getBox()->CornerMax();
 159   gp_XY mid = (min + max) / 2.;
 160
 161   //DEBTRACE("buildChildrenData level, min, max, nbNodes "<<level()<< " ("<< min.X()<<","<< min.Y()<<") ("<< max.X()<<","<< max.Y()<<") "<< myNodes->size());
 162   Nodes_3D::iterator it = myNodes->begin();
 163   while (it != myNodes->end())
 164     {
 165       gpi_XYZ* n1 = *it;
 166       int ChildBoxNum = getChildIndex(n1->X(), n1->Y(), mid);
 167       HYDROData_QuadtreeNode* myChild = dynamic_cast<HYDROData_QuadtreeNode*>(myChildren[ChildBoxNum]);
 168       myChild->myNodes->push_back(n1);
 169       myNodes->erase(it);
 170       it = myNodes->begin();
 171     }
 172   for (int i = 0; i < 4; i++)
 173     {
 174       HYDROData_QuadtreeNode* myChild = dynamic_cast<HYDROData_QuadtreeNode*>(myChildren[i]);
 175       if (myChild->myNodes->size() <= getMaxNbNodes())
 176         {
 177           myChild->myIsLeaf = true;
 178           //DEBTRACE("buildChildrenData leaf nbNodes "<< myChild->myNodes->size());
 179         }
 180     }
 181 }
 182
 183 /*!
 184  * \brief Return in Result a list of Nodes potentials to be near Node
 185  * \param Node - Node
 186  * \param precision - precision used
 187  * \param Result - list of Nodes potentials to be near Node
 188  */
 189 void HYDROData_QuadtreeNode::NodesAround(const gp_XY& Node,
 190                                          list<const gpi_XYZ*>* Result,
 191                                          const double precision)
 192 {
 193   gp_XY p(Node);
 194   if (isInside(p, precision))
 195     {
 196       if (isLeaf())
 197         {
 198           Result->insert(Result->end(), myNodes->begin(), myNodes->end());
 199           //DEBTRACE("Leaf result "<< Result->size());
 200         }
 201       else
 202         {
 203           for (int i = 0; i < 4; i++)
 204             {
 205               HYDROData_QuadtreeNode* myChild = dynamic_cast<HYDROData_QuadtreeNode*>(myChildren[i]);
 206               myChild->NodesAround(p, Result, precision);
 207             }
 208         }
 209     }
 210 }
 211
 212 /*!
 213  * \brief Return in dist2Nodes nodes mapped to their square distance from Node
 214  *  \param node - node to find nodes closest to
 215  *  \param dist2Nodes - map of found nodes and their distances
 216  *  \param precision - radius of a sphere to check nodes inside
 217  *  \retval bool - true if an exact overlapping found !!!
 218  */
 219 bool HYDROData_QuadtreeNode::NodesAround(const gp_XY& node,
 220                                          map<double, const gpi_XYZ*>& dist2Nodes,
 221                                          double precision)
 222 {
 223   if (!dist2Nodes.empty())
 224     precision = min(precision, sqrt(dist2Nodes.begin()->first));
 225   else if (precision == 0.)
 226     precision = maxSize() / 2;
 227
 228   if (isInside(node, precision))
 229     {
 230       if (!isLeaf())
 231         {
 232           // first check a child containing node
 233           gp_XY mid = (getBox()->CornerMin() + getBox()->CornerMax()) / 2.;
 234           int nodeChild = getChildIndex(node.X(), node.Y(), mid);
 235           if (((HYDROData_QuadtreeNode*) myChildren[nodeChild])->NodesAround(node, dist2Nodes, precision))
 236             return true;
 237
 238           for (int i = 0; i < 4; i++)
 239             if (i != nodeChild)
 240               if (((HYDROData_QuadtreeNode*) myChildren[i])->NodesAround(node, dist2Nodes, precision))
 241                 return true;
 242         }
 243       else if (NbNodes() > 0)
 244         {
 245           double minDist = precision * precision;
 246           Nodes_3D::iterator nIt = myNodes->begin();
 247           for (; nIt != myNodes->end(); ++nIt)
 248             {
 249               const gpi_XYZ* p = *nIt;
 250               gp_XY p2(p->X(), p->Y());
 251               double dist2 = (node - p2).SquareModulus();
 252               if (dist2 < minDist)
 253                 dist2Nodes.insert(make_pair(minDist = dist2, p));
 254             }
 255 //       if ( dist2Nodes.size() > 1 ) // leave only closest node in dist2Nodes
 256 //         dist2Nodes.erase( ++dist2Nodes.begin(), dist2Nodes.end());
 257
 258 // true if an exact overlapping found
 259           return (sqrt(minDist) <= precision * 1e-12);
 260         }
 261     }
 262   return false;
 263 }