伯爵的相邻箱数伯爵
假设我有一组（X，Y）坐标的1000箱。
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
我想计算相邻箱子的数量，使用C / C ++他们每个人。我该怎么办呢？
I would like to calculate the number of adjacent boxes for each of them using c/c++ . How can I do it?
示例的
在此画面中，相邻的箱盒7的总数是6，对于盒-3是三。我怎么能指望他们使用C ++？
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++?
编辑和更新与新值
让我们尝试它16个值 -
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-
和更新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;
}
问题
现在的矩形＃1它shows-
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
这忽略了矩形＃8和9和; 10！ （请检查新图片）
It misses the rectangle#8 and 9 & 10 !! (Please check the new picture)
和为矩形＃2时显示 -
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
这忽略了矩形＃5和7＆放大器; 6！ （请检查新图片）
It misses the rectangle#5 and 7 & 6 !!! (Please check the new picture)
我该如何解决这个问题？
How can I fix it?
推荐答案
一个天真的解决方案需要O（N ^ 2），其中N是矩形的数量，这里是如何更快地做到这一点。
A naive solution requires O(N^2) where N is the number of rectangle, here is how to do it faster.
两个矩形是相邻的，只有当他们有一个共同的坐标（注意该反向是不正确的）。因此可以通过首先使用两个哈希，一种基于矩形的x位置和其他基于所述y位置进行分区输入矩形数的相邻盒数更快。其结果是，根据它的X1，Y1，X2，和y2 1矩形将适合四个不同的散列桶
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
例如，矩形（0.0000,0.0000），（0.3412,0.4175）将被散列到 bucketX（0.000）， bucketX（0.3412）， bucketY（0.0000）和 bucketY（0.4175）。
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).
从输入到OP，bucketX（0.000）和bucketX（1.000）将有以下矩形：
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
散列步骤仅需要O（N）的计算时间，其中N是矩形的数目，将得到的检查需要O（平方公尺），其中m是最大桶的大小，在大多数情况下远小于ñ。
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
然后，对于相同的哈希桶中的所有的矩形。检查两个矩形是否是相邻的通过确定它们是否可能已在y或反之亦然相同的x值和重叠值。
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
下面提供了一个示例code的邻接检查：
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);
}
}
}
和输出是：
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]
