нахождение граничных элементов в декартовых сетках


У меня есть 2D декартовой сетке (см. рисунок ниже). Красочные ячейки заполнены элемент. Я хотел бы обнаружить синие клетки. Синие клетки связаны элементы, если вы сканируете снизу вверх и слева направо, и наоборот.

enter image description here

Я написал следующий код, когда я делаю сканирование снизу, но я не знаю, что будет лучше на все четыре стороны сканирования. Я пытаюсь смоделировать на простом примере с 8 ячеек в направлении X и 5 ячеек в направлении y. Однако, реальная проблема заключается в порядок (10000 х 10000) клеток. Следующий код только найти две нижние синие клетки.

#include "stdafx.h"
#include <vector>
#include <set>

#include "iostream"

struct cell 
{
  cell(size_t i_x, size_t i_y)
    {
    x = i_x;
    y = i_y;
    }
  size_t x;
  size_t y;
  bool operator==(cell a)
    {
    if (a.x == x && a.y == y)
      return true;
    else
      return false;
    };
};



int main()
  {
  std::vector<cell> cartesian{ cell(0, 1), cell(0, 2), cell(0, 3),
    cell(1, 2), cell(1, 3), cell(1, 4), cell(1, 5), 
    cell(2, 1), cell(2, 2), cell(2, 3), cell(2, 4), cell(2, 5), 
    cell(3, 0), cell(3, 1), cell(3, 2), cell(3, 3), cell(3, 4), cell(3, 5), cell(3, 6), 
    cell(4, 2), cell(4, 3), cell(4, 4), cell(4, 5), cell(4, 6) };
  size_t max_X = 8;
  size_t max_Y = 5;


  std::vector<size_t> bound_elements;
  for (size_t i = 0; i < max_X; ++i)
    {
    bool found = false;
    for (size_t j = 0; j < max_Y; ++j)
      {
      auto is_filled = std::find(cartesian.begin(), cartesian.end(), cell(i, j));
      if (is_filled == cartesian.end())
        {
        continue;
        }
      size_t position = (j + (max_X* i));

      if (bound_elements.size() == 2)
        {
        bound_elements[1] = position;
        }
      else
        {
        bound_elements.push_back(position);
        }
      found = true;
      }
    if (found)
      {
      break;
      }
    }
  for (auto element : bound_elements)
    {
    std::cout  << element << std::endl;
    }
  return 0;
  }

Для сверху вниз, это просто противоположная сторона для итерации цикла. Эта стратегия кажется слишком многословным, есть ли лучший способ с точки зрения производительности или стиль написания?



237
4
задан 5 марта 2018 в 11:03 Источник Поделиться
Комментарии
1 ответ

Заголовки

Мне пришлось угробить нестандартных и отсутствует "stdafx.h"добавить <algorithm> и исправить орфографию <iostream> для компиляции этого.

Правильно std::size_t

Этот тип последовательно записывается как size_t без префикса пространства имен, которые не портативный.

Тип клетки

struct cell может быть просто std::pairно там может быть выгода более строгая типизация как у вас с этим. Я рекомендую вы предпочитаете инициализации членов, а не присваивания (и что удобно позволяет просто опускать конструктор). Мы можем также изменить == оператор взять ссылку и сделать это const (мы могли бы опереться std::tuple для реализации, но это, кажется, не стоит два человека и только один оператор).

struct cell
{
const std::size_t x;
const std::size_t y;

bool operator==(const cell& a) const { return a.x == x && a.y == y; }
};

Алгоритм

Неоднократно поиск элементов выглядит как очень трудоемкий способ изучения каждой клетке. Вместо этого мы можем просто перебирать известные клетки и изменять минимумы и максимумы для соответствующей строки и столбца:

#include <iostream>
#include <map>
#include <set>
#include <utility>
#include <vector>

struct cell
{
const std::size_t x;
const std::size_t y;
};

int main()
{
std::vector<cell> cartesian = {
{0, 1}, {0, 2}, {0, 3},
{1, 2}, {1, 3}, {1, 4}, {1, 5},
{2, 1}, {2, 2}, {2, 3}, {2, 4}, {2, 5},
{3, 0}, {3, 1}, {3, 2}, {3, 3}, {3, 4}, {3, 5}, {3, 6},
{4, 2}, {4, 3}, {4, 4}, {4, 5}, {4, 6}
};

// map each row and column to (min,max) filled cell in that column
std::map<std::size_t, std::pair<std::size_t,std::size_t>> row_range;
std::map<std::size_t, std::pair<std::size_t,std::size_t>> column_range;

for (const auto& c: cartesian) {
auto rit = row_range.find(c.y);
if (rit != row_range.end()) {
auto& row = rit->second;
if (c.x < row.first) {
row.first = c.x;
} else if (row.second < c.x) {
row.second = c.x;
}
} else {
row_range.insert({c.y, {c.x, c.x}});
}

auto cit = column_range.find(c.x);
if (cit != column_range.end()) {
auto& col = cit->second;
if (c.y < col.first) {
col.first = c.y;
} else if (col.second < c.y) {
col.second = c.y;
}
} else {
column_range.insert({c.x, {c.y, c.y}});
}
}

// show the results for column 0
const auto zr = column_range[0];

std::cout << zr.first << ',' << zr.second << std::endl;
}

Мы можем отрефакторить часть, которая является общей для строк и столбцов в небольшой вспомогательный метод:

using range_map = std::map<std::size_t, std::pair<std::size_t,std::size_t>>;

static void update_min_max(range_map& ranges, std::size_t index,
std::size_t value)
{
auto it = ranges.find(index);
if (it != ranges.end()) {
auto& range = it->second;
if (value < range.first) {
range.first = value;
} else if (range.second < value) {
range.second = value;
}
} else {
ranges.insert({index, {value, value}});
}
}

И тогда цикл будет

    range_map row_range;
range_map column_range;

for (const auto& c: cartesian) {
update_min_max(row_range, c.y, c.x);
update_min_max(column_range, c.x, c.y);
}

5
ответ дан 5 марта 2018 в 03:03 Источник Поделиться