src/GeomAlgoAPI/GeomAlgoAPI_SortListOfShapes.cpp

   1 // Copyright (C) 2017  CEA/DEN, EDF R&D
   2 //
   3 // This library is free software; you can redistribute it and/or
   4 // modify it under the terms of the GNU Lesser General Public
   5 // License as published by the Free Software Foundation; either
   6 // version 2.1 of the License, or (at your option) any later version.
   7 //
   8 // This library is distributed in the hope that it will be useful,
   9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11 // Lesser General Public License for more details.
  12 //
  13 // You should have received a copy of the GNU Lesser General Public
  14 // License along with this library; if not, write to the Free Software
  15 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  16 //
  17 // See http://www.salome-platform.org/ or
  18 // email : webmaster.salome@opencascade.com<mailto:webmaster.salome@opencascade.com>
  19 //
  20
  21 #include "GeomAlgoAPI_SortListOfShapes.h"
  22
  23 #include <Bnd_Box.hxx>
  24 #include <Bnd_Box2d.hxx>
  25 #include <BRep_Tool.hxx>
  26 #include <BRepBndLib.hxx>
  27 #include <BRepTools.hxx>
  28 #include <gp_Pnt.hxx>
  29 #include <Precision.hxx>
  30 #include <TopoDS.hxx>
  31 #include <TopoDS_Edge.hxx>
  32 #include <TopoDS_Face.hxx>
  33
  34 #include <algorithm>
  35 #include <map>
  36
  37 class CompareShapes
  38 {
  39   std::map<TopoDS_TShape*, Bnd_Box> myShapes;
  40   std::map<TopoDS_TShape*, Bnd_Box2d> myUVBounds;
  41
  42   bool compareEdges(const GeomShapePtr& theLHS, const GeomShapePtr& theRHS)
  43   {
  44     const TopoDS_Edge& aLHSEdge = TopoDS::Edge(theLHS->impl<TopoDS_Shape>());
  45     const TopoDS_Edge& aRHSEdge = TopoDS::Edge(theRHS->impl<TopoDS_Shape>());
  46
  47     double aLF, aLE, aRF, aRE;
  48     Handle(Geom_Curve) aLHSCurve = BRep_Tool::Curve(aLHSEdge, aLF, aLE);
  49     Handle(Geom_Curve) aRHSCurve = BRep_Tool::Curve(aRHSEdge, aRF, aRE);
  50
  51     if (aLHSCurve == aRHSCurve) {
  52       // compare by first parameter
  53       if (isLessWithTol(aLF, aRF, Precision::PConfusion()))
  54         return true;
  55       else if (isLessWithTol(aRF, aLF, Precision::PConfusion()))
  56         return false;
  57       // compare by last parameter
  58       return isLessWithTol(aLE, aRE, Precision::PConfusion());
  59     }
  60     // different underlying curves => compare bounding boxe
  61     return compareByBoundingBox(theLHS, theRHS);
  62   }
  63
  64   bool compareFaces(const GeomShapePtr& theLHS, const GeomShapePtr& theRHS)
  65   {
  66     const TopoDS_Face& aLHSFace = TopoDS::Face(theLHS->impl<TopoDS_Shape>());
  67     const TopoDS_Face& aRHSFace = TopoDS::Face(theRHS->impl<TopoDS_Shape>());
  68
  69     Handle(Geom_Surface) aLHSSurf = BRep_Tool::Surface(aLHSFace);
  70     Handle(Geom_Surface) aRHSSurf = BRep_Tool::Surface(aRHSFace);
  71
  72     if (aLHSSurf == aRHSSurf) {
  73       // compare parametric space for faces on the same surface
  74       Bnd_Box2d aLHSBox = boundingBoxUV(aLHSFace);
  75       Bnd_Box2d aRHSBox = boundingBoxUV(aRHSFace);
  76
  77       double aLHSBB[4], aRHSBB[4];
  78       aLHSBox.Get(aLHSBB[0], aLHSBB[1], aLHSBB[2], aLHSBB[3]);
  79       aRHSBox.Get(aRHSBB[0], aRHSBB[1], aRHSBB[2], aRHSBB[3]);
  80       for (int anIndex = 0; anIndex < 4; ++anIndex) {
  81         if (isLessWithTol(aLHSBB[anIndex], aRHSBB[anIndex], Precision::PConfusion()))
  82           return true;
  83         else if (isLessWithTol(aRHSBB[anIndex], aLHSBB[anIndex], Precision::PConfusion()))
  84           return false;
  85       }
  86       // equal parametric boxes
  87       return false;
  88     }
  89     // different underlying surfaces => compare bounding boxes
  90     return compareByBoundingBox(theLHS, theRHS);
  91   }
  92
  93   bool compareByBoundingBox(const GeomShapePtr& theLHS, const GeomShapePtr& theRHS)
  94   {
  95     Bnd_Box aLHSBox = boundingBox(theLHS);
  96     Bnd_Box aRHSBox = boundingBox(theRHS);
  97
  98     gp_Pnt aLHSMin = aLHSBox.CornerMin();
  99     gp_Pnt aLHSMax = aLHSBox.CornerMax();
 100
 101     gp_Pnt aRHSMin = aRHSBox.CornerMin();
 102     gp_Pnt aRHSMax = aRHSBox.CornerMax();
 103
 104     if (isLess(aLHSMin, aRHSMin))
 105       return true;
 106     else if (isLess(aRHSMin, aLHSMin))
 107       return false;
 108
 109     return isLess(aLHSMax, aRHSMax);
 110   }
 111
 112   bool isLessWithTol(const double theLHS, const double theRHS, const double theTolerance)
 113   {
 114     return theLHS + theTolerance < theRHS;
 115   }
 116
 117   bool isLess(const gp_Pnt& theLHS, const gp_Pnt& theRHS)
 118   {
 119     for (int anIndex = 1; anIndex <= 3; ++anIndex) {
 120       if (isLessWithTol(theLHS.Coord(anIndex), theRHS.Coord(anIndex), Precision::Confusion()))
 121         return true;
 122       else if (isLessWithTol(theRHS.Coord(anIndex), theLHS.Coord(anIndex), Precision::Confusion()))
 123         return false;
 124     }
 125     // equal points
 126     return false;
 127   }
 128
 129   Bnd_Box boundingBox(const GeomShapePtr& theShape)
 130   {
 131     const TopoDS_Shape& aShape = theShape->impl<TopoDS_Shape>();
 132     TopoDS_TShape* aS = aShape.TShape().get();
 133     std::map<TopoDS_TShape*, Bnd_Box>::iterator aFound = myShapes.find(aS);
 134     if (aFound == myShapes.end()) {
 135       Bnd_Box aBB;
 136       BRepBndLib::Add(aShape, aBB);
 137       myShapes[aS] = aBB;
 138       aFound = myShapes.find(aS);
 139     }
 140     return aFound->second;
 141   }
 142
 143   Bnd_Box2d boundingBoxUV(const TopoDS_Face& theFace)
 144   {
 145     TopoDS_TShape* aFacePtr = theFace.TShape().get();
 146     std::map<TopoDS_TShape*, Bnd_Box2d>::iterator aFound = myUVBounds.find(aFacePtr);
 147     if (aFound == myUVBounds.end()) {
 148       Bnd_Box2d aBB;
 149       BRepTools::AddUVBounds(theFace, aBB);
 150       myUVBounds[aFacePtr] = aBB;
 151       aFound = myUVBounds.find(aFacePtr);
 152     }
 153     return aFound->second;
 154   }
 155
 156 public:
 157   // Verify theLHS is less than theRHS
 158   bool operator() (const GeomShapePtr& theLHS, const GeomShapePtr& theRHS)
 159   {
 160     if (theLHS->shapeType() == theRHS->shapeType()) {
 161       // edges and faces are compared by geometric properties
 162       if (theLHS->shapeType() == GeomAPI_Shape::EDGE)
 163         return compareEdges(theLHS, theRHS);
 164       else if (theLHS->shapeType() == GeomAPI_Shape::FACE)
 165         return compareFaces(theLHS, theRHS);
 166       // all other comparisons are made by bounding boxes
 167       return compareByBoundingBox(theLHS, theRHS);
 168     }
 169
 170     // shapes of different types are compared by the type
 171     return theLHS->shapeType() < theRHS->shapeType();
 172   }
 173 };
 174
 175
 176 void GeomAlgoAPI_SortListOfShapes::sort(ListOfShape& theShapes)
 177 {
 178   CompareShapes aComparator;
 179   theShapes.sort(aComparator);
 180 }