Count the number of adjacent boxes

Question

Suppose I have a set of (X, Y) coordinates for 1000 boxes.

( x1, y1) ( x2, y2) Area (0.0000,0.0000) (0.3412,0.4175) 0.1424 (0.7445,0.0000) (1.0000,0.6553) 0.1674 (0.7445,0.6553) (1.0000,1.0000) 0.0881 (0.0000,0.6553) (0.7445,1.0000) 0.2566 (0.3412,0.0000) (0.7445,0.4175) 0.1684 (0.3412,0.4175) (0.7445,0.6553) 0.0959 (0.0000,0.4175) (0.3412,0.6553) 0.0812 ....etc 

I would like to calculate the number of neighboring boxes for each of them using c / C ++. How can i do this?

Example

In this picture, the total number of adjacent boxes for box-7 is six, for box-3 is three. How can I count them using C ++?

Edited and updated with new values

Let's try it for 16 values ​​-

 1 0.0000 0.0000 0.8147 0.1355 2 0.8147 0.0000 1.0000 0.1355 3 0.8147 0.1355 0.9058 0.8350 4 0.0000 0.1355 0.1270 0.9689 5 0.9058 0.1355 0.9134 0.2210 6 0.9058 0.8350 1.0000 1.0000 7 0.8147 0.8350 0.9058 1.0000 8 0.1270 0.1355 0.6324 0.3082 9 0.1270 0.9689 0.8147 1.0000 10 0.0000 0.9689 0.1270 1.0000 11 0.9134 0.1355 1.0000 0.2210 12 0.9134 0.2210 1.0000 0.8350 13 0.9058 0.2210 0.9134 0.8350 14 0.6324 0.1355 0.8147 0.3082 15 0.6324 0.3082 0.8147 0.9689 16 0.1270 0.3082 0.6324 0.9689 

For these values, the square of the unit becomes like this image -

And updated code

  #include <iostream> #include <cstdlib> #include <vector> using namespace std; class Rect { public: double x1, x2, y1, y2; // assuming x1 <= x2 and y1 <= y2 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) { //for x-axis if (x1 == rect.x2 || x2 == rect.x1) { // 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; } } // for y-axis if (y1 == rect.y2 || y2 == rect.y1) { if (x1 >= rect.x1 && x1 < rect.x2) { return true; } if (x2 > rect.x1 && x2 <= rect.x2) { return true; } } return false; } }; int main() { vector<Rect> rects; 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 adj_count = 0; int b; cin>>b; for (int x = 0; x < rects.size(); ++x) { if (rects[b].isAdjacent(rects[x])) { if (x==b) { continue; //this is our rectangle , so do not count it. } adj_count++; cout << "rect["<<(b+1)<<"] is adjacent with rect["<<(x+1)<<"]"<<endl; } } cout<<"adjacent count of rect["<<(b+1)<<"] is = "<<adj_count<<endl; return 0; } 

Problem

Now for rectangle # 1, it displays-

 rect[1] is adjacent with rect[2] rect[1] is adjacent with rect[4] rect[1] is adjacent with rect[14] adjacent count of rect[1] is = 3 

It skips rectangle # 8 and 9 and 10! (Please check the new image)

And for rectangle # 2, it shows -

 rect[2] is adjacent with rect[1] rect[2] is adjacent with rect[3] rect[2] is adjacent with rect[11] adjacent count of rect[2] is = 3 

It skips rectangle # 5 and 7 and 6 !!! (Please check the new image)

How can i fix this?

Answer 1

A naive solution requires O (N ^ 2), where N is the number of rectangles, here's how to do it faster.

Two rectangles are adjacent only if they have one common coordinate (note that the opposite is not true). Therefore, you can count the number of neighboring boxes faster by first breaking the input rectangles into two hashes, one based on the x location of the rectangle, and the other based on the y location. As a result, one rectangle will fit into four different hash buckets based on its x1, y1, x2 and y2.

---

Example

For example, rect (0.0000,0.0000) (0.3412,0.4175) will be hashed in bucketX(0.000) , bucketX(0.3412) , bucketY(0.0000) and bucketY(0.4175) .

From the input to the OP, bucketX (0.000) and bucketX (1.000) will have the following rectangles:

 bucketX(0.0000): (0.0000,0.0000) (0.3412,0.4175) (0.0000,0.4175) (0.3412,0.6553) (0.0000,0.6553) (0.7445,1.0000) (0.0000,0.4175) (0.3412,0.6553) bucketX(1.0000): (0.7445,0.0000) (1.0000,0.6553) (0.7445,0.6553) (1.0000,1.0000) 

---

Time complexity

For the hashing step, only the calculation time O (N) is required, where N is the number of rectangles, and for the verification obtained, O (m ^ 2) is required, where m is the size of the largest bucket, which in most cases is much smaller than N.

---

Adjacency check in each hash bucket

Then for all the rectangles inside the same hash bucket. Check if the two rectangles are adjacent by determining if they have the same x value and the overlapping value in y or vice versa.

The following is an example of checking if two rectangles are adjacent:

 class Rect { public: double x1, x2, y1, y2; // assuming x1 <= x2 and 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; } } 

---

Running example

Here is an example adjacency verification code:

 #include <stdio.h> #include <stdlib.h> #include <vector> class Rect { public: double x1, x2, y1, y2; // assuming x1 <= x2 and y1 <= y2 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; } } double area() { return (x2 - x1) * (y2 - y1); } 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; } }; int main() { std::vector<Rect> rects; rects.push_back(Rect(9999, 9999, 9999, 9999)); 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 adj_count = 0; int y = 1; for (int x = 0; x < rects.size(); ++x) { if (x == y) continue; if (rects[y].isAdjacent(rects[x])) { printf("rect[%d] is adjacent with rect[%d]\n", y, x); } } y = 2; for (int x = 0; x < rects.size(); ++x) { if (x == y) continue; if (rects[y].isAdjacent(rects[x])) { printf("rect[%d] is adjacent with rect[%d]\n", y, x); } } } 

and output:

 rect[1] is adjacent with rect[2] rect[1] is adjacent with rect[4] rect[1] is adjacent with rect[8] rect[1] is adjacent with rect[14] rect[2] is adjacent with rect[1] rect[2] is adjacent with rect[3] rect[2] is adjacent with rect[5] rect[2] is adjacent with rect[11] 

Answer 2

Let's say you are interested in field B for which the coordinates (x0, y0, x1, y1) are found: (B.x0, B.y0, B.x1, B.y1)

Then with:

 ax0 = min(x0,x1); ax1 = max(x0,x1); ay0 = min(y0,y1); ay1 = max(y0,y1); bx0 = min(B.x0,B.x1); bx1 = max(B.x0,B.x1); by0 = min(B.y0,B.y1); by1 = max(B.y0,B.y1); 

you look at the entire list of mailboxes (with a for loop), and you select those for which:

 (((ay0 <= by1 && ay1 >= by0) && (ax1 == bx0 || ax0 == bx1) || // touch on x axis ((ax0 <= bx1 && ax1 >= bx0) && (ay1 == by0 || ay0 == by1)) // touch on y axis 

Answer 3

In the scenario described by the blocks, corners are used, so if you calculated all the corners of the window, you can see which of them touched

 // O(n) foreach box b { // compute b other 2 corners and save them } // 16 * O(n^2) = O(n^2) foreach box b { foreach box other { // match if any of b corners match any of others points } } 

There is probably a much more efficient / elegant solution, it is somewhat naive.