exciseLoops finds loops within the contour that do not include the start and end. Loops are removed from the contour and added to the contour set. Loop detection is performed by Johnson's algorithm for finding elementary cycles.
(conts contourSet, quick bool)
| 512 | // contour set. Loop detection is performed by Johnson's algorithm for |
| 513 | // finding elementary cycles. |
| 514 | func (c *contour) exciseLoops(conts contourSet, quick bool) { |
| 515 | if quick { |
| 516 | // Find cases we can guarantee don't need |
| 517 | // a complete analysis. |
| 518 | seen := make(map[point]struct{}) |
| 519 | var crossOvers int |
| 520 | for _, p := range c.backward { |
| 521 | if _, ok := seen[p]; ok { |
| 522 | crossOvers++ |
| 523 | } |
| 524 | seen[p] = struct{}{} |
| 525 | } |
| 526 | for _, p := range c.forward[:len(c.forward)-1] { |
| 527 | if _, ok := seen[p]; ok { |
| 528 | crossOvers++ |
| 529 | } |
| 530 | seen[p] = struct{}{} |
| 531 | } |
| 532 | switch crossOvers { |
| 533 | case 0: |
| 534 | return |
| 535 | case 1: |
| 536 | c.exciseQuick(conts) |
| 537 | return |
| 538 | } |
| 539 | } |
| 540 | |
| 541 | wp := append(c.backward.reverse(), c.forward...) |
| 542 | g := graphFrom(wp) |
| 543 | cycles := cyclesIn(g) |
| 544 | if len(cycles) == 0 { |
| 545 | // No further work to do but clean up after ourselves. |
| 546 | // We should not have reached here. |
| 547 | c.backward.reverse() |
| 548 | return |
| 549 | } |
| 550 | delete(conts, c) |
| 551 | |
| 552 | // Put loops into the contour set. |
| 553 | for _, cyc := range cycles { |
| 554 | loop := wp.subpath(cyc) |
| 555 | conts[&contour{ |
| 556 | z: c.z, |
| 557 | backward: loop[:1:1], |
| 558 | forward: loop[1:], |
| 559 | }] = struct{}{} |
| 560 | } |
| 561 | |
| 562 | // Find non-loop paths and keep them. |
| 563 | g.remove(cycles) |
| 564 | paths := wp.linearPathsIn(g) |
| 565 | for _, p := range paths { |
| 566 | conts[&contour{ |
| 567 | z: c.z, |
| 568 | backward: p[:1:1], |
| 569 | forward: p[1:], |
| 570 | }] = struct{}{} |
| 571 | } |