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

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

\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
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.