1 // Copyright (C) 2007-2014 CEA/DEN, EDF R&D, OPEN CASCADE
3 // Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
4 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
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.
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.
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
20 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
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)
30 #include "HYDROData_QuadtreeNode.hxx"
35 #include "HYDRO_trace.hxx"
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
46 HYDROData_QuadtreeNode::HYDROData_QuadtreeNode(Nodes_3D* theNodes,
49 const double minBoxSize) :
50 HYDROData_Quadtree(new Limit(maxLevel, minBoxSize, maxNbNodes)), myNodes(theNodes)
52 DEBTRACE("---------------------------- HYDROData_QuadtreeNode root constructor");
55 DEBTRACE(" --- start compute");
57 DEBTRACE(" --- end compute");
62 * \brief Constructor used to allocate a child
64 HYDROData_QuadtreeNode::HYDROData_QuadtreeNode() :
68 myNodes = new Nodes_3D();
72 * \brief virtual destructor: deletes myNodes
74 HYDROData_QuadtreeNode::~HYDROData_QuadtreeNode()
84 * \brief Set the nodes and compute the quadtree,
85 * when the nodes are not given to the public constructor (delayed compute)
87 void HYDROData_QuadtreeNode::setNodesAndCompute(Nodes_3D* theNodes)
92 DEBTRACE(" --- start 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());
101 * \brief Return max number of nodes in a tree leaf
103 int HYDROData_QuadtreeNode::getMaxNbNodes() const
105 return ((Limit*) myLimit)->myMaxNbNodes;
109 * \brief Construct an empty HYDROData_QuadtreeNode used by HYDROData_Quadtree::buildChildren()
111 HYDROData_Quadtree* HYDROData_QuadtreeNode::newChild() const
113 return new HYDROData_QuadtreeNode();
117 * \brief Compute the first bounding box
119 * We take the max/min coord of the nodes
121 Bnd_B2d* HYDROData_QuadtreeNode::buildRootBox()
123 Bnd_B2d* box = new Bnd_B2d;
124 Nodes_3D::iterator it = myNodes->begin();
125 for (; it != myNodes->end(); it++)
127 const gp_XYZ* n1 = *it;
128 gp_XY p1(n1->X(), n1->Y());
131 if (myNodes->size() <= getMaxNbNodes())
138 * \brief Tells us if Node is inside the current box with the precision "precision"
140 * \param precision - The box is enlarged with this precision
141 * \retval bool - True if Node is in the box within precision
143 const bool HYDROData_QuadtreeNode::isInside(const gp_XY& p, const double precision)
146 return !(getBox()->IsOut(p));
147 Bnd_B2d BoxWithPrecision = *getBox();
148 BoxWithPrecision.Enlarge(precision);
149 return !BoxWithPrecision.IsOut(p);
153 * \brief Set the data of the children
154 * Shares the father's data with each of his child
156 void HYDROData_QuadtreeNode::buildChildrenData()
158 gp_XY min = getBox()->CornerMin();
159 gp_XY max = getBox()->CornerMax();
160 gp_XY mid = (min + max) / 2.;
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())
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);
171 it = myNodes->begin();
173 for (int i = 0; i < 4; i++)
175 HYDROData_QuadtreeNode* myChild = dynamic_cast<HYDROData_QuadtreeNode*>(myChildren[i]);
176 if (myChild->myNodes->size() <= getMaxNbNodes())
178 myChild->myIsLeaf = true;
179 //DEBTRACE("buildChildrenData leaf nbNodes "<< myChild->myNodes->size());
185 * \brief Return in Result a list of Nodes potentials to be near Node
187 * \param precision - precision used
188 * \param Result - list of Nodes potentials to be near Node
190 void HYDROData_QuadtreeNode::NodesAround(const gp_XY& Node,
191 list<const gp_XYZ*>* Result,
192 const double precision)
195 if (isInside(p, precision))
199 Result->insert(Result->end(), myNodes->begin(), myNodes->end());
200 //DEBTRACE("Leaf result "<< Result->size());
204 for (int i = 0; i < 4; i++)
206 HYDROData_QuadtreeNode* myChild = dynamic_cast<HYDROData_QuadtreeNode*>(myChildren[i]);
207 myChild->NodesAround(p, Result, precision);
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 !!!
220 bool HYDROData_QuadtreeNode::NodesAround(const gp_XY& node,
221 map<double, const gp_XYZ*>& dist2Nodes,
224 if (!dist2Nodes.empty())
225 precision = min(precision, sqrt(dist2Nodes.begin()->first));
226 else if (precision == 0.)
227 precision = maxSize() / 2;
229 if (isInside(node, precision))
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))
239 for (int i = 0; i < 4; i++)
241 if (((HYDROData_QuadtreeNode*) myChildren[i])->NodesAround(node, dist2Nodes, precision))
244 else if (NbNodes() > 0)
246 double minDist = precision * precision;
247 Nodes_3D::iterator nIt = myNodes->begin();
248 for (; nIt != myNodes->end(); ++nIt)
250 const gp_XYZ* p = *nIt;
251 gp_XY p2(p->X(), p->Y());
252 double dist2 = (node - p2).SquareModulus();
254 dist2Nodes.insert(make_pair(minDist = dist2, p));
256 // if ( dist2Nodes.size() > 1 ) // leave only closest node in dist2Nodes
257 // dist2Nodes.erase( ++dist2Nodes.begin(), dist2Nodes.end());
259 // true if an exact overlapping found
260 return (sqrt(minDist) <= precision * 1e-12);