marchingsquares.hh 2.86 KB
Newer Older
1
2
3
#ifndef RADIX_RADIXALGORITHM_MARCHINGSQUARES_HH_
#define RADIX_RADIXALGORITHM_MARCHINGSQUARES_HH_

4
5
6
#include <limits>
#include <memory>
#include <numeric>
7
8
#include <vector>

9
10
#include "radixbug/bug.hh"

11
12
namespace radix
{
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
template <typename data_type>
class MarchingSquares
{
 protected:
  std::vector<data_type> mData;
  std::vector<int> mBit;
  std::vector<int> mComponent;
  size_t mRows;
  size_t mColumns;

  enum class StepDirection
  {
    Up,
    Down,
    Right,
    Left,
    None
  };
  StepDirection next_step;
  StepDirection prev_step;
  /**
   * @brief starting_point find a starting position which matches or exceeds
   * isovalue
   * @param pos std::pair<size_t, size_t> <row, column> aka <y index, xindex>
   * @return bool true if a position was found
   */
  bool starting_point(std::pair<size_t, size_t>& pos) const;
  /**
   * @brief step Performs a step in the march
   * @param r row aka y index
   * @param c column aka x index
   */
  void step(size_t r, size_t c);
  bool accepts(size_t r, size_t c) const;

  void union_coords(size_t r1, size_t c1, size_t r2, size_t c2)
  {
    size_t first  = mColumns * c1 + r1;
    size_t second = mColumns * c2 + r2;
    if (r2 < mRows && c2 < mColumns && mBit[first] && mBit[second])
      do_union(int(first), int(second));
  }
  void do_union(int a, int b)
  {
    // get the root component of a and b, and set the one's parent to the other
    while (mComponent[a] != a) a = mComponent[a];
    while (mComponent[b] != b) b = mComponent[b];
    mComponent[b] = a;
  }

 public:
  /**
   * @brief MarchingSquares
   * @param data const std::vector<data_type> 1D representation of 2D data
   * @param rows number of rows, aka y size
   * @param columns number of columns, aka x size
   */
  MarchingSquares(const std::vector<data_type>& data, size_t rows,
                  size_t columns)
      : mData(data)
      , mBit(data.size(), 0)
      , mComponent(data.size())
      , mRows(rows)
      , mColumns(columns)
  {
    radix_line("MarchingSquares data size(" << data.size() << ")");
    radix_check(data.size() == (rows * columns));
  }

  /**
   * @brief march March the data on the isovalue threshold. Can be called
   * multiple times for multiple grouping at threshold.
   * @param isovalue the threshold value of the data
   * @param wash_bit the value that replace all data matchings isovalue
   * @param wash_threshold the threshold to which washing shouldn't apply.
   * Primary use in multi-contour requests.
   * @return std::vector<std::pair<int,int>> listing of all x,y indices, aka
   * a closed polygon
   */
  std::vector<std::pair<int, int>> march(
      data_type isovalue, data_type wash_bit = {0},
      data_type wash_threshold = std::numeric_limits<data_type>::max());
};  // class
96
97
98
99
100
}  // namespace

/** Include implementation file */
#include "radixalgorithm/marchingsquares.i.hh"
#endif /**  RADIX_RADIXALGORITHM_MARCHINGSQUARES_HH_ */