Найдите 4 точки, которые образуют квадрат из 2D списка

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

Объяснение: сначала мы go просматриваем массив и ищем точки, у которых есть другая точка чуть выше них. Если мы найдем такую ​​точку, то добавим новое значение в словарь d. Ключ является вертикальной координатой, и значение будет содержать список возможных x координат. В следующем l oop мы просто go просматриваем каждый из этих списков x координат и проверяем, содержит ли список две последовательные x координаты. Если это так, то мы нашли квадрат.

Answer 2

Решение, которое не требует, чтобы точки были последовательными, или даже список не сортировался каким-либо образом:

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) в среднем (см. ответ Алекса ) ,