algorithm - 检查最近的矩形

Question

描述

假设用 (x1,y1)、(x2,y2)、(x3,y3) 和 (x4,y4) 表示的矩形的 4 边坐标。就像这张图——

在此处输入图像描述

我有一组保存在 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

我究竟做错了什么？

score 1 · Accepted Answer

反转问题。当您生成矩形时，维护一组 n 元组 J（其中 n 在 2 和 4 之间变化）表示“连接点”，即 2、3 或 4 个矩形相遇的角。对于您上面的图片，{1,4} 表示矩形 1 和 4 的（左）角，{1,4,8} 表示矩形 1、4 和 8 的角。您的图片有 25 个这样的 n 元组.

当您要对矩形 R 执行最近的矩形查询时，您需要在 J 中找到所有出现的 R，如果您根据关系“矩形 R 出现在 n 元组中”将 J 的元素组织到等价类中，这很容易，并且用矩形编号索引一个向量。然后查找 R 的邻居是 O(1)。

score 0 · Accepted Answer

假设您的矩形的 x 和 y 坐标为xleft, xright, ybottom, ytop。
对矩形进行排序并将它们分别保存在不同的数组中。

ybottomarrayybottom : 按then的升序对矩形进行排序xleft。

ytoparrayytop: 按升序排序xleft。

xleftarray: 按xleft当时的顺序排序ytop。

xrightarray: 按xright当时的顺序排序ytop。

现在遍历每个矩形。

步骤1：查找其上相邻矩形的数量，即ybottom等于ytop当前矩形的矩形。

二进制搜索ybottomarray以查找 ybottom 等于ytop当前矩形的第一个和最后一个索引。说范围是range_y。
在对小于当前矩形range_y的矩形索引进行二分搜索时，说 idx1。这会在当前矩形上方给出最左边的矩形。xleftxleft
xleft再次对具有最大值小于或等于当前矩形的矩形进行二分搜索，xright例如 idx2。这给出了当前矩形上方最右边的矩形。

因此，位于 idx1 到 idx2 中的矩形都与其上方的当前矩形相邻。所以idx2-idx1+1会给它上面的矩形。同样在所有四个边上找到矩形。

第2步：找到右边的矩形。
第3步：在底部找到矩形。
第4步：找到左边的矩形。

此外，还需要小心处理极端情况，以免矩形被计算两次，也没有留下用于计数。

复杂

排序步骤的复杂度为O(nlog n)。
迭代中的每个步骤都需要两次二进制搜索来查找 range_y 和二进制搜索来查找 idx1 和 idx2。所以每一步有四次二分查找，有四步。所以总共有 16 次二进制搜索，这使得每次迭代的复杂度为 O(logn) 。

因此，对于所有迭代，复杂度将为 O(n logn)。
所以这个解决方案的整体复杂度是O(n logn)。

score 0 · Accepted Answer

在您的情况下，每个最近的矩形必须共享一个公共边或部分公共边（如 rect 9 和 rect. 3 的情况）

考虑到你想找出最近的矩形矩形。一个
你知道它的角的 (x,y) 坐标
你知道坐标沿边缘变化
例如考虑边缘 A(x3,y3) 到 A(x4,y4)
考虑一个矩形B并检查它是否符合以下任何标准

B(x2,y2) 介于 A(x3,y3) 和 A(x4,y4)
之间 B(x1,y1) 介于 A(x3,y3) 和 A(x4,y4)
之间 A(x3,y3) 介于B(x2,y2) 和 B(x1,y1)
A(x4,y4) 在 B(x2,y2) 和 B(x1,y1) 之间
考虑的 B 的角与 A 的角重合

由角 A(x3,y3) 和 A(x4,y4) 描述的边缘是矩形 A 的顶部边缘，您想查看是否有任何矩形 B 位于其顶部，因此考虑由 B 描述的 B 的边缘(x1,y1) 和 B(x2,y2)

在某些情况下，上述某些标准是重叠的。

对正确匹配角坐标的其余边执行相同操作。（例如，在考虑由 A(x3,y2) 和 A(x2,y2) 描述的 A 的边缘时，考虑 B(x1,y1) 和 B(x4,y4)）

考虑所有矩形。数一数，瞧！

编辑：记住 A 是矩形。您要为其查找最近的成员。B是一个矩形。您正在检查它是否满足给定标准。

score 0 · Accepted Answer

所以，基本上，你正在寻找的是找到接触相关矩形的矩形？如果是这样，我认为应该这样做（虽然我还没有测试过）：

struct Rectangle {
    int x1, y1;
    int x2, y2;
    int x3, y3;
    int x4, y4;
};

// This is why I hate C++ :/
bool operator==(const Rectangle& lhs, const Rectangle& rhs) {
    return  lhs.x1 == rhs.x1 && lhs.y1 == rhs.y1 &&
            lhs.x2 == rhs.x2 && lhs.y2 == rhs.y2 &&
            lhs.x3 == rhs.x3 && lhs.y3 == rhs.y3 &&
            lhs.x4 == rhs.x4 && lhs.y4 == rhs.y4;
}

// Returns all rectangles in `rectangles` that touch `base`
std::vector<int> get_touching_rectangles(Rectangle base,
        std::vector<Rectangle> rectangles) {

    // Create the array that we will return,
    //  i.e. the touching rectangles
    std::vector<Rectangle> ret;

    // Iterate through each rectangle
    for (auto it = rectangles.begin(); it != rectangles.end(); it++) {
        Rectangle other = *it;

        // If this (`other`) is our rectangle (`base`)
        //   i.e. the one we are trying to find rectangles that touch it,
        // skip it
        if (base == other) {
            continue;
        }

        // If `other` touches the top or bottom sides of `base`, add it
        if ((other.x2 >= base.x1 && other.x1 <= base.x2) &&
                (other.y1 == base.y3 || other.y3 == base.y1)) {
            ret.push_back(other);
            continue;
        }

        // If `other` touches the left or right sides of `base`, add it
        if ((other.y3 >= base.y2 && other.y2 <= base.y3) &&
                (other.x1 == base.x3 || other.x3 == base.x1)) {
            ret.push_back(other);
            continue;
        }

    }

    return ret;
}

然后像这样使用它：

std::vector<Rectangle> rectangles;
parse_txt_file(file, &rectangles); // Or whatever you do to parse that .txt file
std::vector<Rectangle> touching = get_touching_rectangles(rectangles.at(2) /* Rectangle #3 */, rectangles);

然后touching应该包含，如你所说，矩形 9、15、14、1、2、5、13、6 和 7（它将返回Rectangle，而不是数字）。

algorithm - 检查最近的矩形

4 回答 4

Related

Reference