Как распознать квадрат в растровом изображении?

Question

я наткнулся на этот вопрос интервью:

• В виде N х N би-одномерный массив логических элементов, как определить, если значения образуют квадрат?

Например:

true true true true 
true false false true 
true false false true 
true true true true 

образуют квадрат.

Я понял, что мне нужно начать с проверки, есть ли квадрат посередине (если N нечетно, что всегда верно), а затем рекурсивно проверяя значения по периметру.

• Это лучший способ сделать это или есть лучший, быстрый способ узнать?

Answer 1

Скрест можно определить двумя точками. Скажем, левая верхняя точка (x1,y1) и правая нижняя точка (x2,y2). И, давайте использовать 1 как true, и 0 как false.

Рассмотрим массив:

array = [None] * 5 
array[0] = [1, 1, 1, 1, 0] 
array[1] = [1, 0, 0, 1, 0] 
array[2] = [1, 0, 0, 1, 0] 
array[3] = [1, 1, 1, 1, 0] 
array[4] = [1, 0, 0, 1, 0] 

Это, очевидно, что (0,0)(3,3) образует квадрат в этом случае. И мы могли бы найти имущество, которое:

Квадрат формируется, если и только если:

• Добавив две строки границы вместе, вы получите последовательность 2; Длина последовательности равна расстоянию между двумя границами строк.

• Добавляя две границы столбцов вместе, вы получите последовательность 2; Длина последовательности равна расстоянию между двумя границами столбца.

---

Эксплуатируя свойство выше, вы получите алгоритм:

row_segment = [] 
col_segment = [] 
for v1 in range(len(array)): 
    for v2 in range(v1+1, len(array)): 
     add_row = [array[v1][col]+array[v2][col] for col in range(len(array))] 
     add_col = [array[row][v1]+array[row][v2] for row in range(len(array))] 
     row_distance = v2-v1 
     row_sum = sum(add_row[:row_distance+1]) 
     col_sum = sum(add_col[:row_distance+1]) 
     for i in range(len(array)-row_distance): 
      j = i+row_distance 
      if row_sum == 2*(row_distance+1): 
       row_segment.append([v1, i, v2, j]) 
      if col_sum == 2*(row_distance+1): 
       col_segment.append([i, v1, j, v2]) 
      row_sum = row_sum - add_row[i] + add_row[j+1] if j+1 < len(array) else None 
      col_sum = col_sum - add_col[i] + add_col[j+1] if j+1 < len(array) else None 

for i in row_segment: 
    if i in col_segment: 
     print "Square ({x1}, {y1}) ({x2}, {y2})".format(x1=i[0], y1=i[1], x2=i[2], y2=i[3]) 

---

Давайте несколько тестов:

Тест 1:

0 0 0 0 0 
0 0 1 1 1 
0 0 1 0 1 
0 0 1 1 1 
0 0 0 0 0 

Square (1, 2) (3, 4) 

Тест 2:

0 0 0 0 0 
1 1 1 1 1 
1 0 1 0 1 
1 1 1 0 1 
0 0 1 1 1 

Square (1, 0) (3, 2) 

Тест 3:

0 0 0 0 0 
1 1 1 1 1 
1 0 1 0 1 
1 1 1 1 1 
0 0 0 0 0 

Square (1, 0) (3, 2) 
Square (1, 2) (3, 4) 

Тест 4:

1 1 1 1 1 
1 0 1 0 1 
1 1 0 0 1 
1 0 0 1 0 
1 1 1 1 1 

No squares found