marchingsquares.i.hh 15.2 KB
Newer Older
1

2
#include <queue>
3
#include <set>
4
5
#include <vector>

6
#include "radixalgorithm/marchingsquares.hh"
7
#include "radixalgorithm/ordering.hh"
8
9
10
11
#include "radixbug/bug.hh"

namespace radix
{
12
template <typename data_type>
13
14
15
void MarchingSquares<data_type>::clear_connected_component(int row, int col,
                                                           size_t label,
                                                           data_type wash_bit)
16
{
17
18
19
20
21
  if (row < 0 || row == mColumns) return;  // out of bounds
  if (col < 0 || col == mRows) return;     // out of bounds
  std::set<size_t> list;
  list.insert(mColumns * row + col);
  while (!list.empty())
22
  {
23
24
25
26
27
28
29
30
    const auto& it = list.begin();
    size_t c_i     = *it;

    // update the row
    row = c_i / mColumns;
    // upate the column
    col = c_i % mColumns;
    // clear data
31
    mBit[c_i]  = 0;
32
33
    mData[c_i] = wash_bit;
    // search neighbors
34
    for (int direction = 0; direction < 4; ++direction)
35
    {
36
37
38
39
      int nc = col + dx[direction];
      int nr = row + dy[direction];
      if (nc < 0 || nc >= mColumns) continue;  // out of bounds
      if (nr < 0 || nr >= mRows) continue;     // out of bounds
40
41
42
43
44
45
46
47
48
49
      size_t nc_i = mColumns * nr + nc;
      if (mBit[nc_i] == label)
      {
        // if we already have this cell in the list to look at
        // don't add it again
        if (list.find(nc_i) == list.end())
        {
          list.insert(nc_i);
        }
      }
50
    }
51
    list.erase(it);
52
53
54
  }
}

55
56
template <typename data_type>
std::vector<std::pair<int, int>> MarchingSquares<data_type>::march(
57
    data_type isovalue, data_type wash_bit, data_type wash_threshold)
58
{
59
60
  std::pair<size_t, size_t> start;
  std::vector<std::pair<int, int>> out;
61
62

  //
63
64
  // Get a starting point first, because if there isn't a place to start
  // then we don't care about going any further
65
  if (starting_point(isovalue, wash_threshold, start) == false)
66
  {
67
68
69
70
71
72
73
74
75
    radix_tagged_line("Did not find a starting point.");
    // return empty listing
    return out;
  }

  radix_tagged_line("Starting point[" << start.first << "," << start.second
                                      << "]");
  //
  // Initialize bit field
76
77
78

  size_t data_size = mData.size();
  for (size_t p_i = 0; p_i < data_size; ++p_i)
79
80
  {
    // select data as 1 if greater than isovalue
81
    data_type value = mData[p_i];
82
    if (value >= isovalue && value < wash_threshold)
83
    {
84
      mBit[p_i] = 1;
85
    }
86
    else if (value >= wash_threshold)
87
    {
88
      mBit[p_i] = 2;
89
    }
90
  }
91
92
93
94

  //
  // Walk the perimeter
  size_t row = start.first, column = start.second;
95
  radix_tagged_line("Starting (" << row << ", " << column << ")");
96
97
98
99
100
  do
  {
    step(row, column);
    // If our current point is within our image
    // add it to the list of points
101
102
103
    // We have to allow for row and column being equal to the number
    // of rows and columns to allow for traveling the boundaries
    if (column >= 0 && column <= mColumns && row >= 0 && row <= mRows)
104
    {
105
      out.push_back({row, column});
106
    }
107
108

    switch (next_step)
109
    {
110
111
112
113
114
115
116
117
118
119
120
121
122
123
      case StepDirection::Up:
        --row;
        break;
      case StepDirection::Left:
        --column;
        break;
      case StepDirection::Down:
        ++row;
        break;
      case StepDirection::Right:
        ++column;
        break;
      default:
        break;
124
    }
125
126
  } while (row != start.first || column != start.second);

127
128
129
130
  //
  // Finish connecting the contour by making the last=first
  out.push_back(start);

131
132
133
  clear_connected_component(start.first, start.second,
                            mBit[mColumns * start.first + start.second],
                            wash_bit);
134

135
136
137
138
139
  return out;
}  // march

template <typename data_type>
bool MarchingSquares<data_type>::starting_point(
140
    data_type isovalue, data_type wash_threshold,
141
142
    std::pair<size_t, size_t>& pos) const
{
143
144
  size_t data_size = mData.size();
  for (size_t i = 0; i < data_size; ++i)
145
  {
146
    data_type value = mData[i];
147
    if (value >= isovalue && value < wash_threshold)
148
149
150
151
152
153
154
155
156
157
    {
      // save the row
      pos.first = i / mColumns;
      // save the column
      pos.second = i % mColumns;
      return true;
    }
  }
  return false;
}
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

template <typename data_type>
bool MarchingSquares<data_type>::starting_point(
    short label, std::pair<size_t, size_t>& pos,
    std::pair<size_t, size_t> prev) const
{
  size_t data_size = mBit.size();
  size_t starti    = mColumns * prev.first + prev.second;
  for (size_t i = starti; i < data_size; ++i)
  {
    short value = mBit[i];
    if (value == label)
    {
      // save the row
      pos.first = i / mColumns;
      // save the column
      pos.second = i % mColumns;
      return true;
    }
  }
  return false;
}
180
181
182
183
184
185
186
template <typename data_type>
bool MarchingSquares<data_type>::accepts(size_t r, size_t c) const
{
  // Make sure we don't pick a point out of bounds
  if (c < 0 || r < 0 || c >= mColumns || r >= mRows) return false;

  // Check the data value
187
  if (mBit[mColumns * r + c] == 1) return true;
188
189
190
191
192
193

  return false;
}

template <typename data_type>
void MarchingSquares<data_type>::step(size_t r, size_t c)
194
195
196
197
198
199
200
{
  // step using the default label of 1
  step(r, c, 1);
}

template <typename data_type>
void MarchingSquares<data_type>::step(size_t r, size_t c, short label)
201
202
203
204
205
206
{
  //
  // The meat of the marching squares algorithm
  // See https://en.wikipedia.org/wiki/Marching_squares
  // for specifics on the algorithm
  // upper relations
207
208
  bool u_left  = accepts(r - 1, c - 1, label);
  bool u_right = accepts(r - 1, c, label);
209
  // lower relations
210
211
  bool l_left  = accepts(r, c - 1, label);
  bool l_right = accepts(r, c, label);
212
213
214
215
216
217

  prev_step = next_step;
  int state = 0;

  if (u_left) state |= 1;
  if (u_right) state |= 2;
218
219
  if (l_right) state |= 4;
  if (l_left) state |= 8;
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
  // State now contains a number between 0 and 15
  // representing our state.
  // In binary, it looks like 0000-1111 (in binary)

  // An example. Let's say the top two pixels are filled,
  // and the bottom two are empty.
  // Stepping through the if statements above with a state
  // of 0b0000 initially produces:
  // upper Left == true ==>  0b0001
  // upper Right == true ==> 0b0011
  // The others are false, so 0b0011 is our state
  // (That's a result 3)

  // Looking at the chart above, we see that state
  // corresponds to a move right, so in our switch statement
  // below, we add a case for 3, and assign Right as the
  // direction of the next step. We repeat this process
  // for all 16 states.

  // So we can use a switch statement to determine our
  // next direction based on
  switch (state)
  {
    case 1:
244
      next_step = StepDirection::Left;
245
246
      break;
    case 2:
247
      next_step = StepDirection::Up;
248
249
      break;
    case 3:
250
      next_step = StepDirection::Left;
251
252
      break;
    case 4:
253
      next_step = StepDirection::Right;
254
255
      break;
    case 5:
256
      if (prev_step == StepDirection::Down)
257
        next_step = StepDirection::Right;
258
      else
259
260
261
262
        next_step = StepDirection::Left;
      break;
    case 6:
      next_step = StepDirection::Up;
263
264
      break;
    case 7:
265
      next_step = StepDirection::Left;
266
267
268
269
270
271
272
      break;
    case 8:
      next_step = StepDirection::Down;
      break;
    case 9:
      next_step = StepDirection::Down;
      break;
273
    case 10:
274
275
276
      if (prev_step == StepDirection::Left)
        next_step = StepDirection::Down;
      else
277
278
279
280
        next_step = StepDirection::Up;
      break;
    case 11:
      next_step = StepDirection::Down;
281
282
      break;
    case 12:
283
      next_step = StepDirection::Right;
284
285
      break;
    case 13:
286
      next_step = StepDirection::Right;
287
288
      break;
    case 14:
289
      next_step = StepDirection::Up;
290
291
292
293
      break;
    default:
      next_step = StepDirection::None;
      break;
294
  }
295
296
297
298
299
300
301
302
303

  radix_tagged_line(
      "(" << r << ", " << c << ") =" << state << " "
          << ((next_step == StepDirection::Up)
                  ? "Up"
                  : ((next_step == StepDirection::Down)
                         ? "Down"
                         : (next_step == StepDirection::Left) ? "Left"
                                                              : "Right")));
304
}
305
306
307
308
309
310
311
312
template <typename data_type>
bool MarchingSquares<data_type>::accepts(size_t r, size_t c, short label) const
{
  // Make sure we don't pick a point out of bounds
  if (c < 0 || r < 0 || c >= mColumns || r >= mRows) return false;

  // Check the data value
  if (mBit[mColumns * r + c] >= label) return true;
313

314
315
316
317
  return false;
}
template <typename data_type>
std::vector<std::vector<std::vector<std::pair<float, float>>>>
318
319
320
MarchingSquares<data_type>::march(const std::vector<data_type>& isovalues,
                                  size_t max_contour_polygons,
                                  size_t max_polygon_points)
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
{
  std::pair<size_t, size_t> start, prev;

  size_t isovalues_size = isovalues.size();
  // [isovalue i][polygon i][point i]
  std::vector<std::vector<std::vector<std::pair<float, float>>>> contours(
      isovalues_size);
  //
  // Determine order to ensure largest to smallest ordering
  // This ensures that we can deal with nested scenarios
  auto comparator          = [](data_type a, data_type b) { return (a > b); };
  std::vector<size_t> perm = sort_permutation(isovalues, comparator);
  // apply ordering so a > b > c > d ...
  std::vector<data_type> ordered_isovalues = isovalues;
  apply_permutation(ordered_isovalues, perm);

  //
  // Initialize bit field
  std::vector<size_t> label_counts(isovalues_size + 1, 0);
  size_t data_size = mData.size();
  for (size_t p_i = 0; p_i < data_size; ++p_i)
  {
    // select data as 1 if greater than isovalue
    data_type value = mData[p_i];
    for (size_t isoi = 0; isoi < isovalues_size; ++isoi)
    {
      if (value >= ordered_isovalues[isoi])
      {
        //
        // save the category (aka there are only number of isovalue categories)
        // specifically 1-N, 0 is background
        mBit[p_i] = isovalues_size - isoi;
        break;
      }
    }
  }
357
358
359
360
361
362
363
364
365
366

  typedef std::pair<float, float> Point;
  typedef std::vector<Point> Polygon;
  struct PolyComparator
  {
    bool operator()(const Polygon& a, const Polygon& b)
    {
      return a.size() < b.size();
    }
  };
367
368
369
370
371
372
373
374
375
376
377

  for (size_t isoi = 0; isoi < isovalues_size; ++isoi)
  {
    //
    // since we are using permutation as an interface, to ensure a > b
    // the label will be reversed to the size
    short label     = short(isovalues_size - isoi);
    size_t contouri = size_t(label - 1);
    //
    // Get a starting point first, because if there isn't a place to start
    // then we don't care about going any further for this isovalue
378

379
380
    // reset previous for each contour search
    prev = {0, 0};
381
    std::priority_queue<Polygon, std::vector<Polygon>, PolyComparator> pqueue;
382
383
384
385
    while (starting_point(label, start, prev))
    {
      prev = start;
      // we have a new polygon
386
      std::vector<std::pair<float, float>> polygon;
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403

      radix_tagged_line("Starting point("
                        << ordered_isovalues[isoi] << ") label (" << label
                        << ")[" << start.first << "," << start.second << "]");

      //
      // Walk the perimeter
      size_t row = start.first, column = start.second;
      do
      {
        step(row, column, label);
        // If our current point is within our image
        // add it to the list of points
        // We have to allow for row and column being equal to the number
        // of rows and columns to allow for traveling the boundaries
        if (column >= 0 && column <= mColumns && row >= 0 && row <= mRows)
        {
404
          polygon.push_back({row, column});
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
        }

        switch (next_step)
        {
          case StepDirection::Up:
            --row;
            break;
          case StepDirection::Left:
            --column;
            break;
          case StepDirection::Down:
            ++row;
            break;
          case StepDirection::Right:
            ++column;
            break;
          default:
            break;
        }
      } while (row != start.first || column != start.second);

      //
      // Finish connecting the contour by making the last=first
428
429
      polygon.push_back(start);
      pqueue.push(polygon);
430
431
432
433
434
435
436
437

      radix_tagged_line("clearing label ("
                        << mBit[mColumns * start.first + start.second]
                        << ") threshold (" << ordered_isovalues[isoi] << ")");

      clear_isovalue_label(start.first, start.second,
                           mBit[mColumns * start.first + start.second],
                           ordered_isovalues);
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
    }
    //
    // save the top N polygons
    size_t count = std::min(max_contour_polygons, pqueue.size());
    contours[contouri].resize(count);
    for (size_t i = 0; i < count; ++i)
    {
      auto& top      = pqueue.top();
      auto& cpolygon = contours[contouri][i];
      if (top.size() > max_polygon_points)
      {
        // std::cout << "Taking every other point given size(" << top.size()
        //          << ") exceeds " << max_polygon_points << std::endl;
        // take every other point
        size_t polygon_size = top.size() / 2;
        for (size_t pi = 0; pi < polygon_size; ++pi)
        {
          cpolygon.push_back(top[pi * 2]);
        }
      }
      else
      {
        cpolygon.resize(top.size());
        std::copy(top.begin(), top.end(), cpolygon.begin());
      }
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
    }
  }
  return contours;
}  // march

template <typename data_type>
void MarchingSquares<data_type>::clear_isovalue_label(
    int row, int col, short label,
    const std::vector<data_type>& ordered_isovalues)
{
  if (row < 0 || row == mColumns) return;  // out of bounds
  if (col < 0 || col == mRows) return;     // out of bounds

  std::set<size_t> list;
  list.insert(mColumns * row + col);
  size_t isovalues_size = ordered_isovalues.size();
  size_t isoi           = isovalues_size - size_t(label) + 1;
  while (!list.empty())
  {
    const auto& it = list.begin();
    size_t c_i     = *it;

    // update the row
    row = c_i / mColumns;
    // upate the column
    col = c_i % mColumns;
    // re-initilize bit field
    data_type value = mData[c_i];
    if (label > 1)  // not the last isovalue
    {
493
494
      // radix_tagged_line("Comparing " << value
      //                               << " >= " << ordered_isovalues[isoi]);
495
496
497
498
499
500
      if (value >= ordered_isovalues[isoi])
      {
        //
        // save the category (aka there are only number of isovalue categories)
        // specifically 1-N, 0 is background
        mBit[c_i] = label - 1;
501
502
503
        // radix_tagged_line("Found new isovalue (" << ordered_isovalues[isoi]
        //                                         << ") for [" << row << ","
        //                                         << col << "]");
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
      }
    }
    // we didn't find a lower level contour, so zero it out
    if (mBit[c_i] == label) mBit[c_i] = 0;
    // search neighbors
    for (int direction = 0; direction < 4; ++direction)
    {
      int nc = col + dx[direction];
      int nr = row + dy[direction];
      if (nc < 0 || nc >= mColumns) continue;  // out of bounds
      if (nr < 0 || nr >= mRows) continue;     // out of bounds
      size_t nc_i = mColumns * nr + nc;
      if (mBit[nc_i] == label)
      {
        // if we already have this cell in the list to look at
        // don't add it again
        if (list.find(nc_i) == list.end())
        {
          list.insert(nc_i);
        }
      }
    }
    list.erase(it);
  }
}
529
}  // namespace radix