Group similar fields

Question

I have a set of coordinates (X, Y) that split a unit square into sub-rectangles. Suppose my coordinates are

( x1, y1) ( x2, y2) (0.0000,0.0000) (0.3412,0.4175) (0.7445,0.0000) (1.0000,0.6553) (0.7445,0.6553) (1.0000,1.0000) (0.0000,0.6553) (0.7445,1.0000) (0.3412,0.0000) (0.7445,0.4175) (0.3412,0.4175) (0.7445,0.6553) (0.0000,0.4175) (0.3412,0.6553)....etc (total 10,000 coordinates) 

As an example, I took only 16 data sets, and these coordinates break my square like this:

Definition of a similar block

Those boxes that have the same number of neighbors are considered as similar fields. For the image above field [8], field [13] , etc. Has 4 nearest neighbor. Thus, they are considered as similar fields.

The following image should make it clear -

:: MY PROBLEM::

From the image we see -

The following fields are located in field [8] :

box (1) (which has 4 neighbors)

box [4] (which also has 4 neighbors)

field [14] (has 4 neighbors)

box [16] (has 4 neighbors)

So, in this case, the sum of the nearest nearest boxes = 4 + 4 + 4 + 4 = 16

Again for field [13], the closest fields are:

field [3] (which has 6 neighbors)

box [5] (which also has 4 neighbors)

field [6] (has 3 neighbors)

box [12] (has 3 neighbors)

So, in this case, the sum of the nearest neighboring squares = 6 + 4 + 3 + 3 = 16

And here is the total number of neighbors for boxes (similar boxes) [8] and field [13] = 16 + 16 = 32.

Similarly, I want to group all the boxes with 4 neighbors and find the sum of the neighbors of their closest boxes. And continue to work for each similar group.

My code

Here is my code.

 #include <iostream> #include <cstdlib> #include <vector> #include <stdio.h> using namespace std; class Rect { public: double x1, x2, y1, y2; // coordinates Rect(double X1, double Y1, double X2, double Y2) { if (X1 < X2) { x1 = X1; x2 = X2; } else { x2 = X1; x1 = X2; } if (Y1 < Y2) { y1 = Y1; y2 = Y2; } else { y2 = Y1; y1 = Y2; } } bool isAdjacent(Rect rect) { if (x1 == rect.x1 || x1 == rect.x2 || x2 == rect.x1 || x2 == rect.x2) { // use only < when comparing y1 and rect.y2 avoids sharing only a corner if (y1 >= rect.y1 && y1 < rect.y2) { return true; } if (y2 > rect.y1 && y2 <= rect.y2) { return true; } if (rect.y1 >= y1 && rect.y1 < y2) { return true; } if (rect.y2 > y1 && rect.y2 <= y2) { return true; } } if (y1 == rect.y1 || y1 == rect.y2 || y2 == rect.y1 || y2 == rect.y2) { if (x1 >= rect.x1 && x1 < rect.x2) { return true; } if (x2 > rect.x1 && x2 <= rect.x2) { return true; } if (rect.x1 >= x1 && rect.x1 < x2) { return true; } if (rect.x2 > x1 && rect.x2 <= x2) { return true; } } return false; } }; void isNearest(int b){ vector<Rect> rects; //Rect( x1 , y1 , x2 , y2 ) rects.push_back(Rect(0.0000,0.0000, 0.8147,0.1355)); rects.push_back(Rect(0.8147,0.0000, 1.0000,0.1355)); rects.push_back(Rect(0.8147,0.1355, 0.9058,0.8350)); rects.push_back(Rect(0.0000,0.1355, 0.1270,0.9689)); rects.push_back(Rect(0.9058,0.1355, 0.9134,0.2210)); rects.push_back(Rect(0.9058,0.8350, 1.0000,1.0000)); rects.push_back(Rect(0.8147,0.8350, 0.9058,1.0000)); rects.push_back(Rect(0.1270,0.1355, 0.6324,0.3082)); rects.push_back(Rect(0.1270,0.9689, 0.8147,1.0000)); rects.push_back(Rect(0.0000,0.9689, 0.1270,1.0000)); rects.push_back(Rect(0.9134,0.1355, 1.0000,0.2210)); rects.push_back(Rect(0.9134,0.2210, 1.0000,0.8350)); rects.push_back(Rect(0.9058,0.2210, 0.9134,0.8350)); rects.push_back(Rect(0.6324,0.1355, 0.8147,0.3082)); rects.push_back(Rect(0.6324,0.3082, 0.8147,0.9689)); rects.push_back(Rect(0.1270,0.3082, 0.6324,0.9689)); int nearBox_count = 0; double TotalArea=0; for (int x = 0; x < rects.size(); ++x) { if (rects[b].isAdjacent(rects[x])) { if (x==b) { continue; //this is our box , so do not count it. } nearBox_count++; printf("box[%d] is nearest to box[%d] \n", (b+1), (x+1)); } } printf("Total number of nearest box for [%d] is %d \n",(b+1),nearBox_count ); printf("\n"); } int main() { for (int i = 0; i < 16; ++i) { isNearest(i); } return 0; } 

It gives the correct result:

 box[1] is nearest to box[2] box[1] is nearest to box[4] box[1] is nearest to box[8] box[1] is nearest to box[14] Total number of nearest box for [1] is 4 box[2] is nearest to box[1] box[2] is nearest to box[3] box[2] is nearest to box[5] box[2] is nearest to box[11] Total number of nearest box for [2] is 4 box[3] is nearest to box[2] box[3] is nearest to box[5] box[3] is nearest to box[7] box[3] is nearest to box[13] box[3] is nearest to box[14] box[3] is nearest to box[15] Total number of nearest box for [3] is 6 box[4] is nearest to box[1] box[4] is nearest to box[8] box[4] is nearest to box[10] box[4] is nearest to box[16] Total number of nearest box for [4] is 4 box[5] is nearest to box[2] box[5] is nearest to box[3] box[5] is nearest to box[11] box[5] is nearest to box[13] Total number of nearest box for [5] is 4 box[6] is nearest to box[7] box[6] is nearest to box[12] box[6] is nearest to box[13] Total number of nearest box for [6] is 3 box[7] is nearest to box[3] box[7] is nearest to box[6] box[7] is nearest to box[9] box[7] is nearest to box[15] Total number of nearest box for [7] is 4 box[8] is nearest to box[1] box[8] is nearest to box[4] box[8] is nearest to box[14] box[8] is nearest to box[16] Total number of nearest box for [8] is 4 box[9] is nearest to box[7] box[9] is nearest to box[10] box[9] is nearest to box[15] box[9] is nearest to box[16] Total number of nearest box for [9] is 4 box[10] is nearest to box[4] box[10] is nearest to box[9] Total number of nearest box for [10] is 2 box[11] is nearest to box[2] box[11] is nearest to box[5] box[11] is nearest to box[12] Total number of nearest box for [11] is 3 box[12] is nearest to box[6] box[12] is nearest to box[11] box[12] is nearest to box[13] Total number of nearest box for [12] is 3 box[13] is nearest to box[3] box[13] is nearest to box[5] box[13] is nearest to box[6] box[13] is nearest to box[12] Total number of nearest box for [13] is 4 box[14] is nearest to box[1] box[14] is nearest to box[3] box[14] is nearest to box[8] box[14] is nearest to box[15] Total number of nearest box for [14] is 4 box[15] is nearest to box[3] box[15] is nearest to box[7] box[15] is nearest to box[9] box[15] is nearest to box[14] box[15] is nearest to box[16] Total number of nearest box for [15] is 5 box[16] is nearest to box[4] box[16] is nearest to box[8] box[16] is nearest to box[9] box[16] is nearest to box[15] Total number of nearest box for [16] is 4 

Although he can identify the nearest fields and count the number of neighbors, but I could not understand how I can group similar fields (as indicated above) and find the sum.

And I'm stuck here. Can anybody help me?

Updated code snippet

 vector<CheckRect> rects; unsigned isNearest(unsigned b, vector<unsigned>& neighbours) { unsigned nearBox_count = 0; for (unsigned x = 0; x < rects.size(); ++x) { if (rects[b].isAdjacent(rects[x])) { if (x==b) continue; //this is our box , so do not count it. nearBox_count++; printf("box[%d] is nearest to box[%d] \n", (b+1), (x+1)); neighbours.push_back(x); } } printf("Total number of nearest box for [%d] is %d \n", (b+1), nearBox_count ); printf("\n"); return nearBox_count; } int main(){ cin>>N; for(int b=0; b<N; b++){ ifstream inputFile1("RectCoordinates.txt"); //input from the file previously generated int rect_number; double xa0,ya0,xa1,ya1; int neighbours; isNearest( b, &neighbours);// This is the line that causing my ERROR } vector<unsigned> nearBox_count(rects.size()); vector< vector<unsigned> > neighbours(rects.size()); for (unsigned i = 0; i < rects.size(); ++i) { nearBox_count[i] = isNearest(i, neighbours[i]); } // Calculate the sums of neighbouring boxes vector<unsigned> neighCount(rects.size(), 0); for (unsigned i = 0; i < rects.size(); i++) { for (unsigned j = 0; j < neighbours[i].size(); j++) { neighCount[i] += nearBox_count[neighbours[i][j]]; } } // Calculate your result map<unsigned,unsigned> finalCount; for (unsigned i = 0; i < rects.size(); i++) { if (finalCount.count(nearBox_count[i]) == 0) finalCount[nearBox_count[i]] = neighCount[i]; else finalCount[nearBox_count[i]] += neighCount[i]; } // Print the result for (map<unsigned,unsigned>::iterator it = finalCount.begin(); it != finalCount.end(); ++it) { printf("Sum neighbours for the neighbours of similar boxes with %d " "neighbours is %d\n", it->first, it->second); } return 0; } 

Gives me a mistake -

 ss.cpp: In function 'int main()': ss.cpp:102:29: error: invalid initialization of reference of type 'std::vector<unsigned int>&' from expression of type 'unsigned int' ss.cpp:22:10: error: in passing argument 2 of 'unsigned int isNearest(unsigned int, std::vector<unsigned int>&)' 

How can i fix this?

Answer 1

Like trying to calculate your value, I made a few minor changes to your code.

Since all the indexes on your list are never negative, and most likely you will have a very large number of rectangles in the future, I would suggest making all your int unsigned . This has the added benefit of preventing some compiler warnings about comparing signed and unsigned integers in the code below.

The second change that I propose to make is to declare rects only once, and not every time you iterate through isNearest . In the code below, I achieved this by making rects global variable and creating a separate function to initialize it. Having made rects global variable, you can now replace all your 16 with rects.size() (reduce the chance of forgetting to change one 16 when added to the full data set).

 #include <iostream> #include <fstream> #include <cstdlib> #include <vector> #include <map> #include <stdio.h> using namespace std; class Rect { public: double x1, x2, y1, y2; // coordinates Rect(double X1, double Y1, double X2, double Y2) { if (X1 < X2) { x1 = X1; x2 = X2; } else { x2 = X1; x1 = X2; } if (Y1 < Y2) { y1 = Y1; y2 = Y2; } else { y2 = Y1; y1 = Y2; } } bool isAdjacent(Rect rect) { if (x1 == rect.x1 || x1 == rect.x2 || x2 == rect.x1 || x2 == rect.x2) { // use only < when comparing y1 and rect.y2 avoids sharing only a corner if (y1 >= rect.y1 && y1 < rect.y2) { return true; } if (y2 > rect.y1 && y2 <= rect.y2) { return true; } if (rect.y1 >= y1 && rect.y1 < y2) { return true; } if (rect.y2 > y1 && rect.y2 <= y2) { return true; } } if (y1 == rect.y1 || y1 == rect.y2 || y2 == rect.y1 || y2 == rect.y2) { if (x1 >= rect.x1 && x1 < rect.x2) { return true; } if (x2 > rect.x1 && x2 <= rect.x2) { return true; } if (rect.x1 >= x1 && rect.x1 < x2) { return true; } if (rect.x2 > x1 && rect.x2 <= x2) { return true; } } return false; } }; vector<Rect> rects; unsigned isNearest(unsigned b, vector<unsigned>& neighbours) { unsigned nearBox_count = 0; for (unsigned x = 0; x < rects.size(); ++x) { if (rects[b].isAdjacent(rects[x])) { if (x==b) continue; //this is our box , so do not count it. nearBox_count++; printf("box[%d] is nearest to box[%d] \n", (b+1), (x+1)); neighbours.push_back(x); } } printf("Total number of nearest box for [%d] is %d \n", (b+1), nearBox_count ); printf("\n"); return nearBox_count; } void initRects(void) { //Rect( x1 , y1 , x2 , y2 ) rects.push_back(Rect(0.0000,0.0000, 0.8147,0.1355)); rects.push_back(Rect(0.8147,0.0000, 1.0000,0.1355)); rects.push_back(Rect(0.8147,0.1355, 0.9058,0.8350)); rects.push_back(Rect(0.0000,0.1355, 0.1270,0.9689)); rects.push_back(Rect(0.9058,0.1355, 0.9134,0.2210)); rects.push_back(Rect(0.9058,0.8350, 1.0000,1.0000)); rects.push_back(Rect(0.8147,0.8350, 0.9058,1.0000)); rects.push_back(Rect(0.1270,0.1355, 0.6324,0.3082)); rects.push_back(Rect(0.1270,0.9689, 0.8147,1.0000)); rects.push_back(Rect(0.0000,0.9689, 0.1270,1.0000)); rects.push_back(Rect(0.9134,0.1355, 1.0000,0.2210)); rects.push_back(Rect(0.9134,0.2210, 1.0000,0.8350)); rects.push_back(Rect(0.9058,0.2210, 0.9134,0.8350)); rects.push_back(Rect(0.6324,0.1355, 0.8147,0.3082)); rects.push_back(Rect(0.6324,0.3082, 0.8147,0.9689)); rects.push_back(Rect(0.1270,0.3082, 0.6324,0.9689)); } void readRects(const string& filename) { ifstream fpInput(filename.c_str()); double dTemp[4]; while (true) { for (unsigned i = 0; i < 4; i++) fpInput >> dTemp[i]; if (!fpInput.good()) break; rects.push_back(Rect(dTemp[0], dTemp[1], dTemp[2], dTemp[3])); } fpInput.close(); } int main() { // Initialize the vector rects //initRects(); readRects("RectCoordinates.txt"); vector<unsigned> nearBox_count(rects.size()); vector< vector<unsigned> > neighbours(rects.size()); for (unsigned i = 0; i < rects.size(); ++i) { nearBox_count[i] = isNearest(i, neighbours[i]); } // Calculate the sums of neighbouring boxes vector<unsigned> neighCount(rects.size(), 0); for (unsigned i = 0; i < rects.size(); i++) { for (unsigned j = 0; j < neighbours[i].size(); j++) { neighCount[i] += nearBox_count[neighbours[i][j]]; } } // Calculate your result map<unsigned,unsigned> finalCount; for (unsigned i = 0; i < rects.size(); i++) { if (finalCount.count(nearBox_count[i]) == 0) { finalCount[nearBox_count[i]] = neighCount[i]; } else { finalCount[nearBox_count[i]] += neighCount[i]; } } // Print the result for (map<unsigned,unsigned>::iterator it = finalCount.begin(); it != finalCount.end(); ++it) { printf("Sum neighbours for the neighbours of similar boxes with %d " "neighbours is %d\n", it->first, it->second); } return 0; } 

Update: The above code can now be used by specifying Rect inside the source file or loading it from an external file. In the modified example above, the input file is RectCoordinates.txt :

 0.0000 0.0000 0.8147 0.1355 0.8147 0.0000 1.0000 0.1355 0.8147 0.1355 0.9058 0.8350 0.0000 0.1355 0.1270 0.9689 0.9058 0.1355 0.9134 0.2210 0.9058 0.8350 1.0000 1.0000 0.8147 0.8350 0.9058 1.0000 0.1270 0.1355 0.6324 0.3082 0.1270 0.9689 0.8147 1.0000 0.0000 0.9689 0.1270 1.0000 0.9134 0.1355 1.0000 0.2210 0.9134 0.2210 1.0000 0.8350 0.9058 0.2210 0.9134 0.8350 0.6324 0.1355 0.8147 0.3082 0.6324 0.3082 0.8147 0.9689 0.1270 0.3082 0.6324 0.9689 

The above results:

 Sum neighbours for the neighbours of similar boxes with 2 neighbours is 8 Sum neighbours for the neighbours of similar boxes with 3 neighbours is 32 Sum neighbours for the neighbours of similar boxes with 4 neighbours is 165 Sum neighbours for the neighbours of similar boxes with 5 neighbours is 22 Sum neighbours for the neighbours of similar boxes with 6 neighbours is 25 

Answer 2

Instead of trying to maintain the relationship between the rectangles in some data structures, it would be better to make the rectangle object itself smart and know about the number of its neighbors and who they are.

For example (incomplete proptotype to illustrate the idea):

 class Rect { public: //methods Rect(double X1, double Y1, double X2, double Y2); //const access double getX1() const; double getX2() const; double getY1() const; double getY2() const; int numNeighbors() const { return neighbors.size();} int sumOfNeighbors() const { int res(0); for(size_t i=0;i< neighbors.size();++i) res += neighbors[i]->numNeighbors(); return res;} std::vector<Rect*> getNeighbors() {return neighbors}; void addNeighbor(Rect* newNeighbor) {neighbors.push_back(newNeighbor);} //data private: double x1, x2, y1, y2; // coordinates std::vector<Rect*> neighbors; }; 

With such a rectangular class, you can add neighbors to each rectangle, extract your own all the neighbors of each rectangle and all your neighbors - all relations are stored inside the rectangle itself, and not some external object, the main program code should be very minimal.

Once you fill in the rectangles, you can simply iterate over them, choose from them having the required number of neighbors, and perform any operation on them.

Answer 3

I think if you want to radically simplify all this, you can use the recommendation of Mr. Kobelevsky:

 #include <iostream> #include <cstdlib> #include <vector> #include <stdio.h> using namespace std; class Rect { public: double x1, x2, y1, y2; // coordinates //methods Rect(double X1, double Y1, double X2, double Y2) { if (X1 < X2) { x1 = X1; x2 = X2; } else { x2 = X1; x1 = X2; } if (Y1 < Y2) { y1 = Y1; y2 = Y2; } else { y2 = Y1; y1 = Y2; } } ~Rect() { }; int numNeighbors() const { return neighbors.size();} int sumOfNeighbors() const { int res(0); for(size_t i=0;i< neighbors.size();++i) res += neighbors[i]->numNeighbors(); return res;} std::vector<Rect*> getNeighbors() {return neighbors;}; void addNeighbor(Rect* newNeighbor) {neighbors.push_back(newNeighbor);} //data std::vector<Rect*> neighbors; bool isAdjacent(Rect* rect) { if (x1 == rect->x1 || x1 == rect->x2 || x2 == rect->x1 || x2 == rect->x2) { // use only < when comparing y1 and rect->y2 avoids sharing only a corner if (y1 >= rect->y1 && y1 < rect->y2) { return true; } if (y2 > rect->y1 && y2 <= rect->y2) { return true; } if (rect->y1 >= y1 && rect->y1 < y2) { return true; } if (rect->y2 > y1 && rect->y2 <= y2) { return true; } } if (y1 == rect->y1 || y1 == rect->y2 || y2 == rect->y1 || y2 == rect->y2) { if (x1 >= rect->x1 && x1 < rect->x2) { return true; } if (x2 > rect->x1 && x2 <= rect->x2) { return true; } if (rect->x1 >= x1 && rect->x1 < x2) { return true; } if (rect->x2 > x1 && rect->x2 <= x2) { return true; } } return false; } }; vector<Rect*> rects; void CalculateAdjacentsForRect(unsigned int rects_element){ for (unsigned int x = 0; x < rects.size(); x++) { if (rects[rects_element]->isAdjacent(rects[x])) { if (x==rects_element) { continue; //this is our box , so do not count it. } rects[rects_element]->addNeighbor(rects[x]); } } } const int MAX_ADJACENT_RECTS = 10; int main() { //Rect( x1 , y1 , x2 , y2 ) rects.push_back(&Rect(0.0000,0.0000, 0.8147,0.1355)); rects.push_back(&Rect(0.8147,0.0000, 1.0000,0.1355)); rects.push_back(&Rect(0.8147,0.1355, 0.9058,0.8350)); rects.push_back(&Rect(0.0000,0.1355, 0.1270,0.9689)); rects.push_back(&Rect(0.9058,0.1355, 0.9134,0.2210)); rects.push_back(&Rect(0.9058,0.8350, 1.0000,1.0000)); rects.push_back(&Rect(0.8147,0.8350, 0.9058,1.0000)); rects.push_back(&Rect(0.1270,0.1355, 0.6324,0.3082)); rects.push_back(&Rect(0.1270,0.9689, 0.8147,1.0000)); rects.push_back(&Rect(0.0000,0.9689, 0.1270,1.0000)); rects.push_back(&Rect(0.9134,0.1355, 1.0000,0.2210)); rects.push_back(&Rect(0.9134,0.2210, 1.0000,0.8350)); rects.push_back(&Rect(0.9058,0.2210, 0.9134,0.8350)); rects.push_back(&Rect(0.6324,0.1355, 0.8147,0.3082)); rects.push_back(&Rect(0.6324,0.3082, 0.8147,0.9689)); rects.push_back(&Rect(0.1270,0.3082, 0.6324,0.9689)); for (unsigned int i = 0; i < rects.size(); i++) { CalculateAdjacentsForRect(i); } for (unsigned int i = 0; i < rects.size(); i++) { cout << "\nRect" << i << " has a neighbor sum of " << rects[i]->sumOfNeighbors(); } cout << "\n"; for (int ix = 0; ix < MAX_ADJACENT_RECTS; ix++) { int num_rects_with_this_num_of_adjacents = 0; int num_adjacents_total_for_similar_rects = 0; for (unsigned int i = 0; i < rects.size(); i++) { if ( rects[i]->numNeighbors() == ix ) { num_rects_with_this_num_of_adjacents++; num_adjacents_total_for_similar_rects += rects[i]->sumOfNeighbors(); } } cout << "\nThere are " << num_rects_with_this_num_of_adjacents << " rects with " << ix << " adjacent rects. They have a cum neighbor sum of " << num_adjacents_total_for_similar_rects; } return 0; } 

Answer 4

Well, I suppose you could use vectors, but this method can take up a lot of memory space. Say, make the vector 4neighbors - at first glance, I would say that each box has at least 4 neighbors (you would, however, do this for every possible number of neighbors). Hope this can be calculated and it won't be super-big). Then, checking the number of neighbors of each rectangle, use pushback on the corresponding vector.

 printf("Total number of nearest box for [%d] is %d \n",(b+1),nearBox_count ); if(nearBox_count == 4) 4neighbours.pushback(rects[b]); else if (nearBox_count == 5) 5neighbours.pushback(rects[b]); else if -etc- 

Then go through the vector and for each member of the vector, check the neighbors and for each neighbor calculate the neighbors and sum them up (you would have to nest two cycles - a cycle inside the cycle)

Example: Not Coded

 int TotalNeighbours = 0; while(go through all the boxes in the vector) { while(go through all the neighbours of each box) { TotalNeighbours++; } } 

I believe something like this might work, but, nevertheless, the limitations mentioned above. Depending on the maximum number of neighbors:

• Lots of memory usage;
• A lot of written code (many if statements);

Edit: one field can have 0 neighbors, the rest have at least 1 neighbor, not 4.