11

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

考虑在 XY 坐标系中给出以下坐标 3 10, 3 8, 3 6, 3 4, 3 0, 6 0, 6 4, 6 8, 6 10,

如何找到以下坐标是否形成矩形 (3,0) (3,4) (6,4) (6,0)

运行时间限制：0.1 秒

谢谢

4

7 回答 7

10

将您的点分隔在“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 轴。

于 2013-10-28T21:38:12.363 回答
8

对于每一对点，比如 (x1, y1) 和 (x2, y2) 认为它是某个矩形的对角线。如果在初始集合中存在点 (x1, y2) 和 (x2, y1)，那么我们已经找到了我们的矩形。应该注意的是，将存在 2 条对角线表示同一个矩形，因此我们将最终答案除以 2。

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

伪代码 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;

        if(p1.first == p2.first || p1.second == p2.second)
            continue;

        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;
于 2019-09-30T17:40:58.377 回答
4

检查 4 个点是否形成一个矩形：

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

你将有 a[0] = a[1], a[2] = a[3], a[4] = a[5]

于 2013-10-05T22:22:21.867 回答
1

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

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

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

如果您想在输入中找到所有矩形，您可以对所有四元组进行上述检查。如果由于性能原因这是不可接受的，那么您应该更新您的问题，指出您面临什么样的问题规模和性能约束。

于 2013-10-05T22:20:17.657 回答
0

我谦虚的提交

在此处输入图像描述

我假设优化次数是可能的。

于 2020-01-28T10:38:36.160 回答
0

我的方法是

  • 遍历每个点
  • 检查哪些所有点都在该点上方，然后存储形成一条线的那些点的 Y 坐标
  • 下次当我再次找到相同的 Y 坐标时，这意味着我们找到了 1 个矩形
  • 继续遍历所有其他点再次做同样的事情。

我的解决方案在O(n^2) 中运行，但这只会是平行于 X 或 Y 轴的矩形。

这是我上述方法的代码：

def getRectangleCount(coordinate):
    n = len(coordinate)
    y_count = dict()
    ans = 0
    for i in range(n):
        x, y = coordinate[i]
        for j in range(n):
            dx = coordinate[j][0]
            dy = coordinate[j][1]
            if y < dy and x == dx:
                ans += y_count.get((y, dy), 0)
                y_count[(y, dy)] = y_count.get((y, dy), 0) + 1
    return ans


coordinate = [[3, 10], [3, 8], [3, 6], [3, 4], [3, 0], [6, 0], [6, 4], [6, 8], [6, 10]]
print(getRectangleCount(coordinate))
于 2021-03-14T11:30:51.567 回答
0

这是一个解决方案，可以在 O(n^4) 时间内在给定的坐标点列表中找到所有唯一的矩形（不仅是那些平行于 x 或 y 轴的矩形）。

伪代码：

// checks if two floating point numbers are equal within a given 
// error to avoid rounding issues
bool is_equal(double a, double b, double e) {
    return abs(a - b) < e;
}

// computes the dot product of the vectors ab and ac
double dot_product(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.x - a.x) + (b.y - a.y) * (c.y - a.y);
}

// find all rectangles in a given set of coordinate points
List<Rectangle> find_rectangles(List<Point> points) {
    List<Rectangle> rectangles;

    // sort points in ascending order by first comparing x than y value
    sort(points);

    for (int a = 0; a < points.size(); ++a)
        for (int b = a + 1; a < points.size(); ++b)
            for (int c = b + 1; c < points.size(); ++c)
                for (int d = c + 1; d < points.size(); ++d)
                    // check all angles
                    if (is_equal(dot_product(points[a], points[b], points[c]), 0.0, 1e-7) &&
                        is_equal(dot_product(points[b], points[a], points[d]), 0.0, 1e-7) &&
                        is_equal(dot_product(points[d], points[b], points[c]), 0.0, 1e-7) &&
                        is_equal(dot_product(points[c], points[a], points[d]), 0.0, 1e-7))
                        // found rectangle
                        rectangles.add(new Rectangle(points[a], points[c], points[d], points[b]));

    return rectangles;
}

解释：

对于给定的一组点A, B, C, D来定义一个矩形，我们可以检查是否所有角度都是 90°，这意味着所有非平行边都是正交的。

因为我们可以通过点积为 0 来检查这个属性，这是最有效的方法（而不是必须进行平方根计算来计算边长）。

首先对点进行排序可以避免由于排列而多次检查同一组点。

于 2022-01-13T16:09:42.090 回答