# Identify missing grid points for a given set of points using C++03 STD LIB

C++03 using VS 2010. (Assume no boost available.)

I would like to find the missing points in the below diagram using C++03 std lib. The x's represent a set of given points, and the o's are the missing points.

``````x----o--x----x---o
|    |  |    |   |
o----o--x----o---x
|    |  |    |   |
o----x--x----o---x
|    |  |    |   |
x----o--x----o---o
|    |  |    |   |
x----x--o----o---o
|    |  |    |   |
o----o--x----o---o
``````
I am given a set of points Pi = (Xi, Yi). The coordinates are of type double. If I were to draw a grid (consisting of horizontal and vertical lines) going though every point, I may have some missing points as shown above.

The result should be a std container having the (X, Y) points that are missing.

I suspect that http://www.cplusplus.com/reference/algorithm/set_difference/ or some variation might be useful. So getting the entire list of potential points somehow is probably also useful. Although speed is always a plus, it is not essential.

Any code suggestions?

BTW - there are NOT going to be any tricky points - like a point very far away from the main set of points.
BTW - I've been using axis indices to represent the actual axis coordinate values (but don't worry about that if it complicates the code).

I can probably do this using brute force using a 2D array; so the purpose of this question is to use std lib algorithm functions to simplify the code and hopefully improve performance.
LVL 33
###### Who is Participating?

Commented:
``````std::set<std::pair<int,int> > Pi;
std::set<int>Xi;
std::set<int>Yi;
std::set<std::pair<int,int> >XY;
for( std::set<std::pair<int,int> >::iterator i=Pi.begin(); i!=Pi.end(); ++i ){
Xi.insert(i->first);
Yi.insert(i->second);
XY.insert(*i);
}
std::set<std::pair<int,int> > missing;
for( std::set<int>::iterator x=Xi.begin(); x!=Xi.end(); ++x ){
for( std::set<int>::iterator y=Yi.begin(); y!=Yi.end(); ++y ){
std::pair<int,int>p(*x,*y);
if( XY.count(p)==0 ){
missing.insert(p);
}
}
}
for( std::set<std::pair<int,int> >::iterator i=missing.begin(); i!=missing.end(); ++i ){
std::cout << i->first << ", " << i->second << std::endl;
}
``````
0

Author Commented:
Yesterday I created the matrix initialized with magic numbers representing the o's. I then filled the known points at first using sets similar to what you did but then used vectors instead followed by sorts on Xi and Yi - was much faster.

Today I was planning on identifing the list of missing points from the magic numbers.
I was hoping that your lines 10 to 18 could be replaced with algorithm functions rather than double loops. I will be thinking about that today when I get to work.

I am using doubles instead of int. I would be surprised that lines 8 and 15 even compiled as written.
0

Author Commented:
>> I would be surprised that lines 8 and 15 even compiled as written.
Well, I would because when I used a struct of two doubles instead of a pair, I had to define operator<, which I see is defined for std::pair (as well as other convenient operators).
0

Author Commented:
Any way to change nested for loops into a single loop or better, to remove the nested loop entirely by using STL functions?
0

Commented:
You might change the nested loops to nested std::transform's, which could hide, but not entirely remove the loops.

Or, you might change the 2 nested loops into 3 unnested loops, with only one of the loops being explicit
``````  std::vector<int> X( Xi.begin(), Xi.end() );
std::vector<int> Y( Yi.begin(), Yi.end() );
for( int i = 0; i < X.size() * Y.size(); ++i )
{
std::pair<int,int> p( X[i/Y.size()], Y[i%Y.size()] );
if( XY.count(p) == 0 ) {
std::cout << p.first << ", " << p.second << std::endl;
}
}
``````
0

Author Commented:
Thank you.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.