检查最近的矩形。

Question

描述

假设一个矩形的4个边的坐标分别为(x1,y1), (x2,y2),(x3,y3) 和 (x4,y4)，如下图所示-

我有一个包含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

我做错了什么？

- aries0152

---

快速提示，您不需要x2、y2和x4、y4...您可以自动填充x1、y1和x3、y3，或者说，如果您只处理矩形，就像您所说的那样。 - MiJyn

这跟您之前发表的这篇文章[链接1]和这篇文章[链接2]非常相似，不是吗？请注意不要改变原意。 - meaning-matters

考虑到限制为100000，这似乎是某个编码网站的问题，时间限制为1秒。可接受的复杂度为O(n logn)。 - Shashwat Kumar

请查看http://en.wikipedia.org/wiki/Quadtree。 - Maxime Chéramy

@aries0152：你问了同样的问题3次了吗？ - Karoly Horvath

Answer 1

反转问题。在生成矩形时，维护一个 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)。

- user1666959

Answer 2

所以，基本上你要找的是与所提出的矩形相接触的矩形？如果是这样，我认为像这样的代码应该可以实现（尽管我还没有测试过）：

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 而不是数字）。

- MiJyn

---

我已经编辑了我的问题并尝试使用您的代码。但是出现了一些错误。您能帮我吗？ - aries0152

@aries0152 我编辑了我的问题以修复 == 问题。关于你遇到的第二个问题 (ret was not declared in this scope)，你忘记在 get_touching_rectangles 函数的顶部添加 std::vector<Rectangle> ret;。 - MiJyn

@aries0152 请注意，这个函数有点像伪代码，目的是为了给你一个思路，以及提供一个基本的（参考？）实现（我在写这个答案时也无法理解其他出现的答案XD）。我添加了额外的注释来解释每个部分的工作原理 :) - MiJyn

Answer 3

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

1. 考虑您要查找rect. A的最近矩形
2. 您知道它的角落的(x,y)坐标
3. 您知道坐标沿着边缘变化
4. 例如，考虑从A(x3,y3)到A(x4,y4)的边缘A
5. 考虑一个矩形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(x1,y1)和B(x2,y2)描述的B的边缘

以上某些标准在某些情况下重叠。

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

考虑所有矩形。计数它们，然后大功告成！

编辑:请记住，A是您要查找最近成员的矩形。B是一个矩形，您正在检查它是否符合给定的标准。

- Colorless Photon

---

我给你点了踩，因为你提供的方法是最幼稚的。你只是写出了当给定坐标时两个矩形是否相邻的条件。所以对于每个矩形都进行迭代是一个显而易见的解决方案。我不认为问题会要求这样的解决方案。我相信提问者希望得到更好的方法。这个O(n^2)的解决方案在100000个矩形上会非常慢。 - Shashwat Kumar

Answer 4

假设您的矩形具有x和y坐标，如xleft、xright、ybottom、ytop。
将矩形排序并分别保存在不同的数组中。

• ybottomarray:按递增顺序对ybottom然后xleft的矩形进行排序。

• ytoparray：按递增顺序对ytop然后xleft的矩形进行排序。

• xleftarray：按xleft然后ytop的顺序排序。

• xrightarray：按xright然后ytop的顺序排序。

现在迭代每个矩形。

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

• 在ybottomarray中进行二分查找，找到第一个和最后一个ybottom等于当前矩形的ytop的索引。称这个范围为range_y。

• 在range_y中进行二分查找，找到xleft刚好小于当前矩形的xleft的矩形的索引，称其为idx1。这给出了位于当前矩形上方的最左边的矩形。

• 再次进行二分查找，找到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)。

- Shashwat Kumar