1 // Created on: 2009-10-22
2 // Created by: Mikhail SAZONOV
3 // Copyright (c) 2009-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
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.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 #ifndef Poly_MakeLoops_HeaderFile
17 #define Poly_MakeLoops_HeaderFile
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>
28 * Make loops from a set of connected links. A link is represented by
29 * a pair of integer indices of nodes.
34 //! Orientation flags that can be attached to a link
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
43 //! The Link structure
46 Standard_Integer node1, node2;
47 Standard_Integer flags;
50 : node1(0), node2(0), flags(0) {}
52 Link(Standard_Integer theNode1, Standard_Integer theNode2)
53 : node1(theNode1), node2(theNode2), flags(1) {}
57 flags ^= Poly_MakeLoops::LF_Reversed;
60 Standard_Boolean IsReversed() const
62 return (flags & Poly_MakeLoops::LF_Reversed) != 0;
70 Standard_Boolean IsNull() const
72 return node1 == 0 || node2 == 0;
76 // Define the Loop as a list of links
77 typedef NCollection_List<Link> ListOfLink;
78 typedef ListOfLink Loop;
80 //! The abstract helper class
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 {}
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.
96 HeapOfInteger (const Standard_Integer theNbPreAllocated = 1)
97 : myMap (theNbPreAllocated),
98 myIterReady (Standard_False) {}
103 myIterReady = Standard_False;
106 void Add (const Standard_Integer theValue)
108 myMap.Add (theValue);
109 myIterReady = Standard_False;
112 Standard_Integer Top()
116 myIter.Initialize (myMap);
117 myIterReady = Standard_True;
122 Standard_Boolean Contains (const Standard_Integer theValue) const
124 return myMap.Contains (theValue);
127 void Remove (const Standard_Integer theValue)
129 if (myIterReady && myIter.More() && myIter.Key() == theValue)
131 myMap.Remove (theValue);
134 Standard_Boolean IsEmpty()
138 myIter.Initialize (myMap);
139 myIterReady = Standard_True;
141 return !myIter.More();
145 TColStd_PackedMapOfInteger myMap;
146 TColStd_MapIteratorOfPackedMapOfInteger myIter;
147 Standard_Boolean myIterReady;
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);
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);
163 //! Adds a link to the set. theOrient defines which orientations of the link
165 Standard_EXPORT void AddLink(const Link& theLink);
167 //! Replace one link with another (e.g. to change order of nodes)
168 Standard_EXPORT void ReplaceLink(const Link& theLink, const Link& theNewLink);
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);
177 //! Find the link stored in algo by value
178 Standard_EXPORT Link FindLink(const Link& theLink) const;
187 //! Does the work. Returns the collection of result codes
188 Standard_EXPORT Standard_Integer Perform();
190 //! Returns the number of loops in the result
191 Standard_Integer GetNbLoops() const
193 return myLoops.Length();
196 //! Returns the loop of the given index
197 const Loop& GetLoop(Standard_Integer theIndex) const
199 return myLoops.Value(theIndex);
202 //! Returns the number of detected hanging chains
203 Standard_Integer GetNbHanging() const
205 return myHangIndices.Extent();
208 //! Fills in the list of hanging links
209 Standard_EXPORT void GetHangingLinks(ListOfLink& theLinks) const;
212 virtual Standard_Integer chooseLeftWay
213 (const Standard_Integer theNode,
214 const Standard_Integer theSegIndex,
215 const NCollection_List<Standard_Integer>& theLstIndS) const = 0;
217 const Helper* getHelper () const
222 Link getLink (const Standard_Integer theSegIndex) const
224 Link aLink = myMapLink(Abs(theSegIndex));
230 void showBoundaryBreaks() const;
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;
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;
254 * HashCode method is needed for maps
256 inline Standard_Integer HashCode(const Poly_MakeLoops::Link& theKey,
259 return HashCode(theKey.node1 + theKey.node2, theLimit);
263 * IsEqual method is needed for maps
265 inline Standard_Boolean IsEqual(const Poly_MakeLoops::Link& theKey1,
266 const Poly_MakeLoops::Link& theKey2)
268 return ((theKey1.node1 == theKey2.node1 && theKey1.node2 == theKey2.node2) ||
269 (theKey1.node1 == theKey2.node2 && theKey1.node2 == theKey2.node1));
273 * Implementation for 3D space
276 class Poly_MakeLoops3D: public Poly_MakeLoops
279 //! The abstract helper class
280 class Helper: public Poly_MakeLoops::Helper
283 // all the following methods should return False if
284 // it is impossible to return a valid direction
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;
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;
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;
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);
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
311 return static_cast<const Poly_MakeLoops3D::Helper*>
312 (Poly_MakeLoops::getHelper());
317 * Implementation for 2D space
320 class Poly_MakeLoops2D: public Poly_MakeLoops
323 //! The abstract helper class
324 class Helper: public Poly_MakeLoops::Helper
327 // all the following methods should return False if
328 // it is impossible to return a valid direction
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;
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;
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);
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
352 return static_cast<const Poly_MakeLoops2D::Helper*>
353 (Poly_MakeLoops::getHelper());
357 //! this flag says that chooseLeftWay must choose the right way instead
358 Standard_Boolean myRightWay;