Начиная со всех точек в списке, возьмите первую точку и удалите ее из списка. Исходя из этого, итеративно выбирайте каждую следующую точку в списке и принимайте ее за конечную точку сегмента, начинающегося с первой точки. Для каждого сегмента будет два других квадрата, чтобы проверить, является ли этот сегмент частью возможного квадрата. Если это так, продолжайте проверять два других угла (чьи два возможных местоположения теперь зафиксированы.) В любом случае переходите к следующей точке, чтобы создать тестируемый сегмент, пока не будут проверены все сегменты, начинающиеся с первой отмеченной точки.
Повторяйте вышеупомянутое (вставляя следующую точку и проверяя все ее сегменты), пока в списке не будет меньше 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)]