计算相邻框的数量
ari*_*152 6 c++ algorithm simulation rectangles
假设我有一组(X,Y)坐标为1000个盒子.
( 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 ++计算每个盒子相邻盒子的数量.我该怎么做？
例
在这张图片中,方框7的相邻方框总数为6,方框3为3.如何使用c ++计算它们？
使用新值进行编辑和更新
让我们尝试16个值 -
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
对于这些值,单位正方形变得像这样的图片 -
更新的代码 -
#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,它显示 -
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矩形!(请查看新图片)
对于矩形#2,它显示 -
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矩形!(请查看新图片)
我该如何解决？
一个天真的解决方案需要O(N ^ 2),其中N是矩形的数量,这里是如何更快地做到这一点.
只有两个矩形有一个共同的坐标时才会相邻(注意反面不正确).因此,您可以通过首先使用两个哈希对输入矩形进行分区来更快地计算相邻框的数量,一个基于矩形的x位置,另一个基于y位置.结果,一个矩形将基于其x1,y1,x2和y2适合四个不同的散列桶.
例
例如,矩形(0.0000,0.0000) (0.3412,0.4175)将散列到bucketX(0.000),bucketX(0.3412),bucketY(0.0000),和bucketY(0.4175).
从OP中的输入,bucketX(0.000)和bucketX(1.000)将具有以下矩形:
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)
时间复杂性
散列步骤仅需要O(N)计算时间,其中N是矩形的数量,并且得到的检查需要O(m ^ 2),其中m是最大桶的大小,在大多数情况下小于N.
检查每个散列桶内的邻接
然后,对于同一个哈希桶中的所有矩形.通过确定它们是否具有相同的x值和y中的重叠值来检查两个矩形是否相邻,反之亦然.
以下是检查两个矩形是否相邻的示例:
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;
}
}
一个可运行的例子
这里提供邻接检查的示例代码:
#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]