向由正方形组成的多边形添加正方形

Question

我有一组1*1的多边形，每个多边形是由它的边界（四个点组成）来定义的。我在下面的代码示例中使用了area()这个函数来创建这些多边形。我希望把相邻的这些正方形合并成一个更大的多边形，这个新多边形同样是通过它的边界点来定义的。

我想用一种简单粗暴的方法来实现这个目标，首先我会把两个相邻的1*1正方形合并，形成一个更大的多边形，使用下面的join()函数。这个函数的第一个参数是当前的多边形，第二个参数是我想要添加的相邻的1*1正方形。这个函数会返回新多边形的边界，也就是current和新的1*1正方形合并后的结果。

这是我目前的进展：

def join(current, new):
    """ current is the polygon, new the 1*1 square being added to it"""
    return get_non_touching_part_of_boundary(current, new)  + get_non_touching_part_of_boundary(new, current)

def get_non_touching_part_of_boundary(this, other):
    for i,point in enumerate(this):
        if point not in other and this[i-1] in other:
            break # start of non touching boundary from a clockwise perspective
    non_touching_part_of_boundary = []
    for point in this[i:] + this[:i]:
        if not point in other:
            non_touching_part_of_boundary.append(point)
    return non_touching_part_of_boundary    

def area(point):
    """ boundary defined in a clockwise fashion """
    return [point,(point[0],point[1]+1),(point[0]+1,point[1]+1),(point[0]+1,point[1])]

a = area((0,1))            # a assigned a 1*1 polygon
a = join(a, area((0,2)))   # a assigned a 2*1 polygon
a = join(a, area((1,2)))    
a = join(a, area((2,2)))    
a = join(a, area((2,1)))    
a = join(a, area((2,0)))    

print(a)

这样我得到了以下的多边形形状（数字表示添加这些正方形的顺序）：

234
1 5
  6

上面代码的输出结果是：

[(2, 2), (1, 2), (1, 1), (0, 1), (0, 3), (3, 3), (3, 0), (2, 0)]

这是定义多边形边界所需的最少点数。

但是如果我通过a = join(a, area((1,0)))再添加一个正方形，形成一个洞，我的算法就崩溃了：

234
1 5
 76

这是另一个我的算法无法处理的多边形：

123
 64
  5

有人能帮我吗？我希望多边形中的洞能被列在一个单独的列表中。

谢谢！

Answer 1

我觉得你的算法有点难以修复。比如说，给一个多边形添加一个方块，可能会产生好几个洞：

  xxx
  x x
xxx xxx
x  y  x
xxx xxx
  x x
  xxx

想象一下，所有的 x 代表“当前的多边形”，然后你再加上 y...

一般来说，一个封闭的区域是由一系列封闭的环组成的。你可以用一个列表来处理，但这需要更复杂的方法来在这些环之间建立“零面积”的桥梁。看起来你想要的简单方法其实是完全不同的：

1. 对每个方块进行循环，对于每一个方块：
2. 如果这个方块在里面，而左边的方块在外面（或者反过来），那么你就知道左边需要一堵墙。
3. 如果这个方块在里面，而上面的方块在外面（或者反过来），那么你就知道上面需要一堵墙。
4. 把所有的边收集到一个字典里，对于每一对坐标，记录所有从这个边开始或到达的墙。
5. 扫描完成后，你可以通过从任何一堵墙开始，沿着链条一直走，直到回到起点来重建结果的环... 如果在某个点到达时有多个选择可以继续走哪堵墙，那就随便选一堵。

如果你正确地收集了数据，并且假设你可以在数据周围加上一圈“外部”单元格，那么结果一定会是一个包含零个或多个封闭环的列表，因为每个点会列出偶数个墙。

这些环（在考虑奇偶填充规则时）将定义你的初始区域。注意，你可能会得到自交的环... 如果想避免这种情况，算法会稍微复杂一些。

这种方法比逐个处理边界和进行合并操作要快得多，结果也会更通用（包括不相连的区域和洞）。

编辑

下面的图片是 这个算法的完整实现 的结果，包含了在循环收集过程中避免自交循环的右转逻辑。不同的颜色被分配给输出的多边形，角落被切掉以使转弯明显。