Menu
Suppose I have a set of (X,Y) coordinates of 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 adjacent boxes for each of them using c/c++ . How can I do it?
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 unit square become like this picture-
And the 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 shows-
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 misses the rectangle#8 and 9 & 10 !! (Please check the new picture)
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 misses the rectangle#5 and 7 & 6 !!! (Please check the new picture)
How can I fix it?
595
A naive solution requires O(N^2) where N is the number of rectangle, here is how to do it faster.
Two rectangles are adjacent only if they have one coordinate in common (note that the reverse is not correct). Therefore you can count the number of adjacent boxes faster by first partitioning your input rectangles using 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 into bucketX(0.000), bucketX(0.3412), bucketY(0.0000), and bucketY(0.4175).
From the input in 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
The hashing step only requires O(N) computation time where N is the number of rectangles, and the resulting check requires O(m^2) where m is the size of the largest bucket which in most cases is much smaller than N.
Checking adjacency within each hashed bucket
Then, for all rectangles within the same hash bucket. Check whether two rectangles are adjacent by determining whether they either have same x value and overlapped value in y or vice versa.
The following is an example of checking whether 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;
}
}
A Runnable Example
Here provide a sample code for the adjacency check:
#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 the output is:
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]
Let's say you're interested in box B for which the (x0, y0, x1, y1) coordinates are: (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 go through the whole list of boxes (with a for loop) and you select the ones 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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
