src/INTERP_KERNEL/Geometric2D/InterpKernelGeo2DEdge.hxx

   1 // Copyright (C) 2007-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 // Author : Anthony Geay (CEA/DEN)
  20
  21 #ifndef __INTERPKERNELGEO2DEDGE_HXX__
  22 #define __INTERPKERNELGEO2DEDGE_HXX__
  23
  24 #include "INTERPKERNELDefines.hxx"
  25 #include "InterpKernelException.hxx"
  26 #include "InterpKernelGeo2DBounds.hxx"
  27 #include "InterpKernelGeo2DNode.hxx"
  28 #include "MCIdType.hxx"
  29
  30 #include <iostream>
  31 #include <vector>
  32 #include <list>
  33 #include <map>
  34
  35 namespace INTERP_KERNEL
  36 {
  37   typedef enum
  38   {
  39     SEG         = 1,
  40     ARC_CIRCLE  = 4,
  41     ARC_PARABOL = 8
  42   } TypeOfFunction;
  43
  44   typedef enum
  45   {
  46     CIRCLE  = 0 ,
  47     PARABOL = 1
  48   } TypeOfMod4QuadEdge;
  49
  50   typedef enum
  51   {
  52     START       = 5,
  53     END         = 1,
  54     INSIDE      = 2,
  55     OUT_BEFORE  = 3,
  56     OUT_AFTER   = 4
  57   } TypeOfLocInEdge; //see Edge::OFFSET_FOR_TYPEOFLOCINEDGE
  58
  59   typedef enum
  60   {
  61     FULL_IN_1    = 1,
  62     FULL_ON_1    = 4,
  63     FULL_OUT_1   = 2,
  64     FULL_UNKNOWN = 3
  65   } TypeOfEdgeLocInPolygon;
  66
  67   class INTERPKERNEL_EXPORT MergePoints
  68   {
  69   public:
  70     MergePoints();
  71
  72     //methods called during intersection edge-edge
  73     void start1Replaced();
  74     void end1Replaced();
  75     void start1OnStart2();
  76     void start1OnEnd2();
  77     void end1OnStart2();
  78     void end1OnEnd2();
  79     //methods to be called during aggregation
  80     bool isStart1(unsigned rk) const;
  81     bool isEnd1(unsigned rk) const;
  82     bool isStart2(unsigned rk) const;
  83     bool isEnd2(unsigned rk) const;
  84     void clear();
  85     unsigned getNumberOfAssociations() const;
  86     void updateMergedNodes(mcIdType e1Start, mcIdType e1End, mcIdType e2Start, mcIdType e2End, std::map<mcIdType,mcIdType>& mergedNodes);
  87   private:
  88     static void PushInMap(mcIdType key, mcIdType value, std::map<mcIdType,mcIdType>& mergedNodes);
  89   private:
  90     unsigned _ass1Start1  : 1;
  91     unsigned _ass1End1    : 1;
  92     unsigned _ass1Start2  : 1;
  93     unsigned _ass1End2    : 1;
  94     unsigned _ass2Start1  : 1;
  95     unsigned _ass2End1    : 1;
  96     unsigned _ass2Start2  : 1;
  97     unsigned _ass2End2    : 1;
  98   };
  99
 100   class Edge;
 101   class ComposedEdge;
 102   /*!
 103    * This class is in charge to store an intersection point as result of \b non oververlapping edge intersection.
 104    * This class manages the cases when intersect element is one of the extrimities of edge1 and/or edge2.
 105    */
 106   class INTERPKERNEL_EXPORT IntersectElement
 107   {
 108   public:
 109     IntersectElement(double val1, double val2, bool start1, bool end1, bool start2, bool end2, Node *node, const Edge& e1, const Edge& e2, bool keepOrder);
 110     IntersectElement(const IntersectElement& other);
 111     //! The sort operator is done on the edge 1 \b not edge 2.
 112     bool operator<(const IntersectElement& other) const;
 113     IntersectElement& operator=(const IntersectElement& other);
 114     double getVal1() const { return _chararct_val_for_e1; }
 115     double getVal2() const { return _chararct_val_for_e2; }
 116     //! idem operator< method except that the orientation is done on edge 2 \b not edge 1.
 117     bool isLowerOnOther(const IntersectElement& other) const;
 118     unsigned isOnExtrForAnEdgeAndInForOtherEdge() const;
 119     void attachLoc() { _node->setLoc(_loc_of_node); }
 120     bool isOnMergedExtremity() const;
 121     bool isIncludedByBoth() const;
 122     void setNode(Node *node) const;
 123     void performMerging(MergePoints& commonNode) const;
 124     Node *getNodeOnly() const { return _node; }
 125     Node *getNodeAndReleaseIt() { Node *tmp=_node; _node=0; return tmp; }
 126     ~IntersectElement();
 127   private:
 128     bool _1S;  // true if starting point of edge 1 is located exactly on edge 2 (not nearby)
 129     bool _1E;  // true if ending point of edge 1 is located exactly on edge 2 (not nearby)
 130     bool _2S;  // true if starting point of edge 2 is located exactly on edge 1 (not nearby)
 131     bool _2E;  // true if ending point of edge 2 is located exactly on edge 1 (not nearby)
 132     double _chararct_val_for_e1;
 133     double _chararct_val_for_e2;
 134     Node *_node;
 135     TypeOfLocInPolygon _loc_of_node;
 136     const Edge& _e1;
 137     const Edge& _e2;
 138   public:
 139     static const unsigned LIMIT_ALONE = 22;
 140     static const unsigned LIMIT_ON = 73;
 141     static const unsigned NO_LIMIT = 19;
 142   };
 143
 144   /*!
 145    * This abstract interface specifies all the methods to be overloaded of all possibilities edge-intersection.
 146    */
 147   class INTERPKERNEL_EXPORT EdgeIntersector
 148   {
 149   protected:
 150     //! All non symmetric methods are relative to 'e1'.
 151     EdgeIntersector(const Edge& e1, const Edge& e2):_e1(e1),_e2(e2), _earlyInter(0) { }
 152   public:
 153     virtual ~EdgeIntersector() { if(_earlyInter) delete(_earlyInter); }
 154     virtual bool keepOrder() const = 0;
 155     virtual bool areColinears() const = 0;
 156     //!to call only if 'areOverlapped' have been set to true when areOverlappedOrOnlyColinears was called
 157     virtual bool haveTheySameDirection() const = 0;
 158     //!to call only if 'areOverlapped' have been set to true when areOverlappedOrOnlyColinears was called
 159     virtual void getPlacements(Node *start, Node *end, TypeOfLocInEdge& whereStart, TypeOfLocInEdge& whereEnd, MergePoints& commonNode) const = 0;
 160     //! When true is returned, newNodes should contains at least 1 element. All merging nodes betw _e1 and _e2 extremities must be done.
 161     bool intersect(std::vector<Node *>& newNodes, bool& order, MergePoints& commonNode);
 162     //! Should be called only once per association.
 163     virtual void areOverlappedOrOnlyColinears(bool& obviousNoIntersection, bool& areOverlapped) = 0;
 164     //! The size of returned vector is equal to number of potential intersections point. The values are so that their are interpretable by virtual Edge::isIn method.
 165     virtual std::list< IntersectElement > getIntersectionsCharacteristicVal() const = 0;
 166   protected:
 167     void obviousCaseForCurvAbscisse(Node *node, TypeOfLocInEdge& where, MergePoints& commonNode, bool& obvious) const;
 168     virtual void identifyEarlyIntersection(bool& , bool&, bool&, bool&);
 169   protected:
 170     const Edge& _e1;
 171     const Edge& _e2;
 172     IntersectElement *_earlyInter;   // Non null if the intersection can be determined early -> see areOverlappedOrOnlyColinears()
 173   };
 174
 175   class INTERPKERNEL_EXPORT SameTypeEdgeIntersector : public EdgeIntersector
 176   {
 177   protected:
 178     SameTypeEdgeIntersector(const Edge& e1, const Edge& e2):EdgeIntersector(e1,e2) { }
 179     bool keepOrder() const { return true; }
 180   };
 181
 182   class INTERPKERNEL_EXPORT CrossTypeEdgeIntersector : public EdgeIntersector
 183   {
 184   protected:
 185     CrossTypeEdgeIntersector(const Edge& e1, const Edge& e2, bool reverse):EdgeIntersector(e1,e2),_reverse(reverse) { }
 186     bool keepOrder() const { return _reverse; }
 187     bool haveTheySameDirection() const { throw Exception("Cross type intersector is not supposed to deal with overlapped in cross type."); }
 188     const Edge *myE1() { if(_reverse) return &_e1; else return &_e2; }
 189     const Edge *myE2() { if(_reverse) return &_e2; else return &_e1; }
 190   protected:
 191     //! boolean to inform intersector that unsymetrics treatments reverse of e1 and e2 should be done.
 192     bool _reverse;
 193   };
 194
 195   class EdgeLin;
 196   class EdgeInfLin;
 197   class EdgeArcCircle;
 198
 199   /*!
 200    * Deal with an oriented edge of a polygon.
 201    * An Edge is defined with a start node, an end node and an equation of 1D curve.
 202    * All other attributes are mutable because they don't impact these 3 invariant attributes.
 203    * To be exact start and end nodes can change (address) but their location remain
 204    * the same (at precision).
 205    */
 206   class INTERPKERNEL_EXPORT Edge
 207   {
 208   public:
 209     Edge(Node *start, Node *end, bool direction=true):_cnt(1),_loc(FULL_UNKNOWN) { if(direction) { _start=start; _end=end; } else { _start=end; _end=start; } _start->incrRef(); _end->incrRef(); }
 210     Edge(double sX, double sY, double eX, double eY);
 211     TypeOfEdgeLocInPolygon getLoc() const { return _loc; }
 212     void incrRef() const { _cnt++; }
 213     bool decrRef();
 214     void initLocs() const { _loc=FULL_UNKNOWN; _start->initLocs(); _end->initLocs(); }
 215     void declareOn() const;
 216     void declareIn() const;
 217     void declareOut() const;
 218     void initHitStatus() const { _hit=false; }
 219     bool getHitStatus() const { return _hit; }
 220     void hitMeAlone(double xBary, double yBary, double dimChar) { _hit=true; applySimilarity(xBary,yBary,dimChar); }
 221     void unHitMeAlone(double xBary, double yBary, double dimChar) { _hit=true; unApplySimilarity(xBary,yBary,dimChar); }
 222     void hitMeAfter(double xBary, double yBary, double dimChar) { if(!_hit) hitMeAlone(xBary,yBary,dimChar); }
 223     void unHitMeAfter(double xBary, double yBary, double dimChar) { if(!_hit) unHitMeAlone(xBary,yBary,dimChar); }
 224     const Bounds& getBounds() const { return _bounds; }
 225     void fillXfigStreamForLoc(std::ostream& stream) const;
 226     Node *getNode(TypeOfLocInEdge where) const { if(where==START) return _start; else if(where==END) return _end; else return 0; }
 227     Node *getStartNode() const { return _start; }
 228     Node *getEndNode() const { return _end; }
 229     void setEndNodeWithoutChange(Node *newEnd);
 230     void setStartNodeWithoutChange(Node *newStart);
 231     bool changeStartNodeWith(Node *otherStartNode) const;
 232     bool changeStartNodeWithAndKeepTrack(Node *otherStartNode, std::vector<Node *>& track) const;
 233     bool changeEndNodeWith(Node *otherEndNode) const;
 234     bool changeEndNodeWithAndKeepTrack(Node *otherEndNode, std::vector<Node *>& track) const;
 235     void addSubEdgeInVector(Node *start, Node *end, ComposedEdge& vec) const;
 236     void getNormalVector(double *vectOutput) const;
 237     static EdgeIntersector *BuildIntersectorWith(const Edge *e1, const Edge *e2);
 238     static Edge *BuildFromXfigLine(std::istream& str);
 239     static Edge *BuildEdgeFrom(Node *start, Node *end);
 240     template<TypeOfMod4QuadEdge type>
 241     static Edge *BuildEdgeFrom(Node *start, Node *middle, Node *end);
 242     static Edge *BuildEdgeFrom3Points(const double *start, const double *middle, const double *end);
 243     virtual void update(Node *m) = 0;
 244     //! returns area between this and axe Ox delimited along Ox by _start and _end.
 245     virtual double getAreaOfZone() const = 0;
 246     //! apply a similiraty transformation on 'this'
 247     virtual void applySimilarity(double xBary, double yBary, double dimChar);
 248     //! apply the inverse similiraty transformation on 'this'
 249     virtual void unApplySimilarity(double xBary, double yBary, double dimChar);
 250     //! return the length of arc. Value is always > 0. !
 251     virtual double getCurveLength() const = 0;
 252     virtual void getBarycenter(double *bary) const = 0;
 253     virtual void getBarycenterOfZone(double *bary) const = 0;
 254     //! return the middle of two points
 255     virtual void getMiddleOfPoints(const double *p1, const double *p2, double *mid) const = 0;
 256     //! return the middle of two points respecting the orientation defined by this (relevant for arc of circle). By default same as getMiddleOfPoints()
 257     virtual void getMiddleOfPointsOriented(const double *p1, const double *p2, double *mid) const;
 258     //! Retrieves a point that is owning to this, well placed for IN/OUT detection of this. Typically midlle of this is returned.
 259     virtual Node *buildRepresentantOfMySelf() const = 0;
 260     //! Given a magnitude specified by sub-type returns if in or not. See getCharactValue method.
 261     virtual bool isIn(double characterVal) const = 0;
 262     //! With the same magnitude as defined in 'isIn' method perform a compararison. Precondition : val1 and val2 are different and exactly INSIDE this.
 263     virtual bool isLower(double val1, double val2) const = 0;
 264     //! node is expected to lay on 'this'. It returns a characteristic magnitude usable by isIn method.
 265     virtual double getCharactValue(const Node& node) const = 0;
 266     //! node is expected to lay on 'this'. It returns a characteristic magnitude between 0 and 1.
 267     virtual double getCharactValueBtw0And1(const Node& node) const = 0;
 268     //! retrieves the distance to this : The min distance from pt and any point of this.
 269     virtual double getDistanceToPoint(const double *pt) const = 0;
 270     //! return if node with coords 'coordOfNode' is on this (with precision).
 271     virtual bool isNodeLyingOn(const double *coordOfNode) const = 0;
 272     virtual TypeOfFunction getTypeOfFunc() const = 0;
 273     virtual void dynCastFunction(const EdgeLin * &seg,
 274                                  const EdgeArcCircle * &arcSeg) const = 0;
 275     bool intersectWith(const Edge *other, MergePoints& commonNode,
 276                        ComposedEdge& outVal1, ComposedEdge& outVal2) const;
 277     static bool IntersectOverlapped(const Edge *f1, const Edge *f2, EdgeIntersector *intersector, MergePoints& commonNode,
 278                                     ComposedEdge& outValForF1, ComposedEdge& outValForF2);
 279     static void Interpolate1DLin(const std::vector<double>& distrib1, const std::vector<double>& distrib2,
 280                                  std::map<int, std::map<int,double> >& result);
 281     virtual void dumpInXfigFile(std::ostream& stream, bool direction, int resolution, const Bounds& box) const = 0;
 282     void dumpToCout(const std::map<INTERP_KERNEL::Node *,int>& mapp, int index) const;
 283     bool isEqual(const Edge& other) const;
 284   public:
 285     bool sortSubNodesAbs(const double *coo, std::vector<mcIdType>& subNodes);
 286     void sortIdsAbs(const std::vector<INTERP_KERNEL::Node *>& addNodes, const std::map<INTERP_KERNEL::Node *, mcIdType>& mapp1, const std::map<INTERP_KERNEL::Node *, mcIdType>& mapp2, std::vector<mcIdType>& edgesThis);
 287     virtual Edge *buildEdgeLyingOnMe(Node *start, Node *end, bool direction=true) const = 0;
 288     void fillGlobalInfoAbs(bool direction, const std::map<INTERP_KERNEL::Node *,mcIdType>& mapThis, const std::map<INTERP_KERNEL::Node *,mcIdType>& mapOther, mcIdType offset1, mcIdType offset2, double fact, double baryX, double baryY,
 289                            std::vector<mcIdType>& edgesThis, std::vector<double>& addCoo, std::map<INTERP_KERNEL::Node *,mcIdType> mapAddCoo) const;
 290     void fillGlobalInfoAbs2(const std::map<INTERP_KERNEL::Node *,mcIdType>& mapThis, const std::map<INTERP_KERNEL::Node *,mcIdType>& mapOther, mcIdType offset1, mcIdType offset2, double fact, double baryX, double baryY,
 291                             short skipStartOrEnd,
 292                             std::vector<mcIdType>& edgesOther, std::vector<double>& addCoo, std::map<INTERP_KERNEL::Node *,mcIdType>& mapAddCoo) const;
 293
 294   protected:
 295     Edge():_cnt(1),_loc(FULL_UNKNOWN),_start(0),_end(0) { }
 296     virtual ~Edge();
 297     static int CombineCodes(TypeOfLocInEdge code1, TypeOfLocInEdge code2);
 298     static bool Intersect(const Edge *f1, const Edge *f2, EdgeIntersector *intersector, MergePoints& commonNode,
 299                           ComposedEdge& outValForF1, ComposedEdge& outValForF2);
 300     //! The code 'code' is built by method combineCodes
 301     static bool SplitOverlappedEdges(const Edge *e1, const Edge *e2, Node *nS, Node *nE, bool direction, int code,
 302                                      ComposedEdge& outVal1, ComposedEdge& outVal2);
 303   protected:
 304     mutable bool _hit;
 305     mutable unsigned char _cnt;
 306     mutable TypeOfEdgeLocInPolygon _loc;
 307     Bounds _bounds;
 308     Node *_start;
 309     Node *_end;
 310   protected:
 311     //In relation with max possible value of TypeOfLocInEdge.
 312     static const int OFFSET_FOR_TYPEOFLOCINEDGE = 8;
 313   };
 314 }
 315
 316 #endif