from itertools import combinations
def find_squares(a):
# Find ones
ones = [(i, j) for i, row in enumerate(a) for j, val in enumerate(row) if val]
# Make graph of connected ones
graph = {a: [] for a in ones}
for a, b in combinations(ones, 2):
if abs(a[0] - b[0]) <= 1 and abs(a[1] - b[1]) <= 1:
graph[a].append(b)
graph[b].append(a)
# Find connected components in graph
components = []
for a, a_neigh in graph.items():
if any(a in c for c in components):
continue
component = {a, *a_neigh}
pending = [*a_neigh]
visited = {a}
while pending:
b = pending.pop()
if b in visited:
continue
visited.add(b)
component.add(b)
b_neigh = graph[b]
component.update(b_neigh)
pending.extend(c for c in b_neigh if c not in visited)
components.append(component)
# Find bounds for each component
bounds = [((min(a[0] for a in c), min(a[1] for a in c)),
(max(a[0] for a in c), max(a[1] for a in c)))
for c in components]
return bounds
a = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 1, 0, 0],
[0, 0, 0, 1, 0, 0, 1, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
[0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
square_bounds = find_squares(a)
print(*square_bounds, sep='\n')
# ((1, 5), (3, 8))
# ((2, 3), (2, 3))
# ((4, 1), (5, 1))
# ((5, 3), (8, 6))
# ((6, 8), (6, 8))
# ((8, 8), (8, 8))
您可以从图形的角度来处理这个问题,其中的坐标是图形元素,8路连接-然后您只需在图形中找到连接的组件。如果数据是稀疏的,这应该比在可能的正方形大小中循环要快得多。这是它如何工作的一个例子:
这就是连通成分分析,它已经被asked and answered before。根据您的需要调整公认的答案,一个可能的解决方案非常简短:
这就是输出(没有示例):
希望有帮助
相关问题 更多 >
编程相关推荐