从一组给定的坐标中找到矩形的数量

Question

我必须从给定的一组坐标中找到最大的矩形数。

考虑以下坐标系在X Y坐标系中给出3 103 83 63 43 0，6 0，6 46 86 10，

如何确定以下坐标是否形成矩形（3,0）（3,4）（6,4）（6,0）

运行时间限制：0.1秒

谢谢

Answer 1

要检查四个点是否形成一个矩形：

1. 每两点计算一次距离。将所有内容存储在浮点数组中。
2. 对数组排序。

您将拥有a [0] = a [1]，a [2] = a [3]，a [4] = a [5]

Answer 2

将点分开在“ y”坐标列表中，并按“ x”坐标分组。在您的情况下，您将有两个排序列表：

3: [0,4,6,8,10]
6: [0,4,8,10]

做两个列表的交集，您会得到：[0,4,8,10]

其中任何两个都会形成一个矩形：

[0,4] => (3,0), (3,4), (6,0), (6,4)
[0,8] => (3,0), (3,8), (6,0), (6,8)
[4,8] => (3,4), (3,8), (6,4), (6,8)
...

此解决方案仅适用于正交矩形，即其边平行于x，y轴。

Answer 3

如何查找以下坐标是否形成矩形

检查差矢量是否正交，即点积为零。

此操作不是检查这些坐标是否包含在列表中。它还会not检查矩形是否与坐标轴对齐，这将是一个简单得多的问题。

如果要在输入中查找所有矩形，则可以对所有四倍体进行以上检查。如果由于性能原因不能接受，那么您应该更新您的问题，指出您面临的是什么样的问题大小和性能约束。

Answer 4

对于每对点，假设（x1，y1）和（x2，y2）认为它是某个矩形的对角线。如果初始集中存在点（x1，y2）和（x2，y1），则我们已经找到了矩形。应该注意的是，将存在2个对角线，它们代表相同的矩形，因此我们将最终答案除以2。]

这仅适用于平行于x轴或y轴的矩形。

PseudoCode C ++：

answer = 0;
set<pair<int, int>> points;

for(auto i=points.begin(); i!=std::prev(points.end()); i++)
{
    for(auto j=i+1; j!=points.end(); j++)
    {
        pair<int, int> p1 = *i;
        pair<int, int> p2 = *j;
        pair<int, int> p3 = make_pair(p1.first, p2.second);
        pair<int, int> p4 = make_pair(p2.first, p1.second);
        if(points.find(p3) != points.end() && points.find(p4) != points.end())
            ++answer;
    }
}

return answer/2;