]> SALOME platform Git repositories - modules/hydro.git/blob - src/HYDROData/HYDROData_QuadtreeNode.cxx
Salome HOME
Merge branch 'BR_H2018_2' of https://codev-tuleap.cea.fr/plugins/git/salome/hydro...
[modules/hydro.git] / 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 }