python - 在坐标系中划定正方形

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,
            ...}

目前，如果我遍历板上的所有点，我只能通过查找附近的边并检查它们在我的图中是否设置为 True 来确定是否有完整的 1x1 正方形。我目前正在通过执行以下操作在起点附近（始终位于正方形的左下角）找到边缘：

（(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))图中的（例如），我需要搜索它以查看它是否具有 that 或((1,1),(1,0)).

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

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

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))

我为凌乱的代码道歉，并感谢任何提示或提示。

先感谢您。

标签： pythoncoordinates

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”返回从 (x,y) 开始、大小为 n 的正方形的边列表。它从 4 个边中的每一边做一个片段，然后移动到下一个片段。“产量”只是一次返​​回多个东西的一种可爱方式。也可以将其中的每一个存储在一个列表中，然后在最后返回一个列表。“产量”使其成为发电机。

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

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

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

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