说明
假设矩形4边的坐标由（x1，y1），（x2，y2），（x3，y3）和（x4，y4）表示。就像这张照片-
我在txt文件中保存了一组100000个矩形的坐标例如，下面是由我的代码生成的16个矩形的坐标值-
#Rect x1 y1 x2 y2 x3 y3 x4 y4 area
1 0.0000 0.0000 0.8147 0.0000 0.8147 0.1355 0.0000 0.1355 0.1104
2 0.8147 0.0000 1.0000 0.0000 1.0000 0.1355 0.8147 0.1355 0.0251
3 0.8147 0.1355 0.9058 0.1355 0.9058 0.8350 0.8147 0.8350 0.0637
4 0.0000 0.1355 0.1270 0.1355 0.1270 0.9689 0.0000 0.9689 0.1058
5 0.9058 0.1355 0.9134 0.1355 0.9134 0.2210 0.9058 0.2210 0.0006
6 0.9058 0.8350 1.0000 0.8350 1.0000 1.0000 0.9058 1.0000 0.0155
7 0.8147 0.8350 0.9058 0.8350 0.9058 1.0000 0.8147 1.0000 0.0150
8 0.1270 0.1355 0.6324 0.1355 0.6324 0.3082 0.1270 0.3082 0.0873
9 0.1270 0.9689 0.8147 0.9689 0.8147 1.0000 0.1270 1.0000 0.0214
10 0.0000 0.9689 0.1270 0.9689 0.1270 1.0000 0.0000 1.0000 0.0040
11 0.9134 0.1355 1.0000 0.1355 1.0000 0.2210 0.9134 0.2210 0.0074
12 0.9134 0.2210 1.0000 0.2210 1.0000 0.8350 0.9134 0.8350 0.0532
13 0.9058 0.2210 0.9134 0.2210 0.9134 0.8350 0.9058 0.8350 0.0047
14 0.6324 0.1355 0.8147 0.1355 0.8147 0.3082 0.6324 0.3082 0.0315
15 0.6324 0.3082 0.8147 0.3082 0.8147 0.9689 0.6324 0.9689 0.1205
16 0.1270 0.3082 0.6324 0.3082 0.6324 0.9689 0.1270 0.9689 0.3339
这些坐标将一个单位正方形分割成子矩形，如图所示-
最近矩形的示例
在上图中，矩形3的最近矩形为-9、15、14、1、2、5、13、6和7。
对于矩形9，它们是-10、4、16、15、3和7。
我的问题
现在我想用c/c++计算每个矩形的最近矩形数。我该怎么做？
编辑：基于响应
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
struct Rectangle {
double x1, y1;
double x2, y2;
double x3, y3;
double x4, y4;
};
vector<double> get_touching_rectangles(Rectangle base, vector<Rectangle> rectangles) {
for (auto it = rectangles.begin(); it != rectangles.end(); it++) {
Rectangle other = *it;
if (base == other) {
continue; // This is our rectangle... skip it
}
// Top or bottom
if ((other.x2 >= base.x1 && other.x1 <= base.x2) && (other.y1 == base.y3 || other.y3 == base.y1)) {
ret.push_back(other);
continue;
}
// Left or right
if ((other.y3 >= base.y2 && other.y2 <= base.y3) && (other.x1 == base.x3 || other.x3 == base.x1)) {
ret.push_back(other);
continue;
}
}
return ret;
}
int main(int argc, char const *argv[])
{
vector<Rectangle> rectangles;
//parse_txt_file(file, &rectangles); // Or whateer I need to do to parse that .txt file
ifstream inputFile;
inputFile.open("RectCoordinates.txt");
//std::vector<Rectangle> touching =
get_touching_rectangles(rectangles.at(2) /* Rectangle #3 */, rectangles);
inputFile.close();
return 0;
}
好的，我根据回答写上面的代码但它显示了以下错误-
g++ -std=c++11 st5.cpp -o ssst5.cpp: In function ‘std::vector<double> get_touching_rectangles(Rectangle, std::vector<Rectangle>)’:
st5.cpp:23:21: error: no match for ‘operator==’ in ‘base == other’
st5.cpp:23:21: note: candidates are:
In file included from /usr/include/c++/4.7/iosfwd:42:0,
from /usr/include/c++/4.7/ios:39,
from /usr/include/c++/4.7/ostream:40,
from /usr/include/c++/4.7/iostream:40,
from st5.cpp:1:
/usr/include/c++/4.7/bits/postypes.h:218:5: note: template<class _StateT> bool std::operator==(const std::fpos<_StateT>&, const std::fpos<_StateT>&)
/usr/include/c++/4.7/bits/postypes.h:218:5: note: template argument deduction/substitution failed:
st5.cpp:28:13: error: ‘ret’ was not declared in this scope
st5.cpp:33:13: error: ‘ret’ was not declared in this scope
st5.cpp:37:12: error: ‘ret’ was not declared in this scope
我做错什么了？
最佳答案
把问题颠倒过来生成矩形时，请保持一组n元组的j（其中n在2和4之间变化），表示“连接点”，即2、3或4个矩形的角相交。因为上面的图片{1,4}表示矩形1和4的（左）角，{1,4,8}表示矩形1、4和8的角。你的照片有25个这样的n元组。
如果要对矩形r执行最近矩形查询，则需要查找r在j中的所有出现位置，如果基于关系“矩形r出现在n元组中”将j的元素组织到等价类中并用矩形数索引向量，则很容易找到。然后查R的邻域是O（1）。
关于algorithm - 检查最近的矩形，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17412086/