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.

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.

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.

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

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.

Open in new window