Commit | Line | Data |
---|---|---|
b311480e | 1 | // Created on: 2009-10-22 |
2 | // Created by: Mikhail SAZONOV | |
973c2be1 | 3 | // Copyright (c) 2009-2014 OPEN CASCADE SAS |
b311480e | 4 | // |
973c2be1 | 5 | // This file is part of Open CASCADE Technology software library. |
b311480e | 6 | // |
d5f74e42 | 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 | |
973c2be1 | 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. | |
b311480e | 12 | // |
973c2be1 | 13 | // Alternatively, this file may be used under the terms of Open CASCADE |
14 | // commercial license or contractual agreement. | |
7fd59977 | 15 | |
16 | #include <Poly_MakeLoops.hxx> | |
17 | #include <NCollection_IncAllocator.hxx> | |
18 | #include <NCollection_DataMap.hxx> | |
19 | #include <gp_Dir.hxx> | |
20 | #include <gp_Dir2d.hxx> | |
21 | ||
0797d9d3 | 22 | #ifdef OCCT_DEBUG |
7fd59977 | 23 | static Standard_Integer doDebug = 0; |
24 | #endif | |
25 | ||
26 | //======================================================================= | |
27 | //function : Poly_MakeLoops | |
28 | //purpose : | |
29 | //======================================================================= | |
30 | ||
31 | Poly_MakeLoops::Poly_MakeLoops(const Helper* theHelper, | |
857ffd5e | 32 | const Handle(NCollection_BaseAllocator)& theAlloc) |
7fd59977 | 33 | : myHelper (theHelper), |
34 | myAlloc (theAlloc), | |
35 | myMapLink (4000, myAlloc), | |
36 | myLoops (myAlloc), | |
37 | myStartIndices (4000) | |
38 | { | |
39 | } | |
40 | ||
41 | //======================================================================= | |
42 | //function : Reset | |
43 | //purpose : | |
44 | //======================================================================= | |
45 | ||
46 | void Poly_MakeLoops::Reset | |
47 | (const Helper* theHelper, | |
857ffd5e | 48 | const Handle(NCollection_BaseAllocator)& theAlloc) |
7fd59977 | 49 | { |
50 | myHelper = theHelper; | |
51 | myMapLink.Clear(); | |
52 | myLoops.Clear(theAlloc); | |
53 | myStartIndices.Clear(); | |
54 | myAlloc = theAlloc; | |
55 | } | |
56 | ||
57 | //======================================================================= | |
58 | //function : AddLink | |
59 | //purpose : | |
60 | //======================================================================= | |
61 | ||
62 | void Poly_MakeLoops::AddLink(const Link& theLink) | |
63 | { | |
64 | if (theLink.node1 == theLink.node2) | |
65 | return; | |
66 | Standard_Integer aInd = myMapLink.Add(theLink); | |
67 | Link& aLink = const_cast<Link&>(myMapLink(aInd)); | |
68 | aLink.flags |= theLink.flags; | |
0797d9d3 | 69 | #ifdef OCCT_DEBUG |
7fd59977 | 70 | myHelper->OnAddLink (aInd, aLink); |
71 | #endif | |
72 | } | |
73 | ||
74 | //======================================================================= | |
75 | //function : ReplaceLink | |
76 | //purpose : | |
77 | //======================================================================= | |
78 | ||
79 | void Poly_MakeLoops::ReplaceLink(const Link& theLink, const Link& theNewLink) | |
80 | { | |
81 | if (theNewLink.node1 == theNewLink.node2) | |
82 | return; | |
83 | Standard_Integer aInd = myMapLink.Add(theLink); | |
84 | if (aInd > 0) | |
85 | { | |
86 | Link aLink; | |
87 | // replace with a null link first (workaround exception) | |
88 | myMapLink.Substitute(aInd, aLink); | |
89 | aLink = theNewLink; | |
90 | // and now put there the final value of link | |
91 | myMapLink.Substitute(aInd, aLink); | |
0797d9d3 | 92 | #ifdef OCCT_DEBUG |
7fd59977 | 93 | myHelper->OnAddLink (aInd, aLink); |
94 | #endif | |
95 | } | |
96 | } | |
97 | ||
98 | //======================================================================= | |
99 | //function : SetLinkOrientation | |
100 | //purpose : | |
101 | //======================================================================= | |
102 | ||
103 | Poly_MakeLoops::LinkFlag Poly_MakeLoops::SetLinkOrientation | |
104 | (const Link& theLink, | |
105 | const LinkFlag theOrient) | |
106 | { | |
107 | Standard_Integer aInd = myMapLink.FindIndex(theLink); | |
108 | LinkFlag aOri = LF_None; | |
109 | if (aInd > 0) | |
110 | { | |
111 | Link& aLink = const_cast<Link&>(myMapLink(aInd)); | |
112 | aOri = (LinkFlag) (aLink.flags & LF_Both); | |
113 | aLink.flags = theOrient; | |
0797d9d3 | 114 | #ifdef OCCT_DEBUG |
7fd59977 | 115 | myHelper->OnAddLink (aInd, aLink); |
116 | #endif | |
117 | } | |
118 | return aOri; | |
119 | } | |
120 | ||
121 | //======================================================================= | |
122 | //function : FindLink | |
123 | //purpose : | |
124 | //======================================================================= | |
125 | ||
126 | Poly_MakeLoops::Link Poly_MakeLoops::FindLink(const Link& theLink) const | |
127 | { | |
128 | Standard_Integer aInd = myMapLink.FindIndex(theLink); | |
129 | Poly_MakeLoops::Link aLink; | |
130 | if (aInd > 0) | |
131 | aLink = myMapLink(aInd); | |
132 | return aLink; | |
133 | } | |
134 | ||
135 | //======================================================================= | |
136 | //function : Perform | |
137 | //purpose : | |
138 | //======================================================================= | |
139 | ||
140 | Standard_Integer Poly_MakeLoops::Perform() | |
141 | { | |
142 | // prepare the set of start indices | |
143 | myStartIndices.Clear(); | |
144 | Standard_Integer i; | |
145 | for (i = 1; i <= myMapLink.Extent(); i++) | |
146 | { | |
147 | const Link& aLink = myMapLink(i); | |
148 | if (aLink.flags & LF_Fwd) | |
149 | myStartIndices.Add(i); | |
150 | if (aLink.flags & LF_Rev) | |
151 | myStartIndices.Add(-i); | |
152 | } | |
153 | ||
0797d9d3 | 154 | #ifdef OCCT_DEBUG |
7fd59977 | 155 | if (doDebug) |
156 | showBoundaryBreaks(); | |
157 | #endif | |
158 | ||
159 | Standard_Integer aResult = 0; | |
160 | ||
161 | Handle(NCollection_IncAllocator) aTempAlloc = new NCollection_IncAllocator(4000); | |
162 | Handle(NCollection_IncAllocator) aTempAlloc1 = new NCollection_IncAllocator(4000); | |
163 | ||
164 | // two pass loop | |
165 | Standard_Integer aPassNum, nbLoopsOnPass2 = 0; | |
166 | for (aPassNum=0; aPassNum < 2; aPassNum++) | |
167 | { | |
168 | myHangIndices.Clear(); | |
169 | // main loop | |
170 | while (!myStartIndices.IsEmpty()) | |
171 | { | |
172 | Standard_Integer aIndexS = myStartIndices.Top(); | |
173 | ||
174 | aTempAlloc->Reset(); | |
175 | NCollection_IndexedMap<Standard_Integer> aContour (100, aTempAlloc); | |
176 | Standard_Integer aStartNumber = findContour (aIndexS, aContour, aTempAlloc, aTempAlloc1); | |
0797d9d3 | 177 | #ifdef OCCT_DEBUG |
7fd59977 | 178 | if (aStartNumber > 1) |
179 | if (doDebug) | |
180 | { | |
04232180 | 181 | std::cout << "--- found contour with hanging links:" << std::endl; |
7fd59977 | 182 | for (i = 1; i <= aContour.Extent(); i++) |
04232180 | 183 | std::cout << " " << aContour(i); |
184 | std::cout << std::endl; | |
7fd59977 | 185 | } |
186 | #endif | |
187 | if (aStartNumber == 0) | |
188 | { // error | |
189 | aResult |= RC_Failure; | |
190 | return aResult; | |
191 | } | |
192 | if (aStartNumber <= aContour.Extent()) | |
193 | { | |
194 | // there is a closed loop in the contour | |
195 | if (aPassNum == 1) | |
196 | nbLoopsOnPass2++; | |
197 | acceptContour (aContour, aStartNumber); | |
198 | } | |
199 | if (aStartNumber > 1) | |
200 | { | |
201 | // it is required to mark hanging edges | |
202 | Standard_Integer aNode; | |
203 | if (aStartNumber <= aContour.Extent()) | |
204 | // mark hanging edges starting from the first one till a bifurcation | |
205 | aNode = getFirstNode(aIndexS); | |
206 | else | |
207 | { | |
208 | // open contour - mark from the end back till a bifurcation | |
209 | aIndexS = aContour(aStartNumber - 1); | |
210 | aNode = getLastNode(aIndexS); | |
211 | } | |
212 | markHangChain(aNode, aIndexS); | |
213 | } | |
214 | } | |
215 | ||
216 | if (aPassNum == 0) | |
217 | { | |
218 | // move hanging links to start indices to make the second pass | |
219 | TColStd_MapIteratorOfPackedMapOfInteger it(myHangIndices); | |
220 | for (; it.More(); it.Next()) | |
221 | myStartIndices.Add(it.Key()); | |
222 | } | |
223 | } | |
0797d9d3 | 224 | #ifdef OCCT_DEBUG |
7fd59977 | 225 | if (doDebug && nbLoopsOnPass2) |
04232180 | 226 | std::cout << "MakeLoops: " << nbLoopsOnPass2 |
227 | << " contours accepted on the second pass" << std::endl; | |
7fd59977 | 228 | #endif |
229 | ||
230 | if (!myLoops.IsEmpty()) | |
231 | aResult |= RC_LoopsDone; | |
232 | if (!myHangIndices.IsEmpty()) | |
233 | aResult |= RC_HangingLinks; | |
234 | return aResult; | |
235 | } | |
236 | ||
237 | //======================================================================= | |
238 | //function : findContour | |
239 | //purpose : Collects edges in chain until they form a closed contour. | |
240 | // Returns the index in the map theContour where the loop starts. | |
241 | // It may return the number greater than the extent of the map by 1, | |
242 | // what means that the contour is open | |
243 | //======================================================================= | |
244 | ||
245 | Standard_Integer Poly_MakeLoops::findContour | |
246 | (Standard_Integer theIndexS, | |
247 | NCollection_IndexedMap<Standard_Integer> &theContour, | |
857ffd5e | 248 | const Handle(NCollection_BaseAllocator)& theTempAlloc, |
249 | const Handle(NCollection_IncAllocator)& theTempAlloc1) const | |
7fd59977 | 250 | { |
251 | theContour.Clear(); | |
252 | Standard_Integer aStartIndex = 0; | |
253 | Standard_Integer aIndexS = theIndexS; | |
254 | NCollection_DataMap<Standard_Integer,Standard_Integer> aNodeLink(100, theTempAlloc); | |
255 | Standard_Integer aLastNode = getLastNode (aIndexS); | |
256 | ||
257 | for (;;) { | |
258 | theContour.Add(aIndexS); | |
259 | aNodeLink.Bind(getFirstNode(aIndexS), aIndexS); | |
260 | ||
261 | Standard_Integer aIndex = Abs (aIndexS); | |
262 | ||
263 | // collect the list of links from this node able to participate | |
264 | // in this contour | |
265 | theTempAlloc1->Reset(); | |
266 | NCollection_List<Standard_Integer> aLstIndS (theTempAlloc1); | |
267 | const ListOfLink& aLinks = myHelper->GetAdjacentLinks (aLastNode); | |
268 | Poly_MakeLoops::ListOfLink::Iterator itLinks (aLinks); | |
269 | for (; itLinks.More(); itLinks.Next()) { | |
270 | Standard_Integer aInd = myMapLink.FindIndex(itLinks.Value()); | |
271 | if (aInd == 0 || aInd == aIndex) | |
272 | continue; | |
273 | // determine the orientation in which the link is to be taken | |
274 | Standard_Integer aIndS = aInd; | |
275 | Standard_Integer aNode1 = getFirstNode(aInd); | |
276 | if (aNode1 != aLastNode) | |
277 | aIndS = -aIndS; | |
278 | ||
279 | if (canLinkBeTaken(aIndS)) | |
280 | aLstIndS.Append(aIndS); | |
281 | } | |
282 | ||
283 | if (aLstIndS.IsEmpty()) { | |
284 | // no more ways: open contour | |
285 | aStartIndex = theContour.Extent() + 1; | |
286 | break; | |
287 | } | |
288 | ||
289 | Standard_Integer aIndexSNext = 0; | |
290 | if (aLstIndS.First() == aLstIndS.Last()) | |
291 | // only one possible way | |
292 | aIndexSNext = aLstIndS.First(); | |
293 | else | |
294 | // find the most left way | |
295 | aIndexSNext = chooseLeftWay (aLastNode, aIndexS, aLstIndS); | |
296 | ||
297 | aIndexS = aIndexSNext; | |
298 | ||
299 | if (aIndexS == 0) | |
300 | { | |
301 | // no more ways: open contour | |
302 | aStartIndex = theContour.Extent() + 1; | |
303 | break; | |
304 | } | |
305 | if (theContour.Contains(aIndexS)) | |
306 | { | |
307 | // entering the loop second time, stop search | |
308 | aStartIndex = theContour.FindIndex (aIndexS); | |
309 | break; | |
310 | } | |
311 | if (theContour.Contains (-aIndexS)) | |
312 | { | |
313 | // leaving the loop, stop search | |
314 | aStartIndex = theContour.FindIndex (-aIndexS) + 1; | |
315 | break; | |
316 | } | |
317 | ||
318 | aLastNode = getLastNode (aIndexS); | |
319 | ||
320 | if (aNodeLink.IsBound(aLastNode)) | |
321 | { | |
322 | // closing the loop, stop search | |
323 | theContour.Add(aIndexS); | |
324 | aStartIndex = theContour.FindIndex(aNodeLink.Find(aLastNode)); | |
325 | break; | |
326 | } | |
327 | } | |
328 | ||
329 | return aStartIndex; | |
330 | } | |
331 | ||
332 | //======================================================================= | |
333 | //function : acceptContour | |
334 | //purpose : Builds a wire from a given set of edge indices (starting with | |
335 | // theStartNumber) and appends it to the result list. | |
336 | // Also updates the start indices. | |
337 | //======================================================================= | |
338 | ||
339 | void Poly_MakeLoops::acceptContour | |
340 | (const NCollection_IndexedMap<Standard_Integer>& theContour, | |
341 | Standard_Integer theStartNumber) | |
342 | { | |
343 | // append a new loop to the result | |
344 | Loop anEmptyLoop(myAlloc); | |
345 | myLoops.Append(anEmptyLoop); | |
346 | Loop& aLoop = myLoops.ChangeValue(myLoops.Length()); | |
347 | ||
348 | // build a loop, mark links as taken, | |
349 | // remove them from the set of start indices | |
350 | Standard_Integer i; | |
351 | for (i = theStartNumber; i <= theContour.Extent(); i++) | |
352 | { | |
353 | Standard_Integer aIndexS = theContour(i); // index with sign | |
354 | Standard_Integer aIndex = Abs (aIndexS); | |
355 | const Link& aLink = myMapLink(aIndex); | |
356 | Link aOrientedLink = aLink; | |
357 | if (aIndexS < 0) | |
358 | aOrientedLink.Reverse(); | |
359 | aLoop.Append(aOrientedLink); | |
360 | // remove from start set | |
361 | myStartIndices.Remove(aIndexS); | |
362 | } | |
363 | } | |
364 | ||
365 | //======================================================================= | |
366 | //function : getFirstNode | |
367 | //purpose : Returns the first node of the given link | |
368 | // taking into account its orientation (the sign of index) | |
369 | //======================================================================= | |
370 | ||
371 | Standard_Integer Poly_MakeLoops::getFirstNode(Standard_Integer theIndexS) const | |
372 | { | |
373 | Standard_Integer aIndex = Abs(theIndexS); | |
374 | const Link& aLink = myMapLink(aIndex); | |
375 | if (theIndexS > 0) | |
376 | return aLink.node1; | |
377 | return aLink.node2; | |
378 | } | |
379 | ||
380 | //======================================================================= | |
381 | //function : getLastNode | |
382 | //purpose : Returns the last node of the given link | |
383 | // taking into account its orientation (the sign of index) | |
384 | //======================================================================= | |
385 | ||
386 | Standard_Integer Poly_MakeLoops::getLastNode(int theIndexS) const | |
387 | { | |
388 | Standard_Integer aIndex = Abs(theIndexS); | |
389 | const Link& aLink = myMapLink(aIndex); | |
390 | if (theIndexS > 0) | |
391 | return aLink.node2; | |
392 | return aLink.node1; | |
393 | } | |
394 | ||
395 | //======================================================================= | |
396 | //function : markHangChain | |
397 | //purpose : Marks hanging links starting from the given node. | |
398 | // Also removes such links from the start indices. | |
399 | //======================================================================= | |
400 | ||
401 | void Poly_MakeLoops::markHangChain(Standard_Integer theNode, Standard_Integer theIndexS) | |
402 | { | |
403 | Standard_Integer aNode1 = theNode; | |
404 | Standard_Integer aIndexS = theIndexS; | |
405 | Standard_Integer aIndex = Abs(aIndexS); | |
406 | Standard_Boolean isOut = (aNode1 == getFirstNode(aIndexS)); | |
407 | for (;;) | |
408 | { | |
409 | // check if the current link is hanging: | |
410 | // if it is outcoming from aNode1 then count the number of | |
411 | // other incoming links and vise versa; | |
412 | // if the number is zero than it is hanging | |
413 | const ListOfLink& aLinks = myHelper->GetAdjacentLinks (aNode1); | |
414 | Standard_Integer nEdges = 0; | |
415 | Poly_MakeLoops::ListOfLink::Iterator itLinks (aLinks); | |
416 | for (; itLinks.More() && nEdges == 0; itLinks.Next()) | |
417 | { | |
418 | const Link &aL = itLinks.Value(); | |
419 | Standard_Integer aInd = myMapLink.FindIndex(aL); | |
420 | if (aInd == 0 || aInd == aIndex) | |
421 | continue; | |
0ebaa4db | 422 | if ((isOut && aNode1 == aL.node1) || |
423 | (!isOut && aNode1 == aL.node2)) | |
7fd59977 | 424 | aInd = -aInd; |
425 | if (canLinkBeTaken(aInd)) | |
426 | nEdges++; | |
427 | } | |
428 | if (nEdges > 0) | |
429 | // leave this chain | |
430 | break; | |
431 | ||
432 | // mark the current link as hanging | |
433 | myStartIndices.Remove(aIndexS); | |
434 | myHangIndices.Add(aIndexS); | |
435 | ||
436 | // get other node of the link and the next link | |
437 | if (isOut) | |
438 | aNode1 = getLastNode(aIndexS); | |
439 | else | |
440 | aNode1 = getFirstNode(aIndexS); | |
441 | const ListOfLink& aNextLinks = myHelper->GetAdjacentLinks (aNode1); | |
442 | Standard_Integer aNextIndexS = 0; | |
443 | for (itLinks.Init(aNextLinks); itLinks.More(); itLinks.Next()) | |
444 | { | |
445 | const Link &aL = itLinks.Value(); | |
446 | Standard_Integer aInd = myMapLink.FindIndex(aL); | |
447 | if (aInd == 0 || aInd == aIndex) | |
448 | continue; | |
0ebaa4db | 449 | if ((isOut && aNode1 == aL.node2) || |
450 | (!isOut && aNode1 == aL.node1)) | |
7fd59977 | 451 | aInd = -aInd; |
452 | if (canLinkBeTaken(aInd)) | |
453 | { | |
454 | if (aNextIndexS == 0) | |
455 | aNextIndexS = aInd; | |
456 | else | |
457 | { | |
458 | // more than 1 ways, stop the chain | |
459 | aNextIndexS = 0; | |
460 | break; | |
461 | } | |
462 | } | |
463 | } | |
464 | if (aNextIndexS == 0) | |
465 | break; | |
466 | aIndexS = aNextIndexS; | |
467 | aIndex = Abs(aIndexS); | |
468 | } | |
469 | } | |
470 | ||
471 | //======================================================================= | |
472 | //function : canLinkBeTaken | |
473 | //purpose : Returns True if the link appointed by the index can participate | |
474 | // in a loop in given orientation (it is the sign of index). | |
475 | // Remark: A boundary edge can be taken only once | |
476 | //======================================================================= | |
477 | ||
478 | Standard_Boolean Poly_MakeLoops::canLinkBeTaken(Standard_Integer theIndexS) const | |
479 | { | |
480 | return myStartIndices.Contains(theIndexS); | |
481 | } | |
482 | ||
483 | //======================================================================= | |
484 | //function : showBoundaryBreaks | |
485 | //purpose : | |
486 | //======================================================================= | |
487 | ||
0797d9d3 | 488 | #ifdef OCCT_DEBUG |
7fd59977 | 489 | void Poly_MakeLoops::showBoundaryBreaks() const |
490 | { | |
491 | // collect nodes of boundary links | |
492 | TColStd_PackedMapOfInteger aNodesMap; | |
493 | Standard_Integer i; | |
494 | for (i = 1; i <= myMapLink.Extent(); i++) | |
495 | { | |
496 | const Link& aLink = myMapLink(i); | |
497 | Standard_Integer aFlags = aLink.flags & LF_Both; | |
498 | if (aFlags && aFlags != LF_Both) | |
499 | { | |
500 | // take only oriented links | |
501 | aNodesMap.Add(aLink.node1); | |
502 | aNodesMap.Add(aLink.node2); | |
503 | } | |
504 | } | |
505 | ||
506 | // check each node if the number of input and output links are equal | |
507 | Standard_Boolean isFirst = Standard_True; | |
508 | TColStd_MapIteratorOfPackedMapOfInteger it(aNodesMap); | |
509 | for (; it.More(); it.Next()) | |
510 | { | |
511 | Standard_Integer aNode = it.Key(); | |
512 | Standard_Integer nb = 0; | |
513 | const ListOfLink& aLinks = myHelper->GetAdjacentLinks(aNode); | |
514 | Poly_MakeLoops::ListOfLink::Iterator itLinks (aLinks); | |
515 | for (; itLinks.More(); itLinks.Next()) | |
516 | { | |
517 | const Poly_MakeLoops::Link& aLink = itLinks.Value(); | |
518 | if (myMapLink.FindIndex(aLink) == 0) | |
519 | continue; | |
520 | Standard_Integer aFlags = aLink.flags & LF_Both; | |
521 | if (aFlags && aFlags != LF_Both) | |
522 | { | |
523 | if (aNode == aLink.node1) // output? | |
524 | { | |
525 | if (aFlags & LF_Fwd) | |
526 | nb++; // yes, output | |
527 | else | |
528 | nb--; // reversed, so input | |
529 | } | |
530 | else if (aNode == aLink.node2) // input? | |
531 | { | |
532 | if (aFlags & LF_Fwd) | |
533 | nb--; // yes, input | |
534 | else | |
535 | nb++; // reversed, so output | |
536 | } | |
537 | else | |
538 | // inconsistent | |
539 | nb += 100; | |
540 | } | |
541 | } | |
542 | if (nb != 0) | |
543 | { | |
544 | // indicate this node | |
545 | if (isFirst) | |
546 | { | |
547 | isFirst = Standard_False; | |
04232180 | 548 | std::cout << "boundary breaks are found in the following nodes:" << std::endl; |
7fd59977 | 549 | } |
04232180 | 550 | std::cout << aNode << " "; |
7fd59977 | 551 | } |
552 | } | |
553 | if (!isFirst) | |
04232180 | 554 | std::cout << std::endl; |
7fd59977 | 555 | } |
556 | #endif | |
557 | ||
558 | //======================================================================= | |
559 | //function : GetHangingLinks | |
560 | //purpose : | |
561 | //======================================================================= | |
562 | ||
563 | void Poly_MakeLoops::GetHangingLinks(ListOfLink& theLinks) const | |
564 | { | |
565 | TColStd_MapIteratorOfPackedMapOfInteger it(myHangIndices); | |
566 | for (; it.More(); it.Next()) | |
567 | { | |
568 | Standard_Integer aIndexS = it.Key(); | |
569 | Link aLink = myMapLink(Abs(aIndexS)); | |
570 | if (aIndexS < 0) | |
571 | aLink.Reverse(); | |
572 | theLinks.Append(aLink); | |
573 | } | |
574 | } | |
575 | ||
576 | //======================================================================= | |
577 | //function : Poly_MakeLoops3D | |
578 | //purpose : | |
579 | //======================================================================= | |
580 | ||
581 | Poly_MakeLoops3D::Poly_MakeLoops3D(const Helper* theHelper, | |
857ffd5e | 582 | const Handle(NCollection_BaseAllocator)& theAlloc) |
7fd59977 | 583 | : Poly_MakeLoops (theHelper, theAlloc) |
584 | { | |
585 | } | |
586 | ||
587 | //======================================================================= | |
588 | //function : Poly_MakeLoops3D::chooseLeftWay | |
589 | //purpose : | |
590 | //======================================================================= | |
591 | ||
592 | Standard_Integer Poly_MakeLoops3D::chooseLeftWay | |
593 | (const Standard_Integer theNode, | |
594 | const Standard_Integer theSegIndex, | |
595 | const NCollection_List<Standard_Integer>& theLstIndS) const | |
596 | { | |
c6541a0c | 597 | Standard_Real aAngleMin = M_PI * 2; |
7fd59977 | 598 | gp_Dir aNormal; |
599 | const Helper* aHelper = getHelper(); | |
600 | if (!aHelper->GetNormal (theNode, aNormal)) | |
601 | return theLstIndS.First(); | |
602 | ||
603 | Link aLink = getLink(theSegIndex); | |
604 | gp_Dir aTgtRef; | |
605 | if (!aHelper->GetLastTangent (aLink, aTgtRef)) | |
606 | return theLstIndS.First(); | |
607 | ||
608 | // project tangent vector to the plane orthogonal to normal | |
609 | // to get the reference direction | |
610 | gp_XYZ aTgtRefXYZ = aNormal.XYZ().CrossCrossed (aTgtRef.XYZ(), aNormal.XYZ()); | |
611 | if (aTgtRefXYZ.SquareModulus() < 1e-14) | |
612 | // a problem with defining reference direction, take first way | |
613 | return theLstIndS.First(); | |
614 | aTgtRef = aTgtRefXYZ; | |
615 | ||
616 | // find the way with minimal angle to the reference direction | |
617 | // (the angle is in range ]-PI;PI]) | |
618 | Standard_Integer aResIndex = 0; | |
619 | NCollection_List<Standard_Integer>::Iterator aItI (theLstIndS); | |
620 | for (; aItI.More(); aItI.Next()) | |
621 | { | |
622 | Standard_Integer aIndS = aItI.Value(); | |
623 | ||
624 | aLink = getLink(aIndS); | |
625 | gp_Dir aTgt; | |
626 | if (!aHelper->GetFirstTangent (aLink, aTgt)) | |
627 | continue; | |
628 | ||
629 | gp_XYZ aTgtXYZ = aNormal.XYZ().CrossCrossed (aTgt.XYZ(), aNormal.XYZ()); | |
630 | if (aTgtXYZ.SquareModulus() < 1e-14) | |
631 | // skip a problem way | |
632 | continue; | |
633 | aTgt = aTgtXYZ; | |
634 | ||
635 | Standard_Real aAngle = aTgt.AngleWithRef(aTgtRef, aNormal); | |
c6541a0c D |
636 | if (aAngle < 1e-4 - M_PI) |
637 | aAngle = M_PI; | |
7fd59977 | 638 | if (aAngle < aAngleMin) |
639 | { | |
640 | aAngleMin = aAngle; | |
641 | aResIndex = aIndS; | |
642 | } | |
643 | } | |
644 | return aResIndex == 0 ? theLstIndS.First() : aResIndex; | |
645 | } | |
646 | ||
647 | //======================================================================= | |
648 | //function : Poly_MakeLoops2D | |
649 | //purpose : | |
650 | //======================================================================= | |
651 | ||
652 | Poly_MakeLoops2D::Poly_MakeLoops2D(const Standard_Boolean theLeftWay, | |
653 | const Helper* theHelper, | |
857ffd5e | 654 | const Handle(NCollection_BaseAllocator)& theAlloc) |
7fd59977 | 655 | : Poly_MakeLoops (theHelper, theAlloc), |
656 | myRightWay(!theLeftWay) | |
657 | { | |
658 | } | |
659 | ||
660 | //======================================================================= | |
661 | //function : Poly_MakeLoops2D::chooseLeftWay | |
662 | //purpose : | |
663 | //======================================================================= | |
664 | ||
665 | Standard_Integer Poly_MakeLoops2D::chooseLeftWay | |
666 | (const Standard_Integer /*theNode*/, | |
667 | const Standard_Integer theSegIndex, | |
668 | const NCollection_List<Standard_Integer>& theLstIndS) const | |
669 | { | |
c6541a0c | 670 | Standard_Real aAngleMin = M_PI * 2; |
7fd59977 | 671 | const Helper* aHelper = getHelper(); |
672 | Link aLink = getLink(theSegIndex); | |
673 | gp_Dir2d aTgtRef; | |
674 | if (!aHelper->GetLastTangent (aLink, aTgtRef)) | |
675 | // a problem with defining reference direction, take first way | |
676 | return theLstIndS.First(); | |
677 | ||
678 | // find the way with minimal angle to the reference direction | |
679 | // (the angle is in range ]-PI;PI]) | |
680 | Standard_Integer aResIndex = 0; | |
681 | NCollection_List<Standard_Integer>::Iterator aItI (theLstIndS); | |
682 | for (; aItI.More(); aItI.Next()) | |
683 | { | |
684 | Standard_Integer aIndS = aItI.Value(); | |
685 | ||
686 | aLink = getLink(aIndS); | |
687 | gp_Dir2d aTgt; | |
688 | if (!aHelper->GetFirstTangent (aLink, aTgt)) | |
689 | // skip a problem way | |
690 | continue; | |
691 | ||
692 | Standard_Real aAngle = aTgt.Angle(aTgtRef); | |
693 | if (myRightWay) | |
694 | aAngle = -aAngle; | |
c6541a0c D |
695 | if (aAngle < 1e-4 - M_PI) |
696 | aAngle = M_PI; | |
7fd59977 | 697 | if (aAngle < aAngleMin) |
698 | { | |
699 | aAngleMin = aAngle; | |
700 | aResIndex = aIndS; | |
701 | } | |
702 | } | |
703 | return aResIndex == 0 ? theLstIndS.First() : aResIndex; | |
704 | } |