logo标签列表

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

geometrycoordinatesrectangles
12

我需要从一组给定的坐标中找到最大的矩形。

考虑以下坐标在X Y坐标系中给出:

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 秒

谢谢

1
决定问题是什么。4个点形成一个矩形，或者在给定的点中可以形成多少个矩形？ - hasan
实际上，我该如何验证4个点是否构成一个矩形？另外，我该如何找到可能的最大矩形数量？ - Alin
给定点的最大数量是多少？ - hasan
所有给定的点都是整数吗？ - hasan
x和y的最大值是多少？ - hasan
显示剩余4条评论
7个回答
10

将你的点按'x'坐标分组，每组内按'y'坐标排序。在你的情况下，你会得到两个已排序列表：

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轴平行的矩形。

太棒了，我一直在苦苦思索如何实现这个。 - AlvaroAV
我刚看到你关于正交的注释。抱歉。 - hasan
虽然在正交情况下有一种旋转的方式，但应该有一种改变坐标计算的方法来进行旋转。 - John LaBarge
9

对于任意一组点（x1，y1）和（x2，y2），将其视为某个矩形的对角线。如果初始集合中存在点（x1，y2）和（x2，y1），则我们找到了一个矩形。需要注意的是，会存在代表同一矩形的两条对角线，因此我们将最终答案除以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;
帮我看一下，(1,1) (2,2) (3,1) (2,0) 是不是一个矩形？ - hasan
@hasan - 这是一个矩形，但它的边不平行于坐标轴。 - Anurag Singh
4

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

  1. 对于任意两个点，计算它们之间的距离，并将所有距离存储到浮点数数组中。
  2. 对数组进行排序。

如果满足条件，则应该有a[0] = a[1], a[2] = a[3], a[4] = a[5]

2
你的条件是“必要但不充分”的：平行四边形也能满足它。而对浮点数进行精确相等比较是个坏主意，因为存在舍入误差。 - MvG
我对这个解决方案有点困惑。那么这组点（a，b，c，d）=（1,2），（2,1），（3,1），（4,2）呢？a和b之间的距离与c和d之间的距离相同，但它们并不形成一个矩形。 - Eneko Alonso
1
你必须有六个值。a-b = c-d，a-d = b-c，a-c = b-d。最后一个是对角线。 - hasan
我在上面的问题中留言了很多问题。我需要很多信息才能为每种情况提供适当的解决方案。回答它们，我会告诉你。 - hasan
好的，所以你的答案只是检查一组4个点是否为矩形，但并没有解决如何在有限点集上找到矩形数量的问题。我指责问题的作者，因为他问了两个不同的问题:P - Eneko Alonso
显示剩余3条评论
1
我该如何确定以下坐标是否形成矩形？
检查差向量是否正交，即点积为零。
这不检查这些坐标是否包含在您的列表中。它也不检查矩形是否与坐标轴对齐，这将是一个更简单的问题。
如果您想在输入中找到所有矩形，则可以对所有四元组执行上述检查。如果由于性能原因而无法接受，则应更新您的问题，指出您面临的问题规模和性能限制。
如果我理解正确的话，您的建议是迭代所有点的四元组（O(n^4)），并检查每个四元组是否满足v . w = 0，其中v = p1-p2，w = p3-p4，对吗？您所说的“这不检查这些坐标是否包含在您的列表中”是什么意思？您正在迭代给定的点，那么为什么需要进行此检查呢？ - Alan Evangelista
0

我的方法是：

  • 遍历每个点
  • 检查在该点上面有哪些点，并存储形成一条线的Y坐标
  • 下次如果再次发现相同的Y坐标，那么我们就找到了一个矩形
  • 不断地遍历所有其他点，并执行同样的操作。

我的解决方案运行时间为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))
0

我谨呈上

enter image description here

我假设有多种优化方式可供选择。

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来检查此属性，因此这是最有效的方法（而不是计算边长时进行平方根计算）。

首先对点进行排序可避免由于排列组合而多次检查相同的点集。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接