0024023: Revamp the OCCT Handle -- general
[occt.git] / src / Poly / Poly_MakeLoops.hxx
1 // Created on: 2009-10-22
2 // Created by: Mikhail SAZONOV
3 // Copyright (c) 2009-2014 OPEN CASCADE SAS
4 //
5 // This file is part of Open CASCADE Technology software library.
6 //
7 // This library is free software; you can redistribute it and/or modify it under
8 // the terms of the GNU Lesser General Public License version 2.1 as published
9 // by the Free Software Foundation, with special exception defined in the file
10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
11 // distribution for complete text of the license and disclaimer of any warranty.
12 //
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
15
16 #ifndef Poly_MakeLoops_HeaderFile
17 #define Poly_MakeLoops_HeaderFile
18
19 #include <NCollection_Sequence.hxx>
20 #include <NCollection_IndexedMap.hxx>
21 #include <TColStd_PackedMapOfInteger.hxx>
22 #include <TColStd_MapIteratorOfPackedMapOfInteger.hxx>
23 #include <NCollection_IncAllocator.hxx>
24 #include <NCollection_List.hxx>
25
26
27 /**
28  * Make loops from a set of connected links. A link is represented by 
29  * a pair of integer indices of nodes.
30  */
31 class Poly_MakeLoops
32 {
33 public:
34   //! Orientation flags that can be attached to a link
35   enum LinkFlag {
36     LF_None  = 0,
37     LF_Fwd   = 1,    // forward orientation
38     LF_Rev   = 2,    // reversed orientation
39     LF_Both  = 3,    // both ways oriented
40     LF_Reversed = 4  // means the link is reversed
41   };
42
43   //! The Link structure
44   struct Link
45   {
46     Standard_Integer node1, node2;
47     Standard_Integer flags;
48
49     Link()
50       : node1(0), node2(0), flags(0) {}
51
52     Link(Standard_Integer theNode1, Standard_Integer theNode2)
53       : node1(theNode1), node2(theNode2), flags(1) {}
54
55     void Reverse()
56     {
57       flags ^= Poly_MakeLoops::LF_Reversed;
58     }
59
60     Standard_Boolean IsReversed() const
61     {
62       return flags & Poly_MakeLoops::LF_Reversed;
63     }
64
65     void Nullify()
66     {
67       node1 = node2 = 0;
68     }
69
70     Standard_Boolean IsNull() const
71     {
72       return node1 == 0 || node2 == 0;
73     }
74   };
75
76   // Define the Loop as a list of links
77   typedef NCollection_List<Link> ListOfLink;
78   typedef ListOfLink Loop;
79
80   //! The abstract helper class
81   class Helper
82   {
83   public:
84     //! returns the links adjacent to the given node
85     virtual const ListOfLink& GetAdjacentLinks (Standard_Integer theNode) const = 0;
86     //! hook function called from AddLink in _DEBUG mode
87     virtual void OnAddLink (Standard_Integer /*theNum*/, const Link& /*theLink*/) const {}
88   };
89
90   //! This class implements a heap of integers. The most effective usage
91   //! of it is first to add there all items, and then get top item and remove
92   //! any items till it becomes empty.
93   class HeapOfInteger
94   {
95   public:
96     HeapOfInteger (const Standard_Integer theNbPreAllocated = 1)
97       : myMap (theNbPreAllocated),
98         myIterReady (Standard_False) {}
99
100     void Clear()
101     {
102       myMap.Clear();
103       myIterReady = Standard_False;
104     }
105
106     void Add (const Standard_Integer theValue)
107     {
108       myMap.Add (theValue);
109       myIterReady = Standard_False;
110     }
111
112     Standard_Integer Top()
113     {
114       if (!myIterReady)
115       {
116         myIter.Initialize (myMap);
117         myIterReady = Standard_True;
118       }
119       return myIter.Key();
120     }
121
122     Standard_Boolean Contains (const Standard_Integer theValue) const
123     {
124       return myMap.Contains (theValue);
125     }
126
127     void Remove (const Standard_Integer theValue)
128     {
129       if (myIterReady && myIter.More() && myIter.Key() == theValue)
130         myIter.Next();
131       myMap.Remove (theValue);
132     }
133
134     Standard_Boolean IsEmpty()
135     {
136       if (!myIterReady)
137       {
138         myIter.Initialize (myMap);
139         myIterReady = Standard_True;
140       }
141       return !myIter.More();
142     }
143
144   private:
145     TColStd_PackedMapOfInteger              myMap;
146     TColStd_MapIteratorOfPackedMapOfInteger myIter;
147     Standard_Boolean                        myIterReady;
148   };
149
150 public:
151   // PUBLIC METHODS
152
153   //! Constructor. If helper is NULL then the algorithm will
154   //! probably return a wrong result
155   Standard_EXPORT Poly_MakeLoops(const Helper* theHelper,
156                                  const Handle(NCollection_BaseAllocator)& theAlloc = 0L);
157
158   //! It is to reset the algorithm to the initial state.
159   Standard_EXPORT void Reset
160                    (const Helper* theHelper,
161                     const Handle(NCollection_BaseAllocator)& theAlloc = 0L);
162
163   //! Adds a link to the set. theOrient defines which orientations of the link
164   //! are allowed.
165   Standard_EXPORT void AddLink(const Link& theLink);
166
167   //! Replace one link with another (e.g. to change order of nodes)
168   Standard_EXPORT void ReplaceLink(const Link& theLink, const Link& theNewLink);
169
170   //! Set a new value of orientation of a link already added earlier.
171   //! It can be used with LF_None to exclude the link from consideration.
172   //! Returns the old value of orienation.
173   Standard_EXPORT LinkFlag SetLinkOrientation
174                    (const Link& theLink,
175                     const LinkFlag theOrient);
176
177   //! Find the link stored in algo by value
178   Standard_EXPORT Link FindLink(const Link& theLink) const;
179
180   enum ResultCode
181   {
182     RC_LoopsDone    = 1,
183     RC_HangingLinks = 2,
184     RC_Failure      = 4
185   };
186
187   //! Does the work. Returns the collection of result codes
188   Standard_EXPORT Standard_Integer Perform();
189
190   //! Returns the number of loops in the result
191   Standard_Integer GetNbLoops() const
192   {
193     return myLoops.Length();
194   }
195
196   //! Returns the loop of the given index
197   const Loop& GetLoop(Standard_Integer theIndex) const
198   {
199     return myLoops.Value(theIndex);
200   }
201
202   //! Returns the number of detected hanging chains
203   Standard_Integer GetNbHanging() const
204   {
205     return myHangIndices.Extent();
206   }
207
208   //! Fills in the list of hanging links
209   Standard_EXPORT void GetHangingLinks(ListOfLink& theLinks) const;
210
211 protected:
212   virtual Standard_Integer chooseLeftWay
213                    (const Standard_Integer theNode,
214                     const Standard_Integer theSegIndex,
215                     const NCollection_List<Standard_Integer>& theLstIndS) const = 0;
216
217   const Helper* getHelper () const
218   {
219     return myHelper;
220   }
221
222   Link getLink (const Standard_Integer theSegIndex) const
223   {
224     Link aLink = myMapLink(Abs(theSegIndex));
225     if (theSegIndex < 0)
226       aLink.Reverse();
227     return aLink;
228   }
229 #ifdef OCCT_DEBUG
230   void showBoundaryBreaks() const;
231 #endif
232
233 private:
234   int findContour(Standard_Integer theIndexS, NCollection_IndexedMap<Standard_Integer>& theContour,
235                   const Handle(NCollection_BaseAllocator)& theTempAlloc,
236                   const Handle(NCollection_IncAllocator)& theTempAlloc1) const;
237   void acceptContour(const NCollection_IndexedMap<Standard_Integer>& theContour,
238                      Standard_Integer theStartNumber);
239   Standard_Integer getFirstNode(Standard_Integer theIndexS) const;
240   Standard_Integer getLastNode(Standard_Integer theIndexS) const;
241   void markHangChain(Standard_Integer theNode, Standard_Integer theIndexS);
242   Standard_Boolean canLinkBeTaken(Standard_Integer theIndexS) const;
243
244   // FIELDS
245   const Helper*                           myHelper;
246   Handle(NCollection_BaseAllocator)        myAlloc;
247   NCollection_IndexedMap<Link>            myMapLink;
248   NCollection_Sequence<Loop>              myLoops;
249   HeapOfInteger                           myStartIndices;
250   TColStd_PackedMapOfInteger              myHangIndices;
251 };
252
253 /**
254  * HashCode method is needed for maps
255  */
256 inline Standard_Integer HashCode(const Poly_MakeLoops::Link& theKey,
257                     int theLimit)
258 {
259   return HashCode(theKey.node1 + theKey.node2, theLimit);
260 }
261
262 /**
263  * IsEqual method is needed for maps
264  */
265 inline Standard_Boolean IsEqual(const Poly_MakeLoops::Link& theKey1,
266                                 const Poly_MakeLoops::Link& theKey2)
267 {
268   return ((theKey1.node1 == theKey2.node1 && theKey1.node2 == theKey2.node2) ||
269           (theKey1.node1 == theKey2.node2 && theKey1.node2 == theKey2.node1));
270 }
271
272 /**
273  * Implementation for 3D space
274  */
275 class gp_Dir;
276 class Poly_MakeLoops3D: public Poly_MakeLoops
277 {
278 public:
279   //! The abstract helper class
280   class Helper: public Poly_MakeLoops::Helper
281   {
282   public:
283     // all the following methods should return False if 
284     // it is impossible to return a valid direction
285
286     //! returns the tangent vector at the first node of a link
287     virtual Standard_Boolean GetFirstTangent(const Link& theLink,
288                                              gp_Dir& theDir) const = 0;
289
290     //! returns the tangent vector at the last node of a link
291     virtual Standard_Boolean GetLastTangent(const Link& theLink,
292                                             gp_Dir& theDir) const = 0;
293
294     //! returns the normal to the surface at a given node
295     virtual Standard_Boolean GetNormal(Standard_Integer theNode,
296                                        gp_Dir& theDir) const = 0;
297   };
298
299   //! Constructor. If helper is NULL then the algorithm will
300   //! probably return a wrong result
301   Standard_EXPORT Poly_MakeLoops3D(const Helper* theHelper,
302                                       const Handle(NCollection_BaseAllocator)& theAlloc);
303
304 protected:
305   Standard_EXPORT virtual Standard_Integer chooseLeftWay
306                    (const Standard_Integer theNode,
307                     const Standard_Integer theSegIndex,
308                     const NCollection_List<Standard_Integer>& theLstIndS) const;
309   const Helper* getHelper () const
310   {
311     return static_cast<const Poly_MakeLoops3D::Helper*>
312       (Poly_MakeLoops::getHelper());
313   }
314 };
315
316 /**
317  * Implementation for 2D space
318  */
319 class gp_Dir2d;
320 class Poly_MakeLoops2D: public Poly_MakeLoops
321 {
322 public:
323   //! The abstract helper class
324   class Helper: public Poly_MakeLoops::Helper
325   {
326   public:
327     // all the following methods should return False if 
328     // it is impossible to return a valid direction
329
330     //! returns the tangent vector at the first node of a link
331     virtual Standard_Boolean GetFirstTangent(const Link& theLink,
332                                              gp_Dir2d& theDir) const = 0;
333
334     //! returns the tangent vector at the last node of a link
335     virtual Standard_Boolean GetLastTangent(const Link& theLink,
336                                             gp_Dir2d& theDir) const = 0;
337   };
338
339   //! Constructor. If helper is NULL then the algorithm will
340   //! probably return a wrong result
341   Standard_EXPORT Poly_MakeLoops2D(const Standard_Boolean theLeftWay,
342                                       const Helper* theHelper,
343                                       const Handle(NCollection_BaseAllocator)& theAlloc);
344
345 protected:
346   Standard_EXPORT virtual Standard_Integer chooseLeftWay
347                    (const Standard_Integer theNode,
348                     const Standard_Integer theSegIndex,
349                     const NCollection_List<Standard_Integer>& theLstIndS) const;
350   const Helper* getHelper () const
351   {
352     return static_cast<const Poly_MakeLoops2D::Helper*>
353       (Poly_MakeLoops::getHelper());
354   }
355
356 private:
357   //! this flag says that chooseLeftWay must choose the right way instead
358   Standard_Boolean myRightWay;
359 };
360
361 #endif