在坐标系中划定正方形

Question

我有一个 3 格乘 3 格的棋盘，看起来像这样：

每个正方形的边表示为一个元组，包含边的起始坐标和结束坐标，例如：

((0,0), (0,1))

不同之处在于，在任何时候都可以删除这些边中的一个。留个方块不完整。

我正在尝试在 Python 中编写一个算法来检测棋盘上的方块。

棋盘的数据保存在一个字典中，其中键是边，对应的值是布尔值，表示边当前是否在位，它看起来有点像这样：

   Graph=  {((0, 0), (0, 1)): True,
            ((0, 0), (1, 0)): True,
            ((0, 1), (0, 2)): True,
            ((0, 1), (1, 1)): True,
            ((0, 2), (0, 3)): True,
            ...}

目前，如果我遍历板上的所有点，我只能找出是否有完整的 1x1 正方形，方法是找到附近的边并检查它们是否在我的图表中设置为 True。我目前正在通过这样做找到起点附近的边缘（它总是在正方形的左下角）：

((x,y)为起点坐标)

left = ([edge for edge in graph if (x,y) in edge and (x, y+1) in edge])
right = ([edge for edge in graph if (x+1, y) in edge and (x+1, y+1) in edge])
top = ([edge for edge in graph if (x, y+1) in edge and (x+1, y+1) in edge])
down = ([edge for edge in graph if (x, y) in edge and (x+1, y) in edge])[0]

我在这里使用列表理解，因为边缘的方向目前是任意的，而不是直接访问（例如）图中的 ((1,0),(1,1))，我需要搜索它以查看它是否具有那或 ((1,1),(1,0)).

尽管有点复杂，但令我困扰的是我无法想出一种方法来检查更大尺寸的正方形。例如，我还需要检查 2x2 和 3x3（如果 (0,0) 是起点）正方形，因此我的方法是不可持续的。

例如，我需要检测一个从(0,0)开始的2x2正方形，我想检测边缘为：

的正方形

left: ((0,0),(0,1)), ((0,1),(0,2))
right: ((2,0),(2,1)), ((2,1),(2,2))
top: ((0,2),(1,2)), ((1,2),(2,2))
bottom: ((0,0),(1,0)), ((1,0),(2,0))

对于混乱的代码，我深表歉意，感谢任何提示或技巧。

提前致谢。

Answer 1

这是一个起点。同样，这假设字典存储时元组已排序。这并不难。

def make_square( x,y,n ):
    for i in range(n):
        yield (x,y+i),(x,y+i+1)
        yield (x+i,y),(x+i+1,y)
        yield (x+n,y+i),(x+n,y+i+1)
        yield (x+i,y+n),(x+i+1,y+n)

print(sorted(list(make_square(0,0,3))))

# Find 2x2.

for x in range(2):
    for y in range(2):
        if all(Graph[edges] for edges in make_square(x,y,2)):
            print( f"2x2 Square starts at {x},{y}" )

# Find 3x3.

for x in range(1):
    for y in range(1):
        if all(Graph[edges] for edges in make_square(x,y,3)):
            print( f"3x3 Square starts at {x},{y}" )

"make_square" returns 从 (x,y) 开始大小为 n 的正方形边的列表。它从 4 个边中的每一个边做一个片段，然后移动到下一个片段。 “产量”只是 return 一次处理多个事物的一种可爱方式。也可以将它们中的每一个存储在一个列表中，然后 return 最后是一个列表。 “收益”使它成为发电机。

因此，在底部的循环中，我们遍历了一个正方形的每个可能的起始位置。在 3x3 中，寻找 2x2 正方形，它们可以从 (0,0)、(0,1)、(1,0) 或 (1,1) 开始。

因此，对于每个起始位置，我们 make_square 为该正方形生成边。如果列表中的所有元素都为真，则“全部”函数 return 为真。因此，对于 make_square return 列表中的每条边，我们使用 Graph[edges] 的值。如果所有 return 都为真，那么“所有”return 为真，我们就有了赢家。

在最后一个循环中，3x3 正方形只有一个起始位置。我留下了循环，因为它是对称的，但当然它们不是必需的。我希望您能看到如何将其推广到更大的平方。例如，如果您有一个 5x5 的正方形：

for subsquare in range(1,5):
    for x in range(5-subsquare+1):
        for y in range(5-subsquare+1):
...etc...

在坐标系中划定正方形

Delimiting a square in a coordinate system

python

coordinates