从2D列表中找出四个点组成正方形

Question

从2D列表中找出四个点组成正方形

4

我有一个如下的二维列表:

a = [[3, 10], [7, 11], [7, 12], [8, 11], [8, 12], [12, 8], [12, 9], [13, 8], [13, 9], [14, 6], [14, 7], [15, 8], [17, 6], [18, 6]]

有4个点可以形成一个正方形：

[7, 11], [7, 12], [8, 11], [8, 12]

或者这个：

[12, 8], [12, 9], [13, 8], [13, 9]

这是我的代码：

def find_square(a):
    i = 0
    result = []
    while(i < len(a)):
        if a[i][0] == a[i + 1][0]:
            if a[i][1] == a[i + 2][1]:
                if a[i + 2][0] == a[i + 3][0]:
                    if a[i + 1][1] == a[i + 3][1]:
                        result.append([a[i][0] + 1, a[i][1] + 1])
                    i += 4
                else:
                    i += 3
            else:
                i += 2
        else:
            i += 1
    return result

输出：

[8, 12], [13, 9]

这段代码将返回正方形的最后一个点（右下角）。我想检查是否存在4个点，可以组成一条边长为1的正方形，并返回它的右下角。有更好的实现方法吗？

假设2D列表按x坐标升序排序。

更新：

我发现我的代码存在问题的情况：

[7, 11], [7, 12], [7, 13], [8, 11], [8, 12]

我的代码无法检测到正方形，是因为点[7, 13]存在。

- huy

1

所以这个正方形必须由连续的点组成，而不仅仅是列表中的任意四个点？ - M Oehm

@MOehm必须由连续的点组成。 - huy

1

就复杂度而言，你真的做不到更好了（这是线性的，你做不到更好。最多也许你可以赢得一个常数因子）。你的问题是关于实现和拥有漂亮的代码吗？ - gdelab

@gdelab 我没有考虑到那种情况。谢谢。我不需要它们中的任何一个，也许可以为那种情况返回0。 - huy

1

@gdelab 我的代码也有一个问题，就是当出现这样一种情况：[7, 11]，[7, 12]，[7, 13]，[8, 11]，[8, 12]。点 [7, 13] 会位于正方形中间，而我的代码无法检测到该正方形。 - huy

显示剩余3条评论

2个回答

3

一种不要求点是连续的解决方案，甚至不需要列表以任何方式排序：

a = [[3, 10], [7, 11], [7, 12], [7, 13], [8, 11], [8, 12], [12, 8], [12, 9], [13, 8], [13, 9], [14, 6], [14, 7], [15, 8], [17, 6], [18, 6]]

from itertools import combinations

def is_square(points, square_side=1):
    if len(set(tuple(pt) for pt in points)) != 4:  # Some points are identical
        return False
    x_coords = sorted(set(pt[0] for pt in points))
    y_coords = sorted(set(pt[1] for pt in points))
    if not (len(x_coords) == len(y_coords) == 2):  # Points are not aligned 2 by 2 on x and on y
        return False
    # We now know we have a rectangle
    if not (x_coords[1] - x_coords[0] == y_coords[1] - y_coords[0] == square_side):
        # Not a square, or not the right size
        return False
    return True

def find_square(pts_list, square_side=1):
    result = []
    for pts in combinations(pts_list, 4):
        if is_square(pts, square_side):  # Retrieve the right point
            result.append([max(pt[0] for pt in pts), max(pt[1] for pt in pts)])
    return result

print(find_square(a, 1))

然而，它的时间复杂度为Theta(N⁴)。但是，由于列表按x排序，并且仅包含整数坐标，且正方形大小必须为1，因此在最坏情况下可以使用Theta(N²)解决问题，在平均情况下甚至可以使用Theta(N)解决问题（请参见Alex's answer）。

- gdelab

3

很遗憾，这个解决方案的时间复杂度为O(N^4)，但如果输入是有序的，最坏情况下可以在O(N^2)的时间内完成，而最好情况下仅需要O(N)的时间。 - Alex Sveshnikov

是的，你说得对（如果索引都是整数，这似乎是情况）。很好的解决方案！ - gdelab

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alex Sveshnikov · Accepted Answer

好的，也许像这样：

def find_square(a):
    result = []
    for (bl, tl, br, tr) in zip(a, a[1:], a[2:], a[3:]):
        if bl[0] == tl[0] and br[0] == tr[0] and \
           bl[1] == br[1] and tl[1] == tr[1] and \
           br[0] - bl[0] == tl[1] - bl[1]:
           result.append(tr)
    return result

变量的名称为bl表示左下角，tl表示左上角，br表示右下角，tr表示右上角。在if的第一行中，我们检查x坐标，在第二行中 - 检查y坐标，在第三行中我们检查它是一个正方形，而不是矩形。 对于新条件进行更新：

def find_square(a):  
    d = {}
    for p1, p2 in zip(a, a[1:]):
        if p2[0] == p1[0] and p2[1] == p1[1] + 1:
            d.setdefault(p1[1], []).append(p1[0])
    result = []
    for y, xs in d.items():
        for x1, x2 in zip(xs, xs[1:]):
            if x2 == x1 + 1:
                result.append([x2, y + 1])
    return result

解释：首先我们遍历数组，查找有另一个点在其正上方的点。如果我们找到这样的点，那么我们向字典d添加一个新值。键是竖直坐标，值将包含可能的x坐标列表。在下一个循环中，我们只需遍历这些x坐标列表中的每个列表，并检查列表是否包含两个连续的x坐标。如果是，则我们找到了一个正方形。