# finding boundary elements in cartesian grid

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. 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 = 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?

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

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

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

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