1 // File: Poly_MakeLoops.hxx
3 // Author: Mikhail SAZONOV
4 // Copyright: Open Cascade 2009
6 #ifndef Poly_MakeLoops_HeaderFile
7 #define Poly_MakeLoops_HeaderFile
9 #include <NCollection_Sequence.hxx>
10 #include <NCollection_IndexedMap.hxx>
11 #include <TColStd_PackedMapOfInteger.hxx>
12 #include <TColStd_MapIteratorOfPackedMapOfInteger.hxx>
13 #include <NCollection_BaseAllocator.hxx>
14 #include <NCollection_List.hxx>
16 class Handle_NCollection_IncAllocator;
19 * Make loops from a set of connected links. A link is represented by
20 * a pair of integer indices of nodes.
25 //! Orientation flags that can be attached to a link
28 LF_Fwd = 1, // forward orientation
29 LF_Rev = 2, // reversed orientation
30 LF_Both = 3, // both ways oriented
31 LF_Reversed = 4 // means the link is reversed
34 //! The Link structure
37 Standard_Integer node1, node2;
38 Standard_Integer flags;
41 : node1(0), node2(0), flags(0) {}
43 Link(Standard_Integer theNode1, Standard_Integer theNode2)
44 : node1(theNode1), node2(theNode2), flags(0) {}
48 flags ^= Poly_MakeLoops::LF_Reversed;
51 Standard_Boolean IsReversed() const
53 return flags & Poly_MakeLoops::LF_Reversed;
61 Standard_Boolean IsNull() const
63 return node1 == 0 || node2 == 0;
67 // Define the Loop as a list of links
68 typedef NCollection_List<Link> ListOfLink;
69 typedef ListOfLink Loop;
71 //! The abstract helper class
75 //! returns the links adjacent to the given node
76 virtual const ListOfLink& GetAdjacentLinks (Standard_Integer theNode) const = 0;
77 //! hook function called from AddLink in _DEBUG mode
78 virtual void OnAddLink (Standard_Integer /*theNum*/, const Link& /*theLink*/) const {}
81 //! This class implements a heap of integers. The most effective usage
82 //! of it is first to add there all items, and then get top item and remove
83 //! any items till it becomes empty.
87 HeapOfInteger (const Standard_Integer theNbPreAllocated = 1)
88 : myMap (theNbPreAllocated),
89 myIterReady (Standard_False) {}
94 myIterReady = Standard_False;
97 void Add (const Standard_Integer theValue)
100 myIterReady = Standard_False;
103 Standard_Integer Top()
107 myIter.Initialize (myMap);
108 myIterReady = Standard_True;
113 Standard_Boolean Contains (const Standard_Integer theValue) const
115 return myMap.Contains (theValue);
118 void Remove (const Standard_Integer theValue)
120 if (myIterReady && myIter.More() && myIter.Key() == theValue)
122 myMap.Remove (theValue);
125 Standard_Boolean IsEmpty()
129 myIter.Initialize (myMap);
130 myIterReady = Standard_True;
132 return !myIter.More();
136 TColStd_PackedMapOfInteger myMap;
137 TColStd_MapIteratorOfPackedMapOfInteger myIter;
138 Standard_Boolean myIterReady;
144 //! Constructor. If helper is NULL then the algorithm will
145 //! probably return a wrong result
146 Standard_EXPORT Poly_MakeLoops(const Helper* theHelper,
147 const Handle_NCollection_BaseAllocator& theAlloc = 0L);
149 //! It is to reset the algorithm to the initial state.
150 Standard_EXPORT void Reset
151 (const Helper* theHelper,
152 const Handle_NCollection_BaseAllocator& theAlloc = 0L);
154 //! Adds a link to the set. theOrient defines which orientations of the link
156 Standard_EXPORT void AddLink(const Link& theLink);
158 //! Replace one link with another (e.g. to change order of nodes)
159 Standard_EXPORT void ReplaceLink(const Link& theLink, const Link& theNewLink);
161 //! Set a new value of orientation of a link already added earlier.
162 //! It can be used with LF_None to exclude the link from consideration.
163 //! Returns the old value of orienation.
164 Standard_EXPORT LinkFlag SetLinkOrientation
165 (const Link& theLink,
166 const LinkFlag theOrient);
168 //! Find the link stored in algo by value
169 Standard_EXPORT Link FindLink(const Link& theLink) const;
178 //! Does the work. Returns the collection of result codes
179 Standard_EXPORT Standard_Integer Perform();
181 //! Returns the number of loops in the result
182 Standard_Integer GetNbLoops() const
184 return myLoops.Length();
187 //! Returns the loop of the given index
188 const Loop& GetLoop(Standard_Integer theIndex) const
190 return myLoops.Value(theIndex);
193 //! Returns the number of detected hanging chains
194 Standard_Integer GetNbHanging() const
196 return myHangIndices.Extent();
199 //! Fills in the list of hanging links
200 void GetHangingLinks(ListOfLink& theLinks) const;
203 virtual Standard_Integer chooseLeftWay
204 (const Standard_Integer theNode,
205 const Standard_Integer theSegIndex,
206 const NCollection_List<Standard_Integer>& theLstIndS) const = 0;
208 const Helper* getHelper () const
213 Link getLink (const Standard_Integer theSegIndex) const
215 Link aLink = myMapLink(Abs(theSegIndex));
221 void showBoundaryBreaks() const;
225 int findContour(Standard_Integer theIndexS, NCollection_IndexedMap<Standard_Integer>& theContour,
226 const Handle_NCollection_BaseAllocator& theTempAlloc,
227 const Handle_NCollection_IncAllocator& theTempAlloc1) const;
228 void acceptContour(const NCollection_IndexedMap<Standard_Integer>& theContour,
229 Standard_Integer theStartNumber);
230 Standard_Integer getFirstNode(Standard_Integer theIndexS) const;
231 Standard_Integer getLastNode(Standard_Integer theIndexS) const;
232 void markHangChain(Standard_Integer theNode, Standard_Integer theIndexS);
233 Standard_Boolean canLinkBeTaken(Standard_Integer theIndexS) const;
236 const Helper* myHelper;
237 Handle_NCollection_BaseAllocator myAlloc;
238 NCollection_IndexedMap<Link> myMapLink;
239 NCollection_Sequence<Loop> myLoops;
240 HeapOfInteger myStartIndices;
241 TColStd_PackedMapOfInteger myHangIndices;
245 * HashCode method is needed for maps
247 inline Standard_Integer HashCode(const Poly_MakeLoops::Link& theKey,
250 return HashCode(theKey.node1 + theKey.node2, theLimit);
254 * IsEqual method is needed for maps
256 inline Standard_Boolean IsEqual(const Poly_MakeLoops::Link& theKey1,
257 const Poly_MakeLoops::Link& theKey2)
259 return (theKey1.node1 == theKey2.node1 &&
260 theKey1.node2 == theKey2.node2 ||
261 theKey1.node1 == theKey2.node2 &&
262 theKey1.node2 == theKey2.node1);
266 * Implementation for 3D space
269 class Poly_MakeLoops3D: public Poly_MakeLoops
272 //! The abstract helper class
273 class Helper: public Poly_MakeLoops::Helper
276 // all the following methods should return False if
277 // it is impossible to return a valid direction
279 //! returns the tangent vector at the first node of a link
280 virtual Standard_Boolean GetFirstTangent(const Link& theLink,
281 gp_Dir& theDir) const = 0;
283 //! returns the tangent vector at the last node of a link
284 virtual Standard_Boolean GetLastTangent(const Link& theLink,
285 gp_Dir& theDir) const = 0;
287 //! returns the normal to the surface at a given node
288 virtual Standard_Boolean GetNormal(Standard_Integer theNode,
289 gp_Dir& theDir) const = 0;
292 //! Constructor. If helper is NULL then the algorithm will
293 //! probably return a wrong result
294 Standard_EXPORT Poly_MakeLoops3D(const Helper* theHelper,
295 const Handle_NCollection_BaseAllocator& theAlloc);
298 Standard_EXPORT virtual Standard_Integer chooseLeftWay
299 (const Standard_Integer theNode,
300 const Standard_Integer theSegIndex,
301 const NCollection_List<Standard_Integer>& theLstIndS) const;
302 const Helper* getHelper () const
304 return static_cast<const Poly_MakeLoops3D::Helper*>
305 (Poly_MakeLoops::getHelper());
310 * Implementation for 2D space
313 class Poly_MakeLoops2D: public Poly_MakeLoops
316 //! The abstract helper class
317 class Helper: public Poly_MakeLoops::Helper
320 // all the following methods should return False if
321 // it is impossible to return a valid direction
323 //! returns the tangent vector at the first node of a link
324 virtual Standard_Boolean GetFirstTangent(const Link& theLink,
325 gp_Dir2d& theDir) const = 0;
327 //! returns the tangent vector at the last node of a link
328 virtual Standard_Boolean GetLastTangent(const Link& theLink,
329 gp_Dir2d& theDir) const = 0;
332 //! Constructor. If helper is NULL then the algorithm will
333 //! probably return a wrong result
334 Standard_EXPORT Poly_MakeLoops2D(const Standard_Boolean theLeftWay,
335 const Helper* theHelper,
336 const Handle_NCollection_BaseAllocator& theAlloc);
339 Standard_EXPORT virtual Standard_Integer chooseLeftWay
340 (const Standard_Integer theNode,
341 const Standard_Integer theSegIndex,
342 const NCollection_List<Standard_Integer>& theLstIndS) const;
343 const Helper* getHelper () const
345 return static_cast<const Poly_MakeLoops2D::Helper*>
346 (Poly_MakeLoops::getHelper());
350 //! this flag says that chooseLeftWay must choose the right way instead
351 Standard_Boolean myRightWay;