Как получить программу для идентификации квадрата из массива координат?

Question

Я пытаюсь создать программу, в которой пользователь может щелкнуть внутри квадратов сетки и создать квадраты, используя PyQt5 (QPainter), но у меня возникают проблемы с тем, чтобы программа распознала, когда и где рисовать линии. Все точки нажатия сохраняются в списке.

clicked0 = [] #clicked points
distlist0 = [] # list of distances between 2 points
distdict0 {} = # dictionary to identify which two points go with each distance
#there are versions of these for both player 0 and player 1

Это код, который я использовал, чтобы заставить программу распознавать и рисовать квадраты:

    for i in list(itertools.combinations(clicked0, 2)):
        woo = list(chain.from_iterable(i))
        dist = math.hypot(woo[2]-woo[0],woo[3]-woo[1])
        distlist0.append(dist)
        distdict0[str(dist)] = "("+str(woo[0])+","+str(woo[1])+"), ("+str(woo[2])+","+str(woo[3])+")"
    listy = list(itertools.combinations(distlist0, 4))
    for i in listy:
        if i[0] == i[1] and i[0] == i[2] and i[0] == i[3]:
            for item in i:
                diction = list(chain.from_iterable(distdict0.get(str(item))))
                diction = [int(diction[1]),int(diction[3]),int(diction[8]),int(diction[10])]
                x,y = self.cell2coord(diction[0],diction[1]) #method to turn grid coords into x,y coords
                x2,y2 = self.cell2coord(diction[2],diction[3])
                qp.setPen(QPen(QColor(40, 85, 66), 5))
                qp.drawLine(x, y, x2, y2)

Это приводит к замедлению и падению Python, но вот визуальный результат:

Линии должны соединять цветные области сетки (углы), когда из них можно создать квадраты. Я работал над этой частью своего кода в течение нескольких часов, и я просто не уверен, что могу сделать, чтобы упростить / исправить процесс.

Answer 1

Начиная со всех точек в списке, возьмите первую точку и удалите ее из списка. Исходя из этого, итеративно выбирайте каждую следующую точку в списке и принимайте ее за конечную точку сегмента, начинающегося с первой точки. Для каждого сегмента будет два других квадрата, чтобы проверить, является ли этот сегмент частью возможного квадрата. Если это так, продолжайте проверять два других угла (чьи два возможных местоположения теперь зафиксированы.) В любом случае переходите к следующей точке, чтобы создать тестируемый сегмент, пока не будут проверены все сегменты, начинающиеся с первой отмеченной точки.

Повторяйте вышеупомянутое (вставляя следующую точку и проверяя все ее сегменты), пока в списке не будет меньше 4 пунктов.

Это O (N ^ 2). Чтобы проверить, заполнен ли квадрат, вы можете использовать квадратный массив, но решение лучше масштабируется до более крупных сеток, если вы используете dict, ключом которого являются координаты (x, y) (содержимое может быть цветом.)

Использование комбинаций приведет к гораздо большему количеству случаев. С 100 очками, это 3921225 комбинаций. В приведенном выше алгоритме это n (n-1) / 2 = 4950.

Я подозреваю, что я решаю чью-то домашнюю задачу, но в интересах изучения, вот код для поиска набора квадратов, где квадрат - это набор из четырех точек.

#/usr/bin/python3

points = [ (0, 0), (0, 2), (0, 4), (2, 0), (2, 2), (2, 6), (4, 4) ]

grid = {}
for point in points:
    grid[point] = 1

squares = set()     # set of frozenset(p1, p2, p3, p4), each defining a square
while len(points) >= 4:
    p1 = points.pop()
    for p2 in points:
        dx = p2[0] - p1[0]
        dy = p2[1] - p1[1]
        for delta in [(dy, -dx), (-dy, dx)]:
            p3 = (p2[0] + delta[0], p2[1] + delta[1])
            if grid.get(p3, False):
                p4 = (p3[0] - dx, p3[1] - dy)
                if grid.get(p4, False):
                    square = frozenset((p1, p2, p3, p4))    # frozen so it can be a set element
                    squares.add(square) # might be duplicate but that's OK
                break

for square in squares:
    print(list(square))

Выход:

[(0, 4), (4, 4), (2, 6), (2, 2)]
[(2, 0), (0, 0), (0, 2), (2, 2)]

Answer 2

Один из способов сделать это - перебрать все координаты и проверить, образуют ли они квадрат, например, так:

Обратите внимание: эта функция работает только для прямоугольников, ортогональных исходным осям, для наклонных прямоугольников, см. Ниже

def rectangle(a, b, c, d):
        #sort points so they can easily be compared
        points = sorted([a, b, c, d])
        #check if corners line up
        if points[0][0] == points[1][0] and\
           points[0][1] == points[2][1] and\
           points[2][0] == points[3][0] and\
           points[1][1] == points[3][1]:
                   return True
        return False

#example data
lst_points = [[1,1],
              [1,2],
              [2,2],
              [2,1],
              [3,2],
              [4,5],
              [6,7],
              [4,2],
              [2,5]]

#loop over all sets of 4 points
for i in range(len(lst_points)):
        for j in range(i+1, len(lst_points)):
                for k in range(j+1, len(lst_points)):
                        for l in range(k+1, len(lst_points)):
                              #check if rectangle   
                              if rectangle(lst_points[i],
                                             lst_points[j],
                                             lst_points[k],
                                             lst_points[l]):
                                        print lst_points[i], lst_points[j], lst_points[k], lst_points[l]

Это выводит

[1, 1] [1, 2] [2, 2] [2, 1]
[2, 2] [4, 5] [4, 2] [2, 5]

Только два квадрата в списке примеров

Рисовать линии с использованием этих данных должно быть относительно легко.

Эта функция также проверяет наличие прямоугольников под углом.

import numpy as np

def rectangleII(a,b,c,d):
        points = sorted([a,b,c,d])
        V1 = np.array(points[1]) - np.array(points[0])
        V2 = np.array(points[2]) - np.array(points[0])
        V3 = np.array(points[3]) - np.array(points[2])
        V4 = np.array(points[3]) - np.array(points[1])
        if np.all(V1 == V3) and np.all(V2 == V4):
                if np.dot(V1, V2) == 0:
                        return True
        return False