python - 从 2D 列表中找到形成正方形的 4 个点

Question

我在下面有一个 2D 列表:

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 的正方形并返回右下角的点。实现此代码的更好方法是什么？

假设二维列表按 x 坐标的升序排序。

更新:

我发现一个案例，我的代码有问题:

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

点[7, 13]让我的代码无法检测到正方形。

Answer 1

好吧，也许是这样的:

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坐标。如果是，那么我们找到了一个正方形。