Guest User

Untitled

a guest
Jul 21st, 2018
166
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.16 KB | None | 0 0
  1. public List<Pixel> FindBoundary()
  2. {
  3. Pixel hole_pixel;
  4. // note that _image (pixel-matrix) is supplied when creating the class object.
  5. for (int i = 0; i < _image.LenX; i++)
  6. for (int j = 0; j < _image.LenY; j++)
  7. {
  8. hole_pixel = _image.GetArrayElement(i, j);
  9. if (hole_pixel.Value == -1)
  10. // while goto statements are not highly approved of, as they create hard-to-read spaghetti code,
  11. // this (breaking out of nested loops) is one of the rare cases where they should be used,
  12. // as they are more coherent than setting up multiple flags, or using sub-methods that will return.
  13. goto Hole_Exists;
  14. }
  15.  
  16. // if here - no hole was found, simply return null
  17. return null;
  18.  
  19. Hole_Exists:
  20. _boundary = new List<Pixel>();
  21.  
  22. // priming the loop
  23. var first = GetClockWisePixel(hole_pixel);
  24. _boundary.Add(first);
  25.  
  26. var boundary_pixel = GetClockWisePixel(hole_pixel);
  27.  
  28. // stop condition:
  29. // A. reach the same first pixel we started from
  30. // B. in cases of enclaves with 1 space gap, this might cause a premature stop
  31. // we can make sure we are reaching it while completeing the full circle of the circle-wise turning
  32. // i.e. that the turning index (_8i) == 0 (minus the extra step that is taken)
  33. // (also called Jacob's stopping criteria)
  34.  
  35. while (!(boundary_pixel == first && _8i - 1 == 0))
  36. {
  37. if (boundary_pixel.Value != -1)
  38. {
  39. if (!_boundary.Contains(boundary_pixel))
  40. _boundary.Add(boundary_pixel);
  41. }
  42. else
  43. {
  44. Backtrack();
  45. hole_pixel = boundary_pixel;
  46. }
  47. boundary_pixel = GetClockWisePixel(hole_pixel);
  48. }
  49.  
  50. return _boundary;
  51. }
  52.  
  53. // +---+---+---+
  54. // | 1 | 2 | 3 |
  55. // |nw | n |ne |
  56. // +---+---+---+
  57. // | 0 | | 4 |
  58. // | w | | e |
  59. // +---+---+---+
  60. // | 7 | 6 | 5 |
  61. // |sw | s |se |
  62. // +---+---+---+
  63.  
  64. private int[,] _8connected = new int[,] {
  65. {0, -1}, // 0 = w
  66. {-1, -1}, // 1 = nw
  67. {-1, 0}, // 2 = n
  68. {-1, 1}, // 3 = ne
  69. {0, 1}, // 4 = e
  70. {1, 1}, // 5 = se
  71. {1, 0}, // 6 = s
  72. {1, -1}, // 7 = sw
  73. };
  74.  
  75. private int _8i = 0; // index to keep where are we in the clock-wise clock
  76. // 0 - w, 1 - nw, 2 - n, 3 - ne, 4 - e, 5 - se, 6 - s, 7 - sw
  77.  
  78. private Pixel GetClockWisePixel(Pixel input)
  79. {
  80. int new_x, new_y;
  81. do
  82. {
  83. var x_offset = _8connected[_8i, 0];
  84. var y_offset = _8connected[_8i, 1];
  85.  
  86. _8i = (_8i + 1) % 8;
  87.  
  88. new_x = input.Xi + x_offset;
  89. new_y = input.Yi + y_offset;
  90. }
  91. // if edge pixels, move to next clockwise
  92. while (new_x < 0 || new_x >= _image.LenX || new_y < 0 || new_y >= _image.LenY);
  93.  
  94. return _image.GetArrayElement(new_x, new_y);
  95. }
  96.  
  97. private void Backtrack()
  98. {
  99. // We want to go back to the last connected pixel we were in.
  100. // The return position might seem at first a bit redundant, as it returns us to a pixel already covered
  101. // it's crucial for the stop condition in certain cases... If we wouldn't mind missing enclaves
  102. // we could return one less to the next connected pixel not yet covered, though remove Jacob's criteria...
  103.  
  104. // There can be 2 cases where a new hole pixel was found in:
  105. // diagonal - we will want to go counter clock 3 (+1 of the already advanced _8i) = -4 = +4
  106. // _8i index will be +1, i.e. 2,4,6 or 0
  107. // straight - we will want to go counter clock 2 (+1 of the already advanced _8i) = -3 = +5
  108. // _8i index will be +1, i.e. 1,3,5 or 7
  109.  
  110. if (_8i % 2 == 1)
  111. _8i = (_8i + 5) % 8;
  112. else
  113. _8i = (_8i + 4) % 8;
  114. }
Add Comment
Please, Sign In to add comment