finding boundary elements in cartesian grid

Question

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?

• Raimund Krämer: Is that formatting of braces on purpose?
• yuri: @RaimundKrämer Looks a bit like Whitesmiths indendation but maybe it just got mangled.
• Toby Speight: 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.
• user2090491: I edited as you said
• user2090491: My question is matter of algorithm more.

Answer 1

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

• Toby Speight: 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++).
• miscco: I would recomment to use std::tie for the comparison operator
• user2090491: @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.
• Toby Speight: 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.
• Toby Speight: @miscco, I considered that, but as I commented, it's longer and less clear for a single == operator with two members.