Check the nearest rectangles

Question

Description

Suppose the coordinates of 4 side of a rectangle denoted by (x1,y1), (x2,y2),(x3,y3) and (x4,y4). Like this image-

And I have a set of coordinates of 100000 rectangles saved in a txt file. For example here are the values of coordinates of 16 rectangles generated by my code-

#Rect    x1      y1      x2       y2        x3        y3      x4     y4        area

1     0.0000   0.0000   0.8147   0.0000   0.8147   0.1355   0.0000   0.1355   0.1104
2     0.8147   0.0000   1.0000   0.0000   1.0000   0.1355   0.8147   0.1355   0.0251
3     0.8147   0.1355   0.9058   0.1355   0.9058   0.8350   0.8147   0.8350   0.0637
4     0.0000   0.1355   0.1270   0.1355   0.1270   0.9689   0.0000   0.9689   0.1058
5     0.9058   0.1355   0.9134   0.1355   0.9134   0.2210   0.9058   0.2210   0.0006
6     0.9058   0.8350   1.0000   0.8350   1.0000   1.0000   0.9058   1.0000   0.0155
7     0.8147   0.8350   0.9058   0.8350   0.9058   1.0000   0.8147   1.0000   0.0150
8     0.1270   0.1355   0.6324   0.1355   0.6324   0.3082   0.1270   0.3082   0.0873
9     0.1270   0.9689   0.8147   0.9689   0.8147   1.0000   0.1270   1.0000   0.0214
10    0.0000   0.9689   0.1270   0.9689   0.1270   1.0000   0.0000   1.0000   0.0040
11    0.9134   0.1355   1.0000   0.1355   1.0000   0.2210   0.9134   0.2210   0.0074
12    0.9134   0.2210   1.0000   0.2210   1.0000   0.8350   0.9134   0.8350   0.0532
13    0.9058   0.2210   0.9134   0.2210   0.9134   0.8350   0.9058   0.8350   0.0047
14    0.6324   0.1355   0.8147   0.1355   0.8147   0.3082   0.6324   0.3082   0.0315
15    0.6324   0.3082   0.8147   0.3082   0.8147   0.9689   0.6324   0.9689   0.1205
16    0.1270   0.3082   0.6324   0.3082   0.6324   0.9689   0.1270   0.9689   0.3339

These coordinates splits an unit square into sub-rectangles like this picture-

Examples of Nearest Rectangles

In the above picture the nearest rectangles for rectangle# 3 are- 9,15,14,1,2,5,13,6 and 7.

For rectangle# 9 they are- 10,4,16,15,3 and 7.

My Problem

Now I would like to calculate the number of nearest rectangles for each of the rectangles using c/c++. How can I do it?

Edit:Based on the responses

#include <iostream>
#include <vector>
#include <fstream>

using namespace std;


struct Rectangle {
    double x1, y1;
    double x2, y2;
    double x3, y3;
    double x4, y4;
};




vector<double> get_touching_rectangles(Rectangle base, vector<Rectangle> rectangles) {


    for (auto it = rectangles.begin(); it != rectangles.end(); it++) {
        Rectangle other = *it;
        if (base == other) {
            continue; // This is our rectangle... skip it
        }
        // Top or bottom
        if ((other.x2 >= base.x1 && other.x1 <= base.x2) && (other.y1 == base.y3 || other.y3 == base.y1)) {
            ret.push_back(other);
            continue;
        }
        // Left or right
        if ((other.y3 >= base.y2 && other.y2 <= base.y3) && (other.x1 == base.x3 || other.x3 == base.x1)) {
            ret.push_back(other);
            continue;
        }
    }
    return ret;
}

int main(int argc, char const *argv[])
{
vector<Rectangle> rectangles;

//parse_txt_file(file, &rectangles); // Or whateer I need to do to parse that .txt file
ifstream inputFile;
inputFile.open("RectCoordinates.txt");

//std::vector<Rectangle> touching = 
get_touching_rectangles(rectangles.at(2) /* Rectangle #3 */, rectangles);

 inputFile.close();
    return 0;
}

Ok I write the above code based on the responses. But it is showing the following error-

    g++ -std=c++11 st5.cpp -o ssst5.cpp: In function ‘std::vector<double> get_touching_rectangles(Rectangle, std::vector<Rectangle>)’:
    st5.cpp:23:21: error: no match for ‘operator==’ in ‘base == other’
    st5.cpp:23:21: note: candidates are:
    In file included from /usr/include/c++/4.7/iosfwd:42:0,
                     from /usr/include/c++/4.7/ios:39,
                     from /usr/include/c++/4.7/ostream:40,
                     from /usr/include/c++/4.7/iostream:40,
                     from st5.cpp:1:
    /usr/include/c++/4.7/bits/postypes.h:218:5: note: template<class _StateT> bool std::operator==(const std::fpos<_StateT>&, const std::fpos<_StateT>&)
    /usr/include/c++/4.7/bits/postypes.h:218:5: note:   template argument deduction/substitution failed:

st5.cpp:28:13: error: ‘ret’ was not declared in this scope
st5.cpp:33:13: error: ‘ret’ was not declared in this scope
st5.cpp:37:12: error: ‘ret’ was not declared in this scope

What am I doing wrong?

Answer 1

Invert the problem. When you are generating the rectangles maintain a set J of n-tuples (where n varies between 2 and 4) which denote the 'junction points' ie the corner of 2, 3 or 4 rectangles meeting. For your picture above {1,4} would denote the (left) corner of rectangles 1 and 4, {1,4,8} denote the corner of rectangles 1, 4 and 8. There are 25 such n-tuples for your picture.

When you want to perform nearest rectangle query for rectangle R, you need to find all occurrences of R in J, which is easy if you organise elements of J into equivalence classes based on the relation 'rectangle R appears in the n-tuple' and index a vector with the rectangle number. Then looking up the neighbours of R is O(1).