4
\$\begingroup\$

I have a 2D cartesian grid (see picture below). The colorful cells are filled element. I would like to detect blue cells. Blue cells are bound elements if you scan from bottom to top and left to right and vice versa.

enter image description here

I wrote following code when I do scan from bottom, but I do not know what would be the best for all four side scanning. I try to simulate on the simple example below with 8 cells in x direction and 5 cells in y direction. However, the real problem is order of (10000 x 10000) cells. The following code only find the two bottom blue cells.

#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;
  }

For top to down It is just opposite side for loop iteration. This strategy seems to be too verbose, is there a better way in terms of performance or coding style?

\$\endgroup\$
10
  • \$\begingroup\$ Is that formatting of braces on purpose? \$\endgroup\$ – Raimund Krämer Mar 5 '18 at 11:14
  • \$\begingroup\$ @RaimundKrämer Looks a bit like Whitesmiths indendation but maybe it just got mangled. \$\endgroup\$ – yuri Mar 5 '18 at 11:24
  • 2
    \$\begingroup\$ Welcome to Code Review! You'll receive better reviews if you show a complete example. For example, I recommend that you edit to show the necessary #include lines, and a main() that shows how to call your function. It can really help reviewers if they are able to compile and run your program. \$\endgroup\$ – Toby Speight Mar 5 '18 at 11:25
  • \$\begingroup\$ I edited as you said \$\endgroup\$ – user2090491 Mar 5 '18 at 13:09
  • \$\begingroup\$ My question is matter of algorithm more. \$\endgroup\$ – user2090491 Mar 5 '18 at 13:11
5
\$\begingroup\$

Headers

I had to ditch the non-standard and missing "stdafx.h", add <algorithm> and fix the spelling of <iostream> to compile this.

Correct std::size_t

This type is consistently written as size_t without its namespace prefix, which is not portable.

Cell type

struct cell could simply be a std::pair, but there may be benefit to stronger typing as you have it. I recommend you prefer initialization of members rather than assignment (and that conveniently allows us to simply omit the constructor). We can also change the == operator to take a reference and make it const (we could lean on std::tuple for the implementation, but it doesn't seem worth it for two members and only one operator).

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; }
};

Algorithm

Repeatedly searching for elements looks like a very time-consuming way of examining every cell. Instead, we could just iterate over the known cells and update a set of minima and maxima for its row and column:

#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;
}

We can refactor the part that's common to rows and columns into a small helper method:

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}});
    }
}

And then the loop becomes

    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);
    }
\$\endgroup\$
7
  • \$\begingroup\$ I've updated so that it compiles with g++ -std=c++11 (and also my usual warnings: -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Weffc++). \$\endgroup\$ – Toby Speight Mar 5 '18 at 15:52
  • \$\begingroup\$ I would recomment to use std::tie for the comparison operator \$\endgroup\$ – miscco Mar 5 '18 at 18:54
  • \$\begingroup\$ @Is there a way to optimize your algorithm to the case that we do not need to fill the all rows and columns? I do kind of scanning from four sides (top to bottom, bottom to top, left to right and right to left). Blue cells are the boundary of first row or column when I do scanning. There is a possibility to query if the cells is colorful. \$\endgroup\$ – user2090491 Mar 6 '18 at 10:00
  • \$\begingroup\$ I don't quite understand what you're asking - do you mean that some rows and columns may be empty? If so, those rows/columns won't appear as keys in the corresponding range_map variables. \$\endgroup\$ – Toby Speight Mar 6 '18 at 10:54
  • \$\begingroup\$ @miscco, I considered that, but as I commented, it's longer and less clear for a single == operator with two members. \$\endgroup\$ – Toby Speight Mar 6 '18 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.