从二维列表中查找4个形成正方形的点

Question

我有一个二维列表如下：

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]使我的代码无法检测到正方形

Answer 1

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

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）

Answer 2

嗯，也许是这样的：

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