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)
  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()
  66 {
  67   if (myNodes == 0)
  68     myNodes = new Nodes_3D();
  69 }
  70
  71 /*!
  72  * \brief virtual destructor: deletes myNodes
  73  */
  74 HYDROData_QuadtreeNode::~HYDROData_QuadtreeNode()
  75 {
  76   if (myNodes)
  77     {
  78       delete myNodes;
  79       myNodes = 0;
  80     }
  81 }
  82
  83 /*!
  84  * \brief Set the nodes and compute the quadtree,
  85  * when the nodes are not given to the public constructor (delayed compute)
  86  */
  87 void HYDROData_QuadtreeNode::setNodesAndCompute(Nodes_3D* theNodes)
  88 {
  89   myNodes = theNodes;
  90   if (myNodes)
  91     {
  92       DEBTRACE(" --- start compute");
  93       compute();
  94       DEBTRACE(" --- end compute : children & height " << this->nbChildren() << " " << this->getHeight());
  95       DEBTRACE("Bounding box min: " << this->myBox->CornerMin().X() << " "  << this->myBox->CornerMin().Y());
  96       DEBTRACE("Bounding box max: " << this->myBox->CornerMax().X() << " "  << this->myBox->CornerMax().Y());
  97     }
  98 }
  99
 100 /*!
 101  * \brief Return max number of nodes in a tree leaf
 102  */
 103 int HYDROData_QuadtreeNode::getMaxNbNodes() const
 104 {
 105   return ((Limit*) myLimit)->myMaxNbNodes;
 106 }
 107
 108 /*!
 109  * \brief Construct an empty HYDROData_QuadtreeNode used by HYDROData_Quadtree::buildChildren()
 110  */
 111 HYDROData_Quadtree* HYDROData_QuadtreeNode::newChild() const
 112 {
 113   return new HYDROData_QuadtreeNode();
 114 }
 115
 116 /*!
 117  * \brief Compute the first bounding box
 118  *
 119  * We take the max/min coord of the nodes
 120  */
 121 Bnd_B2d* HYDROData_QuadtreeNode::buildRootBox()
 122 {
 123   Bnd_B2d* box = new Bnd_B2d;
 124   Nodes_3D::iterator it = myNodes->begin();
 125   for (; it != myNodes->end(); it++)
 126     {
 127       const gp_XYZ* n1 = *it;
 128       gp_XY p1(n1->X(), n1->Y());
 129       box->Add(p1);
 130     }
 131   if (myNodes->size() <= getMaxNbNodes())
 132     myIsLeaf = true;
 133
 134   return box;
 135 }
 136
 137 /*!
 138  * \brief Tells us if Node is inside the current box with the precision "precision"
 139  * \param Node - Node
 140  * \param precision - The box is enlarged with this precision
 141  * \retval bool - True if Node is in the box within precision
 142  */
 143 const bool HYDROData_QuadtreeNode::isInside(const gp_XY& p, const double precision)
 144 {
 145   if (precision <= 0.)
 146     return !(getBox()->IsOut(p));
 147   Bnd_B2d BoxWithPrecision = *getBox();
 148   BoxWithPrecision.Enlarge(precision);
 149   return !BoxWithPrecision.IsOut(p);
 150 }
 151
 152 /*!
 153  * \brief Set the data of the children
 154  * Shares the father's data with each of his child
 155  */
 156 void HYDROData_QuadtreeNode::buildChildrenData()
 157 {
 158   gp_XY min = getBox()->CornerMin();
 159   gp_XY max = getBox()->CornerMax();
 160   gp_XY mid = (min + max) / 2.;
 161
 162   //DEBTRACE("buildChildrenData level, min, max, nbNodes "<<level()<< " ("<< min.X()<<","<< min.Y()<<") ("<< max.X()<<","<< max.Y()<<") "<< myNodes->size());
 163   Nodes_3D::iterator it = myNodes->begin();
 164   while (it != myNodes->end())
 165     {
 166       gp_XYZ* n1 = *it;
 167       int ChildBoxNum = getChildIndex(n1->X(), n1->Y(), mid);
 168       HYDROData_QuadtreeNode* myChild = dynamic_cast<HYDROData_QuadtreeNode*>(myChildren[ChildBoxNum]);
 169       myChild->myNodes->push_back(n1);
 170       myNodes->erase(it);
 171       it = myNodes->begin();
 172     }
 173   for (int i = 0; i < 4; i++)
 174     {
 175       HYDROData_QuadtreeNode* myChild = dynamic_cast<HYDROData_QuadtreeNode*>(myChildren[i]);
 176       if (myChild->myNodes->size() <= getMaxNbNodes())
 177         {
 178           myChild->myIsLeaf = true;
 179           //DEBTRACE("buildChildrenData leaf nbNodes "<< myChild->myNodes->size());
 180         }
 181     }
 182 }
 183
 184 /*!
 185  * \brief Return in Result a list of Nodes potentials to be near Node
 186  * \param Node - Node
 187  * \param precision - precision used
 188  * \param Result - list of Nodes potentials to be near Node
 189  */
 190 void HYDROData_QuadtreeNode::NodesAround(const gp_XY& Node,
 191                                          list<const gp_XYZ*>* Result,
 192                                          const double precision)
 193 {
 194   gp_XY p(Node);
 195   if (isInside(p, precision))
 196     {
 197       if (isLeaf())
 198         {
 199           Result->insert(Result->end(), myNodes->begin(), myNodes->end());
 200           //DEBTRACE("Leaf result "<< Result->size());
 201         }
 202       else
 203         {
 204           for (int i = 0; i < 4; i++)
 205             {
 206               HYDROData_QuadtreeNode* myChild = dynamic_cast<HYDROData_QuadtreeNode*>(myChildren[i]);
 207               myChild->NodesAround(p, Result, precision);
 208             }
 209         }
 210     }
 211 }
 212
 213 /*!
 214  * \brief Return in dist2Nodes nodes mapped to their square distance from Node
 215  *  \param node - node to find nodes closest to
 216  *  \param dist2Nodes - map of found nodes and their distances
 217  *  \param precision - radius of a sphere to check nodes inside
 218  *  \retval bool - true if an exact overlapping found !!!
 219  */
 220 bool HYDROData_QuadtreeNode::NodesAround(const gp_XY& node,
 221                                          map<double, const gp_XYZ*>& dist2Nodes,
 222                                          double precision)
 223 {
 224   if (!dist2Nodes.empty())
 225     precision = min(precision, sqrt(dist2Nodes.begin()->first));
 226   else if (precision == 0.)
 227     precision = maxSize() / 2;
 228
 229   if (isInside(node, precision))
 230     {
 231       if (!isLeaf())
 232         {
 233           // first check a child containing node
 234           gp_XY mid = (getBox()->CornerMin() + getBox()->CornerMax()) / 2.;
 235           int nodeChild = getChildIndex(node.X(), node.Y(), mid);
 236           if (((HYDROData_QuadtreeNode*) myChildren[nodeChild])->NodesAround(node, dist2Nodes, precision))
 237             return true;
 238
 239           for (int i = 0; i < 4; i++)
 240             if (i != nodeChild)
 241               if (((HYDROData_QuadtreeNode*) myChildren[i])->NodesAround(node, dist2Nodes, precision))
 242                 return true;
 243         }
 244       else if (NbNodes() > 0)
 245         {
 246           double minDist = precision * precision;
 247           Nodes_3D::iterator nIt = myNodes->begin();
 248           for (; nIt != myNodes->end(); ++nIt)
 249             {
 250               const gp_XYZ* p = *nIt;
 251               gp_XY p2(p->X(), p->Y());
 252               double dist2 = (node - p2).SquareModulus();
 253               if (dist2 < minDist)
 254                 dist2Nodes.insert(make_pair(minDist = dist2, p));
 255             }
 256 //       if ( dist2Nodes.size() > 1 ) // leave only closest node in dist2Nodes
 257 //         dist2Nodes.erase( ++dist2Nodes.begin(), dist2Nodes.end());
 258
 259 // true if an exact overlapping found
 260           return (sqrt(minDist) <= precision * 1e-12);
 261         }
 262     }
 263   return false;
 264 }