src/GeomAlgoAPI/GeomAlgoAPI_SortListOfShapes.cpp

   1 // Copyright (C) 2017-2019  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 email : webmaster.salome@opencascade.com
  18 //
  19
  20 #include "GeomAlgoAPI_SortListOfShapes.h"
  21
  22 #include <Bnd_Box.hxx>
  23 #include <Bnd_Box2d.hxx>
  24 #include <BRep_Tool.hxx>
  25 #include <BRepBndLib.hxx>
  26 #include <BRepTools.hxx>
  27 #include <gp_Pnt.hxx>
  28 #include <Precision.hxx>
  29 #include <TopoDS.hxx>
  30 #include <TopoDS_Edge.hxx>
  31 #include <TopoDS_Face.hxx>
  32
  33 #include <algorithm>
  34 #include <map>
  35
  36 class CompareShapes
  37 {
  38   std::map<TopoDS_TShape*, Bnd_Box> myShapes;
  39   std::map<TopoDS_TShape*, Bnd_Box2d> myUVBounds;
  40
  41   bool compareEdges(const GeomShapePtr& theLHS, const GeomShapePtr& theRHS)
  42   {
  43     const TopoDS_Edge& aLHSEdge = TopoDS::Edge(theLHS->impl<TopoDS_Shape>());
  44     const TopoDS_Edge& aRHSEdge = TopoDS::Edge(theRHS->impl<TopoDS_Shape>());
  45
  46     double aLF, aLE, aRF, aRE;
  47     Handle(Geom_Curve) aLHSCurve = BRep_Tool::Curve(aLHSEdge, aLF, aLE);
  48     Handle(Geom_Curve) aRHSCurve = BRep_Tool::Curve(aRHSEdge, aRF, aRE);
  49
  50     if (aLHSCurve == aRHSCurve) {
  51       // compare by first parameter
  52       if (isLessWithTol(aLF, aRF, Precision::PConfusion()))
  53         return true;
  54       else if (isLessWithTol(aRF, aLF, Precision::PConfusion()))
  55         return false;
  56       // compare by last parameter
  57       return isLessWithTol(aLE, aRE, Precision::PConfusion());
  58     }
  59     // different underlying curves => compare bounding boxe
  60     return compareByBoundingBox(theLHS, theRHS);
  61   }
  62
  63   bool compareFaces(const GeomShapePtr& theLHS, const GeomShapePtr& theRHS)
  64   {
  65     const TopoDS_Face& aLHSFace = TopoDS::Face(theLHS->impl<TopoDS_Shape>());
  66     const TopoDS_Face& aRHSFace = TopoDS::Face(theRHS->impl<TopoDS_Shape>());
  67
  68     Handle(Geom_Surface) aLHSSurf = BRep_Tool::Surface(aLHSFace);
  69     Handle(Geom_Surface) aRHSSurf = BRep_Tool::Surface(aRHSFace);
  70
  71     if (aLHSSurf == aRHSSurf) {
  72       // compare parametric space for faces on the same surface
  73       Bnd_Box2d aLHSBox = boundingBoxUV(aLHSFace);
  74       Bnd_Box2d aRHSBox = boundingBoxUV(aRHSFace);
  75
  76       double aLHSBB[4], aRHSBB[4];
  77       aLHSBox.Get(aLHSBB[0], aLHSBB[1], aLHSBB[2], aLHSBB[3]);
  78       aRHSBox.Get(aRHSBB[0], aRHSBB[1], aRHSBB[2], aRHSBB[3]);
  79       for (int anIndex = 0; anIndex < 4; ++anIndex) {
  80         if (isLessWithTol(aLHSBB[anIndex], aRHSBB[anIndex], Precision::PConfusion()))
  81           return true;
  82         else if (isLessWithTol(aRHSBB[anIndex], aLHSBB[anIndex], Precision::PConfusion()))
  83           return false;
  84       }
  85       // equal parametric boxes
  86       return false;
  87     }
  88     // different underlying surfaces => compare bounding boxes
  89     return compareByBoundingBox(theLHS, theRHS);
  90   }
  91
  92   bool compareByBoundingBox(const GeomShapePtr& theLHS, const GeomShapePtr& theRHS)
  93   {
  94     Bnd_Box aLHSBox = boundingBox(theLHS);
  95     Bnd_Box aRHSBox = boundingBox(theRHS);
  96
  97     gp_Pnt aLHSMin = aLHSBox.CornerMin();
  98     gp_Pnt aLHSMax = aLHSBox.CornerMax();
  99
 100     gp_Pnt aRHSMin = aRHSBox.CornerMin();
 101     gp_Pnt aRHSMax = aRHSBox.CornerMax();
 102
 103     if (isLess(aLHSMin, aRHSMin))
 104       return true;
 105     else if (isLess(aRHSMin, aLHSMin))
 106       return false;
 107
 108     return isLess(aLHSMax, aRHSMax);
 109   }
 110
 111   bool isLessWithTol(const double theLHS, const double theRHS, const double theTolerance)
 112   {
 113     return theLHS + theTolerance < theRHS;
 114   }
 115
 116   bool isLess(const gp_Pnt& theLHS, const gp_Pnt& theRHS)
 117   {
 118     static const double aTol = 10. * Precision::Confusion();
 119     for (int anIndex = 1; anIndex <= 3; ++anIndex) {
 120       if (isLessWithTol(theLHS.Coord(anIndex), theRHS.Coord(anIndex), aTol))
 121         return true;
 122       else if (isLessWithTol(theRHS.Coord(anIndex), theLHS.Coord(anIndex), aTol))
 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::AddOptimal(aShape, aBB, false);
 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 }