From ba748cd3dd1769f019d6b4da525afebcb4794e99 Mon Sep 17 00:00:00 2001 From: Paul RASCLE Date: Wed, 4 Jun 2014 06:04:52 +0000 Subject: [PATCH] PR: quadtree --- src/HYDROData/CMakeLists.txt | 10 + src/HYDROData/HYDROData_Bathymetry.cxx | 340 +++++++++------ src/HYDROData/HYDROData_Bathymetry.h | 3 + src/HYDROData/HYDROData_CalculationCase.cxx | 15 + src/HYDROData/HYDROData_Octree.cxx | 71 ++++ src/HYDROData/HYDROData_Octree.hxx | 72 ++++ src/HYDROData/HYDROData_OctreeNode.cxx | 446 ++++++++++++++++++++ src/HYDROData/HYDROData_OctreeNode.hxx | 143 +++++++ src/HYDROData/HYDROData_Quadtree.cxx | 67 +++ src/HYDROData/HYDROData_Quadtree.hxx | 69 +++ src/HYDROData/HYDROData_QuadtreeNode.cxx | 264 ++++++++++++ src/HYDROData/HYDROData_QuadtreeNode.hxx | 122 ++++++ src/HYDROData/HYDROData_Tree.hxx | 264 ++++++++++++ src/HYDROData/HYDRO_trace.hxx | 13 + 14 files changed, 1769 insertions(+), 130 deletions(-) create mode 100644 src/HYDROData/HYDROData_Octree.cxx create mode 100644 src/HYDROData/HYDROData_Octree.hxx create mode 100644 src/HYDROData/HYDROData_OctreeNode.cxx create mode 100644 src/HYDROData/HYDROData_OctreeNode.hxx create mode 100644 src/HYDROData/HYDROData_Quadtree.cxx create mode 100644 src/HYDROData/HYDROData_Quadtree.hxx create mode 100644 src/HYDROData/HYDROData_QuadtreeNode.cxx create mode 100644 src/HYDROData/HYDROData_QuadtreeNode.hxx create mode 100644 src/HYDROData/HYDROData_Tree.hxx create mode 100644 src/HYDROData/HYDRO_trace.hxx diff --git a/src/HYDROData/CMakeLists.txt b/src/HYDROData/CMakeLists.txt index e50e8589..06b6ba09 100644 --- a/src/HYDROData/CMakeLists.txt +++ b/src/HYDROData/CMakeLists.txt @@ -1,6 +1,7 @@ #include(../../CMake/Common.cmake) set(PROJECT_HEADERS + HYDRO_trace.hxx HYDROData.h HYDROData_AltitudeObject.h HYDROData_Application.h @@ -44,6 +45,11 @@ set(PROJECT_HEADERS HYDROData_Transform.h HYDROData_VisualState.h HYDROData_Zone.h + HYDROData_Tree.hxx + HYDROData_Quadtree.hxx + HYDROData_QuadtreeNode.hxx + HYDROData_Octree.hxx + HYDROData_OctreeNode.hxx ) set(PROJECT_SOURCES @@ -89,6 +95,10 @@ set(PROJECT_SOURCES HYDROData_Transform.cxx HYDROData_VisualState.cxx HYDROData_Zone.cxx + HYDROData_Quadtree.cxx + HYDROData_QuadtreeNode.cxx + HYDROData_Octree.cxx + HYDROData_OctreeNode.cxx ) add_definitions( diff --git a/src/HYDROData/HYDROData_Bathymetry.cxx b/src/HYDROData/HYDROData_Bathymetry.cxx index 9bdfd1cf..4624bb8a 100644 --- a/src/HYDROData/HYDROData_Bathymetry.cxx +++ b/src/HYDROData/HYDROData_Bathymetry.cxx @@ -26,16 +26,33 @@ #include #endif +#define _DEVDEBUG_ +#include "HYDRO_trace.hxx" + IMPLEMENT_STANDARD_HANDLE(HYDROData_Bathymetry, HYDROData_IAltitudeObject) IMPLEMENT_STANDARD_RTTIEXT(HYDROData_Bathymetry, HYDROData_IAltitudeObject) +//HYDROData_QuadtreeNode* HYDROData_Bathymetry::myQuadtree = 0; +std::map HYDROData_Bathymetry::myQuadtrees; + HYDROData_Bathymetry::HYDROData_Bathymetry() : HYDROData_IAltitudeObject() { + //DEBTRACE("HYDROData_Bathymetry constructor start " << this); +// if (! myQuadtree) +// myQuadtree = new HYDROData_QuadtreeNode(0, 30, 5, 0.); + //DEBTRACE("HYDROData_Bathymetry constructor end " << this); } HYDROData_Bathymetry::~HYDROData_Bathymetry() { + //DEBTRACE("HYDROData_Bathymetry destructor start " << this); +// if (myQuadtree) +// delete myQuadtree; +// Nodes_3D::iterator it = myListOfNodes.begin(); +// for( ; it != myListOfNodes.end(); ++it) +// delete *it; +// myListOfNodes.clear(); } QStringList HYDROData_Bathymetry::DumpToPython( MapOfTreatedObjects& theTreatedObjects ) const @@ -109,14 +126,57 @@ HYDROData_Bathymetry::AltitudePoints HYDROData_Bathymetry::GetAltitudePoints() c return aPoints; } +HYDROData_QuadtreeNode* HYDROData_Bathymetry::GetQuadtreeNodes() const +{ + TDF_Label aLabel = myLab.FindChild(DataTag_AltitudePoints, false); + if (aLabel.IsNull()) + return 0; + int labkey = myLab.Tag(); + int altkey = aLabel.Tag(); + //DEBTRACE("GetQuadtreeNodes this labkey altkey "<isEmpty() ) + if (myQuadtrees.find(labkey) == myQuadtrees.end()) + { + DEBTRACE("GetQuadtreeNodes init " << this << " " << labkey); + HYDROData_QuadtreeNode* aQuadtree = new HYDROData_QuadtreeNode(0, 30, 5, 0.); + myQuadtrees[labkey] = aQuadtree; + TDF_Label aLabel = myLab.FindChild(DataTag_AltitudePoints, false); + if (aLabel.IsNull()) + return 0; + + Handle(TDataStd_RealArray) aCoordsArray; + if (!aLabel.FindAttribute(TDataStd_RealArray::GetID(), aCoordsArray)) + return 0; + + Nodes_3D* aListOfNodes = new Nodes_3D(); + + for (int i = aCoordsArray->Lower(), n = aCoordsArray->Upper(); i <= n;) + { + if (i + 3 > n + 1) + break; + + double x = aCoordsArray->Value(i++); + double y = aCoordsArray->Value(i++); + double z = aCoordsArray->Value(i++); + gp_XYZ* aPoint = new gp_XYZ(x, y, z); + aListOfNodes->push_back(aPoint); + } + DEBTRACE(" GetQuadtreeNodes call setNodesAndCompute"); + aQuadtree->setNodesAndCompute(aListOfNodes); + return aQuadtree; + } + else + return myQuadtrees[labkey]; +} + void HYDROData_Bathymetry::RemoveAltitudePoints() { - TDF_Label aLabel = myLab.FindChild( DataTag_AltitudePoints, false ); - if ( !aLabel.IsNull() ) - { - aLabel.ForgetAllAttributes(); - SetToUpdate( true ); - } + TDF_Label aLabel = myLab.FindChild(DataTag_AltitudePoints, false); + if (!aLabel.IsNull()) + { + aLabel.ForgetAllAttributes(); + SetToUpdate(true); + } } void interpolateAltitudeForPoints( const gp_XY& thePoint, @@ -172,140 +232,160 @@ void interpolateAltitudeForPoints( const gp_XY& th theResPoint.SetZ( aResVal ); } -double HYDROData_Bathymetry::GetAltitudeForPoint( const gp_XY& thePoint ) const +double HYDROData_Bathymetry::GetAltitudeForPoint(const gp_XY& thePoint) const { + //DEBTRACE("GetAltitudeForPoint p(" << thePoint.X() << ", " << thePoint.Y() << ")"); double anInvalidAltitude = GetInvalidAltitude(); double aResAltitude = anInvalidAltitude; - - AltitudePoints anAltitudePoints = GetAltitudePoints(); - if ( anAltitudePoints.IsEmpty() ) - return aResAltitude; - - QPolygonF aBoundingRect; - - // Boundary plane - // [ 0 (top-left) ] [ 1 (top-right) ] - // thePoint - // [ 2 (bot-left) ] [ 3 (bot-right) ] - AltitudePoint aBounds[ 4 ] = { AltitudePoint( -DBL_MAX, -DBL_MAX, anInvalidAltitude ), - AltitudePoint( DBL_MAX, -DBL_MAX, anInvalidAltitude ), - AltitudePoint( -DBL_MAX, DBL_MAX, anInvalidAltitude ), - AltitudePoint( DBL_MAX, DBL_MAX, anInvalidAltitude ) }; - AltitudePoints::Iterator anIter( anAltitudePoints ); - for ( ; anIter.More(); anIter.Next() ) - { - const AltitudePoint& aPoint = anIter.Value(); - - double aDeltaX = Abs( aPoint.X() ) - Abs( thePoint.X() ); - double aDeltaY = Abs( aPoint.Y() ) - Abs( thePoint.Y() ); - - if ( ValuesEquals( aDeltaX, 0.0 ) ) // Both left and right sides - { - if ( ValuesEquals( aDeltaY, 0.0 ) ) // Both top and bottom sides - { - aResAltitude = aPoint.Z(); - return aResAltitude; - } - else if ( aDeltaY < 0 ) // top side - { - // top border - if ( ValuesMoreEquals( aPoint.X(), aBounds[ 0 ].X() ) && ValuesMoreEquals( aPoint.Y(), aBounds[ 0 ].Y() ) ) - aBounds[ 0 ] = aPoint; - if ( ValuesLessEquals( aPoint.X(), aBounds[ 1 ].X() ) && ValuesMoreEquals( aPoint.Y(), aBounds[ 1 ].Y() ) ) - aBounds[ 1 ] = aPoint; - } - else - { - // bottom border - if ( ValuesMoreEquals( aPoint.X(), aBounds[ 2 ].X() ) && ValuesLessEquals( aPoint.Y(), aBounds[ 2 ].Y() ) ) - aBounds[ 2 ] = aPoint; - if ( ValuesLessEquals( aPoint.X(), aBounds[ 3 ].X() ) && ValuesLessEquals( aPoint.Y(), aBounds[ 3 ].Y() ) ) - aBounds[ 3 ] = aPoint; - } - } - else if ( aDeltaX < 0 ) // left side + HYDROData_QuadtreeNode* aQuadtree = GetQuadtreeNodes(); + if (!aQuadtree) { - if ( ValuesEquals( aDeltaY, 0.0 ) ) - { - // Left border - if ( ValuesMoreEquals( aPoint.X(), aBounds[ 0 ].X() ) && ValuesMoreEquals( aPoint.Y(), aBounds[ 0 ].Y() ) ) - aBounds[ 0 ] = aPoint; - if ( ValuesMoreEquals( aPoint.X(), aBounds[ 2 ].X() ) && ValuesLessEquals( aPoint.Y(), aBounds[ 2 ].Y() ) ) - aBounds[ 2 ] = aPoint; - } - else if ( aDeltaY < 0 ) - { - // top left corner - if ( ValuesMoreEquals( aPoint.X(), aBounds[ 0 ].X() ) && ValuesMoreEquals( aPoint.Y(), aBounds[ 0 ].Y() ) ) - aBounds[ 0 ] = aPoint; - } - else - { - // bottom left corner - if ( ValuesMoreEquals( aPoint.X(), aBounds[ 2 ].X() ) && ValuesLessEquals( aPoint.Y(), aBounds[ 2 ].Y() ) ) - aBounds[ 2 ] = aPoint; - } + DEBTRACE(" no Quadtree"); + return aResAltitude; } - else // right side + + std::map dist2nodes; + aQuadtree->NodesAround(thePoint, dist2nodes, 1.0); + if (dist2nodes.size()) { - if ( ValuesEquals( aDeltaY, 0.0 ) ) - { - // Right border - if ( ValuesLessEquals( aPoint.X(), aBounds[ 1 ].X() ) && ValuesMoreEquals( aPoint.Y(), aBounds[ 1 ].Y() ) ) - aBounds[ 1 ] = aPoint; - if ( ValuesLessEquals( aPoint.X(), aBounds[ 3 ].X() ) && ValuesLessEquals( aPoint.Y(), aBounds[ 3 ].Y() ) ) - aBounds[ 3 ] = aPoint; - } - else if ( aDeltaY < 0 ) - { - // top right corner - if ( ValuesLessEquals( aPoint.X(), aBounds[ 1 ].X() ) && ValuesMoreEquals( aPoint.Y(), aBounds[ 1 ].Y() ) ) - aBounds[ 1 ] = aPoint; - } - else - { - // bottom right corner - if ( ValuesLessEquals( aPoint.X(), aBounds[ 3 ].X() ) && ValuesLessEquals( aPoint.Y(), aBounds[ 3 ].Y() ) ) - aBounds[ 3 ] = aPoint; - } + std::map::const_iterator it = dist2nodes.begin(); + aResAltitude = it->second->Z(); + //DEBTRACE(" number of points found: " << dist2nodes.size() << " nearest z: " << aResAltitude); } - // Update bounding rectangle of our global grid - aBoundingRect << QPointF( aPoint.X(), aPoint.Y() ); - } - - const double LIMIT = 1E300; - if( fabs( aBounds[ 0 ].X() ) > LIMIT || fabs( aBounds[ 0 ].Y() ) > LIMIT || - fabs( aBounds[ 1 ].X() ) > LIMIT || fabs( aBounds[ 1 ].Y() ) > LIMIT || - fabs( aBounds[ 2 ].X() ) > LIMIT || fabs( aBounds[ 2 ].Y() ) > LIMIT || - fabs( aBounds[ 3 ].X() ) > LIMIT || fabs( aBounds[ 3 ].Y() ) > LIMIT ) - return anInvalidAltitude; - - - // Check if requested point is inside of our bounding rectangle - if ( !aBoundingRect.boundingRect().contains( thePoint.X(), thePoint.Y() ) ) - return aResAltitude; - - // Calculate result altitude for point - AltitudePoint aFirstPoint( aBounds[ 0 ] ), aSecPoint( aBounds[ 1 ] ); - - // At first we merge top and bottom borders - if ( aBounds[ 0 ].Y() != aBounds[ 2 ].Y() || aBounds[ 0 ].X() != aBounds[ 2 ].X() ) - interpolateAltitudeForPoints( thePoint, aBounds[ 0 ], aBounds[ 2 ], aFirstPoint, true ); - - if ( aBounds[ 1 ].Y() != aBounds[ 3 ].Y() || aBounds[ 1 ].X() != aBounds[ 3 ].X() ) - interpolateAltitudeForPoints( thePoint, aBounds[ 1 ], aBounds[ 3 ], aSecPoint, true ); - - AltitudePoint aResPoint( aFirstPoint ); - - // At last we merge left and right borders - if ( aFirstPoint.Y() != aSecPoint.Y() || aFirstPoint.X() != aSecPoint.X() ) - interpolateAltitudeForPoints( thePoint, aFirstPoint, aSecPoint, aResPoint, false ); - - aResAltitude = aResPoint.Z(); - return aResAltitude; + + +// AltitudePoints anAltitudePoints = GetAltitudePoints(); +// if ( anAltitudePoints.IsEmpty() ) +// return aResAltitude; +// +// QPolygonF aBoundingRect; +// +// // Boundary plane +// // [ 0 (top-left) ] [ 1 (top-right) ] +// // thePoint +// // [ 2 (bot-left) ] [ 3 (bot-right) ] +// AltitudePoint aBounds[ 4 ] = { AltitudePoint( -DBL_MAX, -DBL_MAX, anInvalidAltitude ), +// AltitudePoint( DBL_MAX, -DBL_MAX, anInvalidAltitude ), +// AltitudePoint( -DBL_MAX, DBL_MAX, anInvalidAltitude ), +// AltitudePoint( DBL_MAX, DBL_MAX, anInvalidAltitude ) }; +// +// AltitudePoints::Iterator anIter( anAltitudePoints ); +// for ( ; anIter.More(); anIter.Next() ) +// { +// const AltitudePoint& aPoint = anIter.Value(); +// +// double aDeltaX = Abs( aPoint.X() ) - Abs( thePoint.X() ); +// double aDeltaY = Abs( aPoint.Y() ) - Abs( thePoint.Y() ); +// +// if ( ValuesEquals( aDeltaX, 0.0 ) ) // Both left and right sides +// { +// if ( ValuesEquals( aDeltaY, 0.0 ) ) // Both top and bottom sides +// { +// aResAltitude = aPoint.Z(); +// return aResAltitude; +// } +// else if ( aDeltaY < 0 ) // top side +// { +// // top border +// if ( ValuesMoreEquals( aPoint.X(), aBounds[ 0 ].X() ) && ValuesMoreEquals( aPoint.Y(), aBounds[ 0 ].Y() ) ) +// aBounds[ 0 ] = aPoint; +// if ( ValuesLessEquals( aPoint.X(), aBounds[ 1 ].X() ) && ValuesMoreEquals( aPoint.Y(), aBounds[ 1 ].Y() ) ) +// aBounds[ 1 ] = aPoint; +// } +// else +// { +// // bottom border +// if ( ValuesMoreEquals( aPoint.X(), aBounds[ 2 ].X() ) && ValuesLessEquals( aPoint.Y(), aBounds[ 2 ].Y() ) ) +// aBounds[ 2 ] = aPoint; +// if ( ValuesLessEquals( aPoint.X(), aBounds[ 3 ].X() ) && ValuesLessEquals( aPoint.Y(), aBounds[ 3 ].Y() ) ) +// aBounds[ 3 ] = aPoint; +// } +// } +// else if ( aDeltaX < 0 ) // left side +// { +// if ( ValuesEquals( aDeltaY, 0.0 ) ) +// { +// // Left border +// if ( ValuesMoreEquals( aPoint.X(), aBounds[ 0 ].X() ) && ValuesMoreEquals( aPoint.Y(), aBounds[ 0 ].Y() ) ) +// aBounds[ 0 ] = aPoint; +// if ( ValuesMoreEquals( aPoint.X(), aBounds[ 2 ].X() ) && ValuesLessEquals( aPoint.Y(), aBounds[ 2 ].Y() ) ) +// aBounds[ 2 ] = aPoint; +// } +// else if ( aDeltaY < 0 ) +// { +// // top left corner +// if ( ValuesMoreEquals( aPoint.X(), aBounds[ 0 ].X() ) && ValuesMoreEquals( aPoint.Y(), aBounds[ 0 ].Y() ) ) +// aBounds[ 0 ] = aPoint; +// } +// else +// { +// // bottom left corner +// if ( ValuesMoreEquals( aPoint.X(), aBounds[ 2 ].X() ) && ValuesLessEquals( aPoint.Y(), aBounds[ 2 ].Y() ) ) +// aBounds[ 2 ] = aPoint; +// } +// } +// else // right side +// { +// if ( ValuesEquals( aDeltaY, 0.0 ) ) +// { +// // Right border +// if ( ValuesLessEquals( aPoint.X(), aBounds[ 1 ].X() ) && ValuesMoreEquals( aPoint.Y(), aBounds[ 1 ].Y() ) ) +// aBounds[ 1 ] = aPoint; +// if ( ValuesLessEquals( aPoint.X(), aBounds[ 3 ].X() ) && ValuesLessEquals( aPoint.Y(), aBounds[ 3 ].Y() ) ) +// aBounds[ 3 ] = aPoint; +// } +// else if ( aDeltaY < 0 ) +// { +// // top right corner +// if ( ValuesLessEquals( aPoint.X(), aBounds[ 1 ].X() ) && ValuesMoreEquals( aPoint.Y(), aBounds[ 1 ].Y() ) ) +// aBounds[ 1 ] = aPoint; +// } +// else +// { +// // bottom right corner +// if ( ValuesLessEquals( aPoint.X(), aBounds[ 3 ].X() ) && ValuesLessEquals( aPoint.Y(), aBounds[ 3 ].Y() ) ) +// aBounds[ 3 ] = aPoint; +// } +// } +// +// // Update bounding rectangle of our global grid +// aBoundingRect << QPointF( aPoint.X(), aPoint.Y() ); +// } +// +// const double LIMIT = 1E300; +// if( fabs( aBounds[ 0 ].X() ) > LIMIT || fabs( aBounds[ 0 ].Y() ) > LIMIT || +// fabs( aBounds[ 1 ].X() ) > LIMIT || fabs( aBounds[ 1 ].Y() ) > LIMIT || +// fabs( aBounds[ 2 ].X() ) > LIMIT || fabs( aBounds[ 2 ].Y() ) > LIMIT || +// fabs( aBounds[ 3 ].X() ) > LIMIT || fabs( aBounds[ 3 ].Y() ) > LIMIT ) +// return anInvalidAltitude; +// +// +// // Check if requested point is inside of our bounding rectangle +// if ( !aBoundingRect.boundingRect().contains( thePoint.X(), thePoint.Y() ) ) +// return aResAltitude; +// +// // Calculate result altitude for point +// AltitudePoint aFirstPoint( aBounds[ 0 ] ), aSecPoint( aBounds[ 1 ] ); +// +// // At first we merge top and bottom borders +// if ( aBounds[ 0 ].Y() != aBounds[ 2 ].Y() || aBounds[ 0 ].X() != aBounds[ 2 ].X() ) +// interpolateAltitudeForPoints( thePoint, aBounds[ 0 ], aBounds[ 2 ], aFirstPoint, true ); +// +// if ( aBounds[ 1 ].Y() != aBounds[ 3 ].Y() || aBounds[ 1 ].X() != aBounds[ 3 ].X() ) +// interpolateAltitudeForPoints( thePoint, aBounds[ 1 ], aBounds[ 3 ], aSecPoint, true ); +// +// AltitudePoint aResPoint( aFirstPoint ); +// +// // At last we merge left and right borders +// if ( aFirstPoint.Y() != aSecPoint.Y() || aFirstPoint.X() != aSecPoint.X() ) +// interpolateAltitudeForPoints( thePoint, aFirstPoint, aSecPoint, aResPoint, false ); +// +// aResAltitude = aResPoint.Z(); +// +// return aResAltitude; } void HYDROData_Bathymetry::SetFilePath( const TCollection_AsciiString& theFilePath ) diff --git a/src/HYDROData/HYDROData_Bathymetry.h b/src/HYDROData/HYDROData_Bathymetry.h index a5dfb35b..95af7420 100644 --- a/src/HYDROData/HYDROData_Bathymetry.h +++ b/src/HYDROData/HYDROData_Bathymetry.h @@ -3,6 +3,7 @@ #define HYDROData_Bathymetry_HeaderFile #include "HYDROData_IAltitudeObject.h" +#include "HYDROData_QuadtreeNode.hxx" class QFile; class gp_XYZ; @@ -64,6 +65,7 @@ public: * \return points list */ HYDRODATA_EXPORT virtual AltitudePoints GetAltitudePoints() const; + HYDRODATA_EXPORT virtual HYDROData_QuadtreeNode* GetQuadtreeNodes() const; /** * Remove all altitude points. @@ -121,6 +123,7 @@ private: */ bool importFromXYZFile( QFile& theFile, AltitudePoints& thePoints ) const; + static std::map myQuadtrees; protected: diff --git a/src/HYDROData/HYDROData_CalculationCase.cxx b/src/HYDROData/HYDROData_CalculationCase.cxx index 509c2c5f..dcc662d6 100644 --- a/src/HYDROData/HYDROData_CalculationCase.cxx +++ b/src/HYDROData/HYDROData_CalculationCase.cxx @@ -49,6 +49,9 @@ #define EXPORT_NAME "HYDRO_" + GetName() +#define _DEVDEBUG_ +#include "HYDRO_trace.hxx" + IMPLEMENT_STANDARD_HANDLE(HYDROData_CalculationCase, HYDROData_Entity) IMPLEMENT_STANDARD_RTTIEXT(HYDROData_CalculationCase, HYDROData_Entity) @@ -535,10 +538,20 @@ double HYDROData_CalculationCase::GetAltitudeForPoint( const gp_XY& Handle(HYDROData_Zone) aZone = GetZoneFromPoint( thePoint ); if ( !aZone.IsNull() ) { + //DEBTRACE("GetAltitudeForPoint Region " << theRegion->GetName().toStdString() << " Zone " << aZone->GetName().toStdString()); Handle(HYDROData_Region) aRefRegion = Handle(HYDROData_Region)::DownCast( aZone->GetFatherObject() ); if ( IsEqual( aRefRegion, theRegion ) ) aResAltitude = GetAltitudeForPoint( thePoint, aZone ); + else + { + DEBTRACE("GetAltitudeForPoint Region " << aRefRegion->GetName().toStdString() << " Zone " << aZone->GetName().toStdString() << " ---------------------------"); + aResAltitude = GetAltitudeForPoint( thePoint, aZone ); + } } + else + { + DEBTRACE(" --- GetAltitudeForPoint No Zone ---"); + } return aResAltitude; } @@ -546,6 +559,7 @@ double HYDROData_CalculationCase::GetAltitudeForPoint( const gp_XY& double HYDROData_CalculationCase::GetAltitudeForPoint( const gp_XY& thePoint, const Handle(HYDROData_Zone)& theZone ) const { + //DEBTRACE("GetAltitudeForPoint Zone " << theZone->GetName().toStdString()); double aResAltitude = HYDROData_IAltitudeObject::GetInvalidAltitude(); if ( theZone.IsNull() ) return aResAltitude; @@ -633,6 +647,7 @@ NCollection_Sequence HYDROData_CalculationCase::GetAltitudesForPoints( const NCollection_Sequence& thePoints, const Handle(HYDROData_Region)& theRegion ) const { + //DEBTRACE("HYDROData_CalculationCase::GetAltitudesForPoints " << theRegion->GetName().toStdString()); NCollection_Sequence aResSeq; for ( int i = 1, n = thePoints.Length(); i <= n; ++i ) diff --git a/src/HYDROData/HYDROData_Octree.cxx b/src/HYDROData/HYDROData_Octree.cxx new file mode 100644 index 00000000..2db14da9 --- /dev/null +++ b/src/HYDROData/HYDROData_Octree.cxx @@ -0,0 +1,71 @@ +// Copyright (C) 2007-2014 CEA/DEN, EDF R&D, OPEN CASCADE +// +// Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, +// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS +// +// 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. +// +// 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 +// + +// HYDRO HYDROData_Octree : Octree implementation (from SMESH module) +// File : HYDROData_Octree.cxx +// Created : Tue Jan 16 16:00:00 2007 +// Author : Nicolas Geimer & Aurélien Motteux(OCC) +// Module : HYDROData +// +#include "HYDROData_Octree.hxx" + +/*! + * Constructor. limit must be provided at tree root construction. + * limit will be deleted by HYDROData_Octree. + */ +HYDROData_Octree::HYDROData_Octree(HYDROData_TreeLimit* limit) : + TBaseTree(limit) +{ +} + +/*! + * \brief Allocate a bndbox according to childIndex. childIndex is zero based + */ +Bnd_B3d* HYDROData_Octree::newChildBox(int childIndex) const +{ + gp_XYZ min = getBox()->CornerMin(); + gp_XYZ max = getBox()->CornerMax(); + gp_XYZ HSize = (max - min) / 2.; + gp_XYZ childHsize = HSize / 2.; + + gp_XYZ minChild(min.X() + childIndex % 2 * HSize.X(), + min.Y() + (childIndex % 4) / 2 * HSize.Y(), + min.Z() + (childIndex >= 4) * HSize.Z()); + + return new Bnd_B3d(minChild + childHsize, childHsize); +} + +/*! + * \brief Compute the bigger dimension of my box + */ +double HYDROData_Octree::maxSize() const +{ + if (getBox() && !getBox()->IsVoid()) + { + gp_XYZ min = getBox()->CornerMin(); + gp_XYZ max = getBox()->CornerMax(); + gp_XYZ Size = (max - min); + double returnVal = (Size.X() > Size.Y()) ? Size.X() : Size.Y(); + return (returnVal > Size.Z()) ? returnVal : Size.Z(); + } + return 0.; +} diff --git a/src/HYDROData/HYDROData_Octree.hxx b/src/HYDROData/HYDROData_Octree.hxx new file mode 100644 index 00000000..1ad44c60 --- /dev/null +++ b/src/HYDROData/HYDROData_Octree.hxx @@ -0,0 +1,72 @@ +// Copyright (C) 2007-2014 CEA/DEN, EDF R&D, OPEN CASCADE +// +// Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, +// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS +// +// 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. +// +// 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 +// + +// HYDRO HYDROData_Octree : Octree implementation (from SMESH module) +// File : HYDROData_Octree.hxx +// Created : Tue Jan 16 16:00:00 2007 +// Author : Nicolas Geimer & Aurélien Motteux (OCC) +// Module : HYDROData +// +#ifndef _HYDROData_OCTREE_HXX_ +#define _HYDROData_OCTREE_HXX_ + +#include +#include + +#include "HYDROData_Tree.hxx" +#include + +//================================================================================ + +/*! + * \brief 3D tree of anything. + * Methods to implement in a descendant are: + * - Bnd_B3d* buildRootBox(); // box of the whole tree + * - descendant* newChild() const; // a new child instance + * - void buildChildrenData(); // Fill in data of the children + */ +class Standard_EXPORT HYDROData_Octree: public HYDROData_Tree +{ +public: + typedef HYDROData_Tree TBaseTree; + + //! Constructor. limit must be provided at tree root construction. + //! limit will be deleted by HYDROData_Octree + HYDROData_Octree(HYDROData_TreeLimit* limit = 0); + virtual ~HYDROData_Octree() {}; + + //! Compute the biggest dimension of my box + double maxSize() const; + + //! Return index of a child the given point is in + inline static int getChildIndex(double x, double y, double z, const gp_XYZ& boxMiddle) + { + return (x > boxMiddle.X()) + (y > boxMiddle.Y()) * 2 + (z > boxMiddle.Z()) * 4; + }; + +protected: + + //! Allocate a bndbox according to childIndex. childIndex is zero based + virtual Bnd_B3d* newChildBox(int childIndex) const; +}; + +#endif diff --git a/src/HYDROData/HYDROData_OctreeNode.cxx b/src/HYDROData/HYDROData_OctreeNode.cxx new file mode 100644 index 00000000..9be89118 --- /dev/null +++ b/src/HYDROData/HYDROData_OctreeNode.cxx @@ -0,0 +1,446 @@ +// Copyright (C) 2007-2014 CEA/DEN, EDF R&D, OPEN CASCADE +// +// Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, +// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS +// +// 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. +// +// 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 +// + +// HYDRO HYDROData_OctreeNode : Octree with Nodes set (from SMESH module) +// inherites class HYDROData_Octree +// File : HYDROData_OctreeNode.cxx +// Created : Tue Jan 16 16:00:00 2007 +// Author : Nicolas Geimer & Aurelien Motteux (OCC) +// Module : HYDROData +// +#include "HYDROData_OctreeNode.hxx" + +//#include "SMDS_SetIterator.hxx" +//#include "HYDROData_TypeDefs.hxx" +#include + +using namespace std; + +//=============================================================== +/*! + * \brief Constructor : Build all the Octree using Compute() + * \param theNodes - Set of nodes, the Octree is built from this nodes + * \param maxLevel - Maximum level for the leaves + * \param maxNbNodes - Maximum number of nodes, a leaf can contain + * \param minBoxSize - Minimal size of the Octree Box + */ +//================================================================ + +HYDROData_OctreeNode::HYDROData_OctreeNode (const Nodes3D& theNodes, const int maxLevel, + const int maxNbNodes , const double minBoxSize ) + :HYDROData_Octree( new Limit( maxLevel,minBoxSize,maxNbNodes)), + myNodes(theNodes) +{ + compute(); +} + +//================================================================================ +/*! + * \brief Constructor used to allocate a child + */ +//================================================================================ + +HYDROData_OctreeNode::HYDROData_OctreeNode ():HYDROData_Octree() +{ + myNodes.clear(); +} + +//================================================================================ +/*! + * \brief Return max number of nodes in a tree leaf + */ +//================================================================================ + +int HYDROData_OctreeNode::getMaxNbNodes() const +{ + return ((Limit*)myLimit)->myMaxNbNodes; +} + +//================================================================================== +/*! + * \brief Construct an empty HYDROData_OctreeNode used by HYDROData_Octree::buildChildren() + */ +//================================================================================== + +HYDROData_Octree* HYDROData_OctreeNode::newChild() const +{ + return new HYDROData_OctreeNode(); +} + +//====================================== +/*! + * \brief Compute the first bounding box + * + * We take the max/min coord of the nodes + */ +//====================================== + +Bnd_B3d* HYDROData_OctreeNode::buildRootBox() +{ + Bnd_B3d* box = new Bnd_B3d; + Nodes3D::iterator it = myNodes.begin(); + for (; it != myNodes.end(); it++) { + const gp_XYZ* n1 = *it; + gp_XYZ p1(*n1); + box->Add(p1); + } + if ( myNodes.size() <= getMaxNbNodes() ) + myIsLeaf = true; + + return box; +} + +//==================================================================================== +/*! + * \brief Tells us if Node is inside the current box with the precision "precision" + * \param Node - Node + * \param precision - The box is enlarged with this precision + * \retval bool - True if Node is in the box within precision + */ +//==================================================================================== + +const bool HYDROData_OctreeNode::isInside (const gp_XYZ& p, const double precision) +{ + if (precision <= 0.) + return !(getBox()->IsOut(p)); + Bnd_B3d BoxWithPrecision = *getBox(); + BoxWithPrecision.Enlarge(precision); + return ! BoxWithPrecision.IsOut(p); +} + +//================================================ +/*! + * \brief Set the data of the children + * Shares the father's data with each of his child + */ +//================================================ +void HYDROData_OctreeNode::buildChildrenData() +{ + gp_XYZ min = getBox()->CornerMin(); + gp_XYZ max = getBox()->CornerMax(); + gp_XYZ mid = (min + max)/2.; + + Nodes3D::iterator it = myNodes.begin(); + while (it != myNodes.end()) + { + const gp_XYZ* n1 = *it; + int ChildBoxNum = getChildIndex( n1->X(), n1->Y(), n1->Z(), mid ); + HYDROData_OctreeNode* myChild = dynamic_cast (myChildren[ChildBoxNum]); + myChild->myNodes.push_back(n1); + myNodes.erase( it ); + it = myNodes.begin(); + } + for (int i = 0; i < 8; i++) + { + HYDROData_OctreeNode* myChild = dynamic_cast (myChildren[i]); + if ( myChild->myNodes.size() <= getMaxNbNodes() ) + myChild->myIsLeaf = true; + } +} + +//=================================================================== +/*! + * \brief Return in Result a list of Nodes potentials to be near Node + * \param Node - Node + * \param precision - precision used + * \param Result - list of Nodes potentials to be near Node + */ +//==================================================================== +void HYDROData_OctreeNode::NodesAround (const Node3D* Node, + list* Result, + const double precision) +{ + gp_XYZ p(*Node); + if (isInside(p, precision)) + { + if (isLeaf()) + { + Result->insert(Result->end(), myNodes.begin(), myNodes.end()); + } + else + { + for (int i = 0; i < 8; i++) + { + HYDROData_OctreeNode* myChild = dynamic_cast (myChildren[i]); + myChild->NodesAround(Node, Result, precision); + } + } + } +} + +//================================================================================ +/*! + * \brief Return in dist2Nodes nodes mapped to their square distance from Node + * \param node - node to find nodes closest to + * \param dist2Nodes - map of found nodes and their distances + * \param precision - radius of a sphere to check nodes inside + * \retval bool - true if an exact overlapping found !!! + */ +//================================================================================ + +bool HYDROData_OctreeNode::NodesAround(const gp_XYZ &node, + map& dist2Nodes, + double precision) +{ + if ( !dist2Nodes.empty() ) + precision = min ( precision, sqrt( dist2Nodes.begin()->first )); + else if ( precision == 0. ) + precision = maxSize() / 2; + + if (isInside(node, precision)) + { + if (!isLeaf()) + { + // first check a child containing node + gp_XYZ mid = (getBox()->CornerMin() + getBox()->CornerMax()) / 2.; + int nodeChild = getChildIndex( node.X(), node.Y(), node.Z(), mid ); + if ( ((HYDROData_OctreeNode*) myChildren[nodeChild])->NodesAround(node, dist2Nodes, precision)) + return true; + + for (int i = 0; i < 8; i++) + if ( i != nodeChild ) + if (((HYDROData_OctreeNode*) myChildren[i])->NodesAround(node, dist2Nodes, precision)) + return true; + } + else if ( NbNodes() > 0 ) + { + double minDist = precision * precision; + Nodes3D::iterator nIt = myNodes.begin(); + for ( ; nIt != myNodes.end(); ++nIt ) + { + const gp_XYZ* p = *nIt; + gp_XYZ p2( *p ); + double dist2 = ( node - p2 ).SquareModulus(); + if ( dist2 < minDist ) + dist2Nodes.insert( make_pair( minDist = dist2, &p2 )); + } +// if ( dist2Nodes.size() > 1 ) // leave only closest node in dist2Nodes +// dist2Nodes.erase( ++dist2Nodes.begin(), dist2Nodes.end()); + + // true if an exact overlapping found + return ( sqrt( minDist ) <= precision * 1e-12 ); + } + } + return false; +} + +//============================= +/*! + * \brief Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance + * Search for all the nodes in theSetOfNodes + * Static Method : no need to create an HYDROData_OctreeNode + * \param theSetOfNodes - set of nodes we look at, modified during research + * \param theGroupsOfNodes - list of nodes closed to each other returned + * \param theTolerance - Precision used, default value is 0.00001 + * \param maxLevel - Maximum level for HYDROData_OctreeNode constructed, default value is -1 (Infinite) + * \param maxNbNodes - maximum Nodes in a Leaf of the HYDROData_OctreeNode constructed, default value is 5 + */ +//============================= +//void HYDROData_OctreeNode::FindCoincidentNodes (TIDSortedNodeSet& theSetOfNodes, +// list< list< const SMDS_MeshNode*> >* theGroupsOfNodes, +// const double theTolerance, +// const int maxLevel, +// const int maxNbNodes) +//{ +// // VSR 14/10/2011: limit max number of the levels in order to avoid endless recursing +// const int MAX_LEVEL = 10; +// HYDROData_OctreeNode theOctreeNode(theSetOfNodes, maxLevel < 0 ? MAX_LEVEL : maxLevel, maxNbNodes, theTolerance); +// theOctreeNode.FindCoincidentNodes (&theSetOfNodes, theTolerance, theGroupsOfNodes); +//} + +//============================= +/*! + * \brief Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance + * Search for all the nodes in theSetOfNodes + * \note The Octree itself is also modified by this method + * \param theSetOfNodes - set of nodes we look at, modified during research + * \param theTolerance - Precision used + * \param theGroupsOfNodes - list of nodes closed to each other returned + */ +//============================= +//void HYDROData_OctreeNode::FindCoincidentNodes ( TIDSortedNodeSet* theSetOfNodes, +// const double theTolerance, +// list< list< const SMDS_MeshNode*> >* theGroupsOfNodes) +//{ +// TIDSortedNodeSet::iterator it1 = theSetOfNodes->begin(); +// list::iterator it2; +// +// while (it1 != theSetOfNodes->end()) +// { +// const SMDS_MeshNode * n1 = *it1; +// +// list ListOfCoincidentNodes;// Initialize the lists via a declaration, it's enough +// +// list * groupPtr = 0; +// +// // Searching for Nodes around n1 and put them in ListofCoincidentNodes. +// // Found nodes are also erased from theSetOfNodes +// FindCoincidentNodes(n1, theSetOfNodes, &ListOfCoincidentNodes, theTolerance); +// +// // We build a list {n1 + his neigbours} and add this list in theGroupsOfNodes +// for (it2 = ListOfCoincidentNodes.begin(); it2 != ListOfCoincidentNodes.end(); it2++) +// { +// const SMDS_MeshNode* n2 = *it2; +// if ( !groupPtr ) +// { +// theGroupsOfNodes->push_back( list() ); +// groupPtr = & theGroupsOfNodes->back(); +// groupPtr->push_back( n1 ); +// } +// if (groupPtr->front() > n2) +// groupPtr->push_front( n2 ); +// else +// groupPtr->push_back( n2 ); +// } +// if (groupPtr != 0) +// groupPtr->sort(); +// +// theSetOfNodes->erase(it1); +// it1 = theSetOfNodes->begin(); +// } +//} + +//====================================================================================== +/*! + * \brief Return a list of nodes closed to Node and remove it from SetOfNodes + * \note The Octree itself is also modified by this method + * \param Node - We're searching the nodes next to him. + * \param SetOfNodes - set of nodes in which we erase the found nodes + * \param Result - list of nodes closed to Node + * \param precision - Precision used + */ +//====================================================================================== +//void HYDROData_OctreeNode::FindCoincidentNodes (const SMDS_MeshNode * Node, +// TIDSortedNodeSet* SetOfNodes, +// list* Result, +// const double precision) +//{ +// gp_Pnt p1 (Node->X(), Node->Y(), Node->Z()); +// bool isInsideBool = isInside( p1.XYZ(), precision ); +// +// if (isInsideBool) +// { +// // I'm only looking in the leaves, since all the nodes are stored there. +// if (isLeaf()) +// { +// TIDSortedNodeSet::iterator it = myNodes.begin(); +// const double tol2 = precision * precision; +// bool squareBool; +// +// while (it != myNodes.end()) +// { +// const SMDS_MeshNode* n2 = *it; +// squareBool = false; +// // We're only looking at nodes with a superior Id. +// // JFA: Why? +// //if (Node->GetID() < n2->GetID()) +// if (Node->GetID() != n2->GetID()) // JFA: for bug 0020185 +// { +// gp_Pnt p2 (n2->X(), n2->Y(), n2->Z()); +// // Distance optimized computation +// squareBool = (p1.SquareDistance( p2 ) <= tol2); +// +// // If n2 inside the SquareDistance, we add it in Result and remove it from SetOfNodes and myNodes +// if (squareBool) +// { +// Result->insert(Result->begin(), n2); +// SetOfNodes->erase( n2 ); +// myNodes.erase( *it++ ); // it++ goes forward and returns it's previous position +// } +// } +// if ( !squareBool ) +// it++; +// } +// if ( !Result->empty() ) +// myNodes.erase(Node); // JFA: for bug 0020185 +// } +// else +// { +// // If I'm not a leaf, I'm going to see my children ! +// for (int i = 0; i < 8; i++) +// { +// HYDROData_OctreeNode* myChild = dynamic_cast (myChildren[i]); +// myChild->FindCoincidentNodes(Node, SetOfNodes, Result, precision); +// } +// } +// } +//} + +//================================================================================ +/*! + * \brief Update data according to node movement + */ +//================================================================================ + +//void HYDROData_OctreeNode::UpdateByMoveNode( const Node3D* node, const gp_Pnt& toPnt ) +//{ +// if ( isLeaf() ) +// { +// Nodes3D::iterator pNode = myNodes.find( node ); +// bool nodeInMe = ( pNode != myNodes.end() ); +// +// bool pointInMe = isInside( toPnt.Coord(), 1e-10 ); +// +// if ( pointInMe != nodeInMe ) +// { +// if ( pointInMe ) +// myNodes.insert( node ); +// else +// myNodes.erase( node ); +// } +// } +// else if ( myChildren ) +// { +// gp_XYZ mid = (getBox()->CornerMin() + getBox()->CornerMax()) / 2.; +// int nodeChild = getChildIndex( node->X(), node->Y(), node->Z(), mid ); +// int pointChild = getChildIndex( toPnt.X(), toPnt.Y(), toPnt.Z(), mid ); +// if ( nodeChild != pointChild ) +// { +// ((HYDROData_OctreeNode*) myChildren[ nodeChild ])->UpdateByMoveNode( node, toPnt ); +// ((HYDROData_OctreeNode*) myChildren[ pointChild ])->UpdateByMoveNode( node, toPnt ); +// } +// } +//} + +//================================================================================ +/*! + * \brief Return iterator over children + */ +//================================================================================ +//HYDROData_OctreeNodeIteratorPtr HYDROData_OctreeNode::GetChildrenIterator() +//{ +// return HYDROData_OctreeNodeIteratorPtr +// ( new SMDS_SetIterator< HYDROData_OctreeNode*, TBaseTree** > +// ( myChildren, (( isLeaf() || !myChildren ) ? myChildren : &myChildren[ 8 ] ))); +//} + +//================================================================================ +/*! + * \brief Return nodes iterator + */ +//================================================================================ +//SMDS_NodeIteratorPtr HYDROData_OctreeNode::GetNodeIterator() +//{ +// return SMDS_NodeIteratorPtr +// ( new SMDS_SetIterator< SMDS_pNode, TIDSortedNodeSet::const_iterator > +// ( myNodes.begin(), myNodes.size() ? myNodes.end() : myNodes.begin())); +//} diff --git a/src/HYDROData/HYDROData_OctreeNode.hxx b/src/HYDROData/HYDROData_OctreeNode.hxx new file mode 100644 index 00000000..e18190cd --- /dev/null +++ b/src/HYDROData/HYDROData_OctreeNode.hxx @@ -0,0 +1,143 @@ +// Copyright (C) 2007-2014 CEA/DEN, EDF R&D, OPEN CASCADE +// +// Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, +// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS +// +// 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. +// +// 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 +// + +// HYDROData HYDROData_OctreeNode : Octree with Nodes set (from SMESH module) +// inherites global class HYDROData_Octree +// File : HYDROData_OctreeNode.hxx +// Created : Tue Jan 16 16:00:00 2007 +// Author : Nicolas Geimer & Aurelien Motteux (OCC) +// Module : HYDROData +// +#ifndef _HYDROData_OCTREENODE_HXX_ +#define _HYDROData_OCTREENODE_HXX_ + +#include +#include + +#include "HYDROData_Octree.hxx" +#include + +#include +#include +#include +#include + +//forward declaration +class HYDROData_OctreeNode; +class gp_XYZ; + +typedef gp_XYZ Node3D; +//typedef NCollection_Sequence Nodes3D; +typedef std::list Nodes3D; + +class Standard_EXPORT HYDROData_OctreeNode : public HYDROData_Octree { + +public: + + // Constructor + HYDROData_OctreeNode (const Nodes3D& theNodes, const int maxLevel = 8, + const int maxNbNodes = 5, const double minBoxSize = 0.); + +//============================= +/*! + * \brief Empty destructor + */ +//============================= + virtual ~HYDROData_OctreeNode () {}; + + // Tells us if Node is inside the current box with the precision "precision" + virtual const bool isInside(const gp_XYZ& p, const double precision = 0.); + + // Return in Result a list of Nodes potentials to be near Node + void NodesAround(const Node3D * Node, + std::list* Result, + const double precision = 0.); + + // Return in dist2Nodes nodes mapped to their square distance from Node + bool NodesAround(const gp_XYZ& node, + std::map& dist2Nodes, + double precision); + + // Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance + // Search for all the nodes in nodes +// void FindCoincidentNodes ( TIDSortedNodeSet* nodes, +// const double theTolerance, +// std::list< std::list< const Node3D*> >* theGroupsOfNodes); + + // Static method that return in theGroupsOfNodes a list of group of nodes close to each other within + // theTolerance search for all the nodes in nodes +// static void FindCoincidentNodes ( TIDSortedNodeSet& nodes, +// std::list< std::list< const Node3D*> >* theGroupsOfNodes, +// const double theTolerance = 0.00001, +// const int maxLevel = -1, +// const int maxNbNodes = 5); + /*! + * \brief Update data according to node movement + */ + void UpdateByMoveNode( const Node3D* node, const gp_Pnt& toPnt ); + /*! + * \brief Return iterator over children + */ +// HYDROData_OctreeNodeIteratorPtr GetChildrenIterator(); + /*! + * \brief Return nodes iterator + */ + //SMDS_NodeIteratorPtr GetNodeIterator(); + /*! + * \brief Return nb nodes in a tree + */ + int NbNodes() const { return myNodes.size(); } + +protected: + + struct Limit : public HYDROData_TreeLimit + { + int myMaxNbNodes; + Limit(int maxLevel, double minSize, int maxNbNodes) + :HYDROData_TreeLimit(maxLevel, minSize), myMaxNbNodes(maxNbNodes) {} + }; + + int getMaxNbNodes() const; + + HYDROData_OctreeNode(); + + // Compute the bounding box of the whole set of nodes myNodes + virtual Bnd_B3d* buildRootBox(); + + // Shares the father's data with each of his child + virtual void buildChildrenData(); + + // Construct an empty HYDROData_OctreeNode used by HYDROData_Octree::buildChildren() + virtual HYDROData_Octree* newChild() const; + +// // Return in result a list of nodes closed to Node and remove it from SetOfNodes +// void FindCoincidentNodes( const Node3D * Node, +// TIDSortedNodeSet* SetOfNodes, +// std::list* Result, +// const double precision); + + // The set of nodes inside the box of the Octree (Empty if Octree is not a leaf) + Nodes3D myNodes; + +}; + +#endif diff --git a/src/HYDROData/HYDROData_Quadtree.cxx b/src/HYDROData/HYDROData_Quadtree.cxx new file mode 100644 index 00000000..0ec9f1aa --- /dev/null +++ b/src/HYDROData/HYDROData_Quadtree.cxx @@ -0,0 +1,67 @@ +// Copyright (C) 2007-2014 CEA/DEN, EDF R&D, OPEN CASCADE +// +// Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, +// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS +// +// 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. +// +// 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 +// + +// HYDROData_Quadtree : Quadtree implementation (from SMESH module) +// File : HYDROData_Quadtree.cxx +// Module : HYDROData +// +#include "HYDROData_Quadtree.hxx" + +/*! + * Constructor. limit must be provided at tree root construction. + * limit will be deleted by HYDROData_Quadtree. + */ +HYDROData_Quadtree::HYDROData_Quadtree(HYDROData_TreeLimit* limit) : + TBaseTree(limit) +{ +} + +/*! + * \brief Allocate a bndbox according to childIndex. childIndex is zero based + */ +Bnd_B2d* HYDROData_Quadtree::newChildBox(int childIndex) const +{ + gp_XY ming = getBox()->CornerMin(); + gp_XY maxg = getBox()->CornerMax(); + gp_XY HSize = (maxg - ming) / 2.; + gp_XY childHsize = HSize / 2.; + + gp_XY minChild(ming.X() + childIndex % 2 * HSize.X(), ming.Y() + (childIndex > 1) * HSize.Y()); + + return new Bnd_B2d(minChild + childHsize, childHsize); +} + +/*! + * \brief Compute the biggest dimension of my box + */ +double HYDROData_Quadtree::maxSize() const +{ + if (getBox() && !getBox()->IsVoid()) + { + gp_XY ming = getBox()->CornerMin(); + gp_XY maxg = getBox()->CornerMax(); + gp_XY Size = (maxg - ming); + double returnVal = (Size.X() > Size.Y()) ? Size.X() : Size.Y(); + return returnVal; + } + return 0.; +} diff --git a/src/HYDROData/HYDROData_Quadtree.hxx b/src/HYDROData/HYDROData_Quadtree.hxx new file mode 100644 index 00000000..ac42cb82 --- /dev/null +++ b/src/HYDROData/HYDROData_Quadtree.hxx @@ -0,0 +1,69 @@ +// Copyright (C) 2007-2014 CEA/DEN, EDF R&D, OPEN CASCADE +// +// Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, +// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS +// +// 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. +// +// 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 +// + +// HYDROData_Quadtree : Quadtree implementation (from SMESH module) +// File : HYDROData_Quadtree.hxx +// Module : HYDROData +// +#ifndef _HYDROData_Quadtree_HXX_ +#define _HYDROData_Quadtree_HXX_ + +#include +#include + +#include "HYDROData_Tree.hxx" +#include + +//================================================================================ + +/*! + * \brief 2D tree of anything. + * Methods to implement in a descendant are: + * - Bnd_B2d* buildRootBox(); // box of the whole tree + * - descendant* newChild() const; // a new child instance + * - void buildChildrenData(); // Fill in data of the children + */ +class Standard_EXPORT HYDROData_Quadtree: public HYDROData_Tree +{ +public: + typedef HYDROData_Tree TBaseTree; + + //! Constructor. limit must be provided at tree root construction. + //! limit will be deleted by HYDROData_Quadtree + HYDROData_Quadtree(HYDROData_TreeLimit* limit = 0); + + //! Compute the biggest dimension of my box + double maxSize() const; + + //! Return index of a child the given point is in + inline int getChildIndex(double x, double y, const gp_XY& boxMiddle) const + { + return (x > boxMiddle.X()) + (y > boxMiddle.Y()) * 2; + }; + +protected: + + //! Allocate a bndbox according to childIndex. childIndex is zero based + virtual Bnd_B2d* newChildBox(int childIndex) const; +}; + +#endif diff --git a/src/HYDROData/HYDROData_QuadtreeNode.cxx b/src/HYDROData/HYDROData_QuadtreeNode.cxx new file mode 100644 index 00000000..64d3ecb0 --- /dev/null +++ b/src/HYDROData/HYDROData_QuadtreeNode.cxx @@ -0,0 +1,264 @@ +// Copyright (C) 2007-2014 CEA/DEN, EDF R&D, OPEN CASCADE +// +// Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, +// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS +// +// 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. +// +// 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 +// + +// HYDRO HYDROData_QuadtreeNode : Quadtree with Nodes set (from SMESH module) +// inherites class HYDROData_Quadtree +// File : HYDROData_QuadtreeNode.cxx +// Created : Tue Jan 16 16:00:00 2007 +// Author : Nicolas Geimer & Aurelien Motteux (OCC) +// Module : HYDROData +// +#include "HYDROData_QuadtreeNode.hxx" + +#include + +#define _DEVDEBUG_ +#include "HYDRO_trace.hxx" + +using namespace std; + +/*! + * \brief Constructor : Build all the Quadtree using Compute() + * \param theNodes - Set of nodes, the Quadtree is built from this nodes + * \param maxLevel - Maximum level for the leaves + * \param maxNbNodes - Maximum number of nodes, a leaf can contain + * \param minBoxSize - Minimal size of the Quadtree Box + */ +HYDROData_QuadtreeNode::HYDROData_QuadtreeNode(Nodes_3D* theNodes, + const int maxLevel, + const int maxNbNodes, + const double minBoxSize) : + HYDROData_Quadtree(new Limit(maxLevel, minBoxSize, maxNbNodes)), myNodes(theNodes) +{ + DEBTRACE("---------------------------- HYDROData_QuadtreeNode root constructor"); + if (myNodes) + { + DEBTRACE(" --- start compute"); + compute(); + DEBTRACE(" --- end compute"); + } +} + +/*! + * \brief Constructor used to allocate a child + */ +HYDROData_QuadtreeNode::HYDROData_QuadtreeNode() : + HYDROData_Quadtree() +{ + if (myNodes == 0) + myNodes = new Nodes_3D(); +} + +/*! + * \brief virtual destructor: deletes myNodes + */ +HYDROData_QuadtreeNode::~HYDROData_QuadtreeNode() +{ + if (myNodes) + { + delete myNodes; + myNodes = 0; + } +} + +/*! + * \brief Set the nodes and compute the quadtree, + * when the nodes are not given to the public constructor (delayed compute) + */ +void HYDROData_QuadtreeNode::setNodesAndCompute(Nodes_3D* theNodes) +{ + myNodes = theNodes; + if (myNodes) + { + DEBTRACE(" --- start compute"); + compute(); + DEBTRACE(" --- end compute : children & height " << this->nbChildren() << " " << this->getHeight()); + DEBTRACE("Bounding box min: " << this->myBox->CornerMin().X() << " " << this->myBox->CornerMin().Y()); + DEBTRACE("Bounding box max: " << this->myBox->CornerMax().X() << " " << this->myBox->CornerMax().Y()); + } +} + +/*! + * \brief Return max number of nodes in a tree leaf + */ +int HYDROData_QuadtreeNode::getMaxNbNodes() const +{ + return ((Limit*) myLimit)->myMaxNbNodes; +} + +/*! + * \brief Construct an empty HYDROData_QuadtreeNode used by HYDROData_Quadtree::buildChildren() + */ +HYDROData_Quadtree* HYDROData_QuadtreeNode::newChild() const +{ + return new HYDROData_QuadtreeNode(); +} + +/*! + * \brief Compute the first bounding box + * + * We take the max/min coord of the nodes + */ +Bnd_B2d* HYDROData_QuadtreeNode::buildRootBox() +{ + Bnd_B2d* box = new Bnd_B2d; + Nodes_3D::iterator it = myNodes->begin(); + for (; it != myNodes->end(); it++) + { + const gp_XYZ* n1 = *it; + gp_XY p1(n1->X(), n1->Y()); + box->Add(p1); + } + if (myNodes->size() <= getMaxNbNodes()) + myIsLeaf = true; + + return box; +} + +/*! + * \brief Tells us if Node is inside the current box with the precision "precision" + * \param Node - Node + * \param precision - The box is enlarged with this precision + * \retval bool - True if Node is in the box within precision + */ +const bool HYDROData_QuadtreeNode::isInside(const gp_XY& p, const double precision) +{ + if (precision <= 0.) + return !(getBox()->IsOut(p)); + Bnd_B2d BoxWithPrecision = *getBox(); + BoxWithPrecision.Enlarge(precision); + return !BoxWithPrecision.IsOut(p); +} + +/*! + * \brief Set the data of the children + * Shares the father's data with each of his child + */ +void HYDROData_QuadtreeNode::buildChildrenData() +{ + gp_XY min = getBox()->CornerMin(); + gp_XY max = getBox()->CornerMax(); + gp_XY mid = (min + max) / 2.; + + //DEBTRACE("buildChildrenData level, min, max, nbNodes "<size()); + Nodes_3D::iterator it = myNodes->begin(); + while (it != myNodes->end()) + { + gp_XYZ* n1 = *it; + int ChildBoxNum = getChildIndex(n1->X(), n1->Y(), mid); + HYDROData_QuadtreeNode* myChild = dynamic_cast(myChildren[ChildBoxNum]); + myChild->myNodes->push_back(n1); + myNodes->erase(it); + it = myNodes->begin(); + } + for (int i = 0; i < 4; i++) + { + HYDROData_QuadtreeNode* myChild = dynamic_cast(myChildren[i]); + if (myChild->myNodes->size() <= getMaxNbNodes()) + { + myChild->myIsLeaf = true; + //DEBTRACE("buildChildrenData leaf nbNodes "<< myChild->myNodes->size()); + } + } +} + +/*! + * \brief Return in Result a list of Nodes potentials to be near Node + * \param Node - Node + * \param precision - precision used + * \param Result - list of Nodes potentials to be near Node + */ +void HYDROData_QuadtreeNode::NodesAround(const gp_XY& Node, + list* Result, + const double precision) +{ + gp_XY p(Node); + if (isInside(p, precision)) + { + if (isLeaf()) + { + Result->insert(Result->end(), myNodes->begin(), myNodes->end()); + //DEBTRACE("Leaf result "<< Result->size()); + } + else + { + for (int i = 0; i < 4; i++) + { + HYDROData_QuadtreeNode* myChild = dynamic_cast(myChildren[i]); + myChild->NodesAround(p, Result, precision); + } + } + } +} + +/*! + * \brief Return in dist2Nodes nodes mapped to their square distance from Node + * \param node - node to find nodes closest to + * \param dist2Nodes - map of found nodes and their distances + * \param precision - radius of a sphere to check nodes inside + * \retval bool - true if an exact overlapping found !!! + */ +bool HYDROData_QuadtreeNode::NodesAround(const gp_XY& node, + map& dist2Nodes, + double precision) +{ + if (!dist2Nodes.empty()) + precision = min(precision, sqrt(dist2Nodes.begin()->first)); + else if (precision == 0.) + precision = maxSize() / 2; + + if (isInside(node, precision)) + { + if (!isLeaf()) + { + // first check a child containing node + gp_XY mid = (getBox()->CornerMin() + getBox()->CornerMax()) / 2.; + int nodeChild = getChildIndex(node.X(), node.Y(), mid); + if (((HYDROData_QuadtreeNode*) myChildren[nodeChild])->NodesAround(node, dist2Nodes, precision)) + return true; + + for (int i = 0; i < 4; i++) + if (i != nodeChild) + if (((HYDROData_QuadtreeNode*) myChildren[i])->NodesAround(node, dist2Nodes, precision)) + return true; + } + else if (NbNodes() > 0) + { + double minDist = precision * precision; + Nodes_3D::iterator nIt = myNodes->begin(); + for (; nIt != myNodes->end(); ++nIt) + { + const gp_XYZ* p = *nIt; + gp_XY p2(p->X(), p->Y()); + double dist2 = (node - p2).SquareModulus(); + if (dist2 < minDist) + dist2Nodes.insert(make_pair(minDist = dist2, p)); + } +// if ( dist2Nodes.size() > 1 ) // leave only closest node in dist2Nodes +// dist2Nodes.erase( ++dist2Nodes.begin(), dist2Nodes.end()); + +// true if an exact overlapping found + return (sqrt(minDist) <= precision * 1e-12); + } + } + return false; +} diff --git a/src/HYDROData/HYDROData_QuadtreeNode.hxx b/src/HYDROData/HYDROData_QuadtreeNode.hxx new file mode 100644 index 00000000..9dfe0a07 --- /dev/null +++ b/src/HYDROData/HYDROData_QuadtreeNode.hxx @@ -0,0 +1,122 @@ +// Copyright (C) 2007-2014 CEA/DEN, EDF R&D, OPEN CASCADE +// +// Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, +// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS +// +// 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. +// +// 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 +// + +// HYDROData HYDROData_QuadtreeNode : Quadtree with Nodes set (from SMESH module) +// inherits global class HYDROData_Quadtree +// File : HYDROData_QuadtreeNode.hxx +// Created : Tue Jan 16 16:00:00 2007 +// Author : Nicolas Geimer & Aurelien Motteux (OCC) +// Module : HYDROData +// +#ifndef _HYDROData_QUADTREENODE_HXX_ +#define _HYDROData_QUADTREENODE_HXX_ + +#include +#include + +#include "HYDROData_Quadtree.hxx" +#include + +#include +#include +#include +#include + +//forward declaration +class HYDROData_QuadtreeNode; +class gp_XY; +class gp_XYZ; + +typedef std::list Nodes_3D; + +class Standard_EXPORT HYDROData_QuadtreeNode: public HYDROData_Quadtree +{ + +public: + + //! public constructor: when theNodes is non null, compute the quadtree + HYDROData_QuadtreeNode(Nodes_3D* theNodes, + const int maxLevel = 8, + const int maxNbNodes = 5, + const double minBoxSize = 0.); + + //! destructor + virtual ~HYDROData_QuadtreeNode(); + + //! tu use when no nodes where given to the public constructor + virtual void setNodesAndCompute(Nodes_3D* theNodes); + + //! Tells us if Node is inside the current box with the precision "precision" + virtual const bool isInside(const gp_XY& p, const double precision = 0.); + + //! Return in Result a list of Nodes potentials to be near Node + void NodesAround(const gp_XY& Node, + std::list* Result, + const double precision = 0.); + + //! Return in dist2Nodes nodes mapped to their square distance from Node + bool NodesAround(const gp_XY& node, + std::map& dist2Nodes, + double precision); + + //! Update data according to node movement + void UpdateByMoveNode(const gp_XYZ* node, const gp_Pnt& toPnt); + + //! Return nb nodes in a tree + int NbNodes() const + { + if (myNodes) + return myNodes->size(); + else + return 0; + } + + //! tells us if the tree as already bin computed + bool isEmpty() const { return myChildren == 0; } + +protected: + + struct Limit: public HYDROData_TreeLimit + { + int myMaxNbNodes; + Limit(int maxLevel, double minSize, int maxNbNodes) : + HYDROData_TreeLimit(maxLevel, minSize), myMaxNbNodes(maxNbNodes) {} + }; + + int getMaxNbNodes() const; + + HYDROData_QuadtreeNode(); + + //! Compute the bounding box of the whole set of nodes myNodes + virtual Bnd_B2d* buildRootBox(); + + //! Shares the father's data with each of his child + virtual void buildChildrenData(); + + //! Construct an empty HYDROData_QuadtreeNode used by HYDROData_Quadtree::buildChildren() + virtual HYDROData_Quadtree* newChild() const; + + //! The set of nodes inside the box of the Quadtree (Empty if Quadtree is not a leaf) + Nodes_3D* myNodes; +}; + +#endif diff --git a/src/HYDROData/HYDROData_Tree.hxx b/src/HYDROData/HYDROData_Tree.hxx new file mode 100644 index 00000000..c946caab --- /dev/null +++ b/src/HYDROData/HYDROData_Tree.hxx @@ -0,0 +1,264 @@ +// Copyright (C) 2007-2014 CEA/DEN, EDF R&D, OPEN CASCADE +// +// Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, +// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS +// +// 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. +// +// 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 +// + +// HYDRO HYDROData_Tree : tree implementation (from SMESH module) +// File : HYDROData_Tree.hxx +// Created : Tue Jan 16 16:00:00 2007 +// Author : Nicolas Geimer & Aurélien Motteux (OCC) +// Module : HYDRO +// +#ifndef _HYDROData_Tree_HXX_ +#define _HYDROData_Tree_HXX_ + +//================================================================================ + +//! Data limiting the tree height +struct HYDROData_TreeLimit +{ + int myMaxLevel; //! 8^8 = 16777216 terminal trees at most + * minSize -> 0 : box size not checked + */ + HYDROData_TreeLimit(int maxLevel = 8, double minSize = 0.) : + myMaxLevel(maxLevel), myMinBoxSize(minSize) + { + } + + virtual ~HYDROData_TreeLimit() + { + } //!< virtual destructor can be inherited +}; + +//================================================================================ + +/*! + * \brief Base class for 2D and 3D trees + */ +template +class HYDROData_Tree +{ +public: + + typedef BND_BOX box_type; + + //! Constructor. limit must be provided at tree root construction. + //! limit will be deleted by HYDROData_Tree + HYDROData_Tree(HYDROData_TreeLimit* limit = 0); + + //! Destructor + virtual ~HYDROData_Tree(); + + //! Compute the Tree. Must be called by constructor of inheriting class + void compute(); + + //! Tell if Tree is a leaf or not. + //! An inheriting class can influence it via myIsLeaf protected field + bool isLeaf() const; + + //! Return its level + int level() const + { + return myLevel; + } + + //! Return Bounding Box of the Tree + const box_type* getBox() const + { + return myBox; + } + + //! Return height of the tree, full or from this level to top leaf + int getHeight(const bool full = true) const; + + static int nbChildren() + { + return NB_CHILDREN; + } + + //! Compute the biggest dimension of my box + virtual double maxSize() const = 0; + +protected: + //! Return box of the whole tree + virtual box_type* buildRootBox() = 0; + + //! Allocate a child + virtual HYDROData_Tree* newChild() const = 0; + + //! Allocate a bndbox according to childIndex. childIndex is zero based + virtual box_type* newChildBox(int childIndex) const = 0; + + //! Fill in data of the children + virtual void buildChildrenData() = 0; + + //! Build the children recursively + void buildChildren(); + + // --- members + + HYDROData_Tree** myChildren; //!< Array of children + + HYDROData_Tree* myFather; //!< Point the father, NULL for the level 0 + + const HYDROData_TreeLimit* myLimit; //!< Tree limit + + box_type* myBox; //!< Bounding box of a tree + + int myLevel; //!< Level of the Tree + + bool myIsLeaf; //!< Tell us if the Tree is a leaf or not +}; + +/*! + * Constructor. limit must be provided at tree root construction. + * limit will be deleted by HYDROData_Tree. + */ +template +HYDROData_Tree::HYDROData_Tree(HYDROData_TreeLimit* limit) : + myChildren(0), myFather(0), myLimit(limit), myBox(0), myLevel(0), myIsLeaf(false) +{ + //if ( !myLimit ) myLimit = new HYDROData_TreeLimit(); +} + +/*! + * \brief Compute the Tree + */ +template +void HYDROData_Tree::compute() +{ + if (myLevel == 0) + { + if (!myLimit) + myLimit = new HYDROData_TreeLimit(); + myBox = buildRootBox(); + if (myLimit->myMinBoxSize > 0. && maxSize() <= myLimit->myMinBoxSize) + myIsLeaf = true; + else + buildChildren(); + } +} + +/*! + * \brief HYDROData_Tree Destructor + */ +template +HYDROData_Tree::~HYDROData_Tree() +{ + if (myChildren) + { + if (!isLeaf()) + { + for (int i = 0; i < NB_CHILDREN; i++) + delete myChildren[i]; + delete[] myChildren; + myChildren = 0; + } + } + if (myBox) + delete myBox; + myBox = 0; + if (level() == 0) + delete myLimit; + myLimit = 0; +} + +/*! + * \brief Build the children boxes and call buildChildrenData() + */ +template +void HYDROData_Tree::buildChildren() +{ + if (isLeaf()) + return; + + myChildren = new HYDROData_Tree*[NB_CHILDREN]; + + // get the whole model size + double rootSize = 0; + { + HYDROData_Tree* root = this; + while (root->myLevel > 0) + root = root->myFather; + rootSize = root->maxSize(); + } + for (int i = 0; i < NB_CHILDREN; i++) + { + // The child is of the same type than its father (For instance, a HYDROData_OctreeNode) + // We allocate the memory we need for the child + myChildren[i] = newChild(); + // and we assign to him its box. + myChildren[i]->myFather = this; + if (myChildren[i]->myLimit) + delete myChildren[i]->myLimit; + myChildren[i]->myLimit = myLimit; + myChildren[i]->myLevel = myLevel + 1; + myChildren[i]->myBox = newChildBox(i); + myChildren[i]->myBox->Enlarge(rootSize * 1e-10); + if (myLimit->myMinBoxSize > 0. && myChildren[i]->maxSize() <= myLimit->myMinBoxSize) + myChildren[i]->myIsLeaf = true; + } + + // --- After building the NB_CHILDREN boxes, we put the data into the children. + buildChildrenData(); + + // --- After we pass to the next level of the Tree + for (int i = 0; i < NB_CHILDREN; i++) + myChildren[i]->buildChildren(); +} + +/*! + * \brief Tell if Tree is a leaf or not + * An inheriting class can influence it via myIsLeaf protected field + */ +template +bool HYDROData_Tree::isLeaf() const +{ + return myIsLeaf || ((myLimit->myMaxLevel > 0) ? (level() >= myLimit->myMaxLevel) : false); +} + +/*! + * \brief Return height of the tree, full or from this level to top leaf + */ +template +int HYDROData_Tree::getHeight(const bool full) const +{ + if (full && myFather) + return myFather->getHeight(true); + + if (isLeaf()) + return 1; + + int heigth = 0; + for (int i = 0; i < NB_CHILDREN; i++) + { + int h = myChildren[i]->getHeight(false); + if (h > heigth) + heigth = h; + } + return heigth + 1; +} + +#endif diff --git a/src/HYDROData/HYDRO_trace.hxx b/src/HYDROData/HYDRO_trace.hxx new file mode 100644 index 00000000..55f08176 --- /dev/null +++ b/src/HYDROData/HYDRO_trace.hxx @@ -0,0 +1,13 @@ +#ifndef __HYDROTRACE_HXX__ +#define __HYDROTRACE_HXX__ + +#include +#include + +#ifdef _DEVDEBUG_ +#define DEBTRACE(msg) {std::cerr<