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

Open in new window

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
phoffricAsked:
Who is Participating?
 
ozoCommented:
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;
  }

Open in new window

0
 
phoffricAuthor 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
 
phoffricAuthor 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
Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

 
phoffricAuthor 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
 
ozoCommented:
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;
      }
  }

Open in new window

0
 
phoffricAuthor 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.

All Courses

From novice to tech pro — start learning today.