python - 将正方形添加到由正方形组成的多边形

Question

我有一个 1*1 多边形的集合，每个多边形都由其边界(一组四个点)定义，我在我的代码示例中使用下面的函数 area() 来创建这些。我希望将这些相邻的正方形组合成一个多边形，该多边形也根据其边界点定义。

我希望以蛮力方式执行此操作，我首先使用下面的函数 join() 添加两个相邻的 1*1 正方形以创建更大的多边形，然后按顺序继续这种方式增长多边形。所以 join 的第一个参数是到目前为止的多边形，第二个参数是一个我希望添加到多边形的邻接 1*1 正方形。返回值是新多边形的边界，当前与新的 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)

这给了我以下多边形形状(数字代表其组成方 block 的添加顺序):

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 都是“当前多边形”，然后您 andd y...

一般来说，闭合​​区域由闭合环的集合定义，您只能使用一个列表，使用更复杂的方法在环之间创建零面积桥。在我看来，您正在寻找的一种简单方法是完全不同的:

1. 在每个方 block 上循环并针对每个方 block :
2. 如果正方形在里面而左边的正方形在外面(反之亦然)那么你知道你需要在左边有一堵墙
3. 如果正方形在里面而上面的正方形在外面(反之亦然)那么你知道你需要在上面有一堵墙
4. 在字典中收集所有边，对于每个坐标对，您都保留一个列表，列出所有开始或到达该边的墙
5. 扫描完成后，您可以通过从任何一面墙开始并一直沿着链条直到回到初始点来重建生成的循环...以防万一您到达某个点时有多个选择用于继续行走的墙，然后选择其中任何一个。

如果您正确地收集了数据并假设您可以在数据周围添加一个“out”单元格的边框，那么可以保证您将得到一个包含零个或多个闭环的列表，因为每个点都会列出一个偶数的墙壁。

这些循环(当考虑奇偶填充规则时)将定义您的初始区域。请注意，如果您想避免算法稍微复杂一些，您可能会得到自相交的循环。

这种方法也比一次处理一个边界并执行所有这些合并操作快得多，结果将是通用的(包括非连接区域和孔)。

编辑

下图是a complete implementation of this algorithm的结果在循环收集期间包括右转逻辑以避免自相交循环。已为输出多边形分配了不同的颜色，并且已切角以使转弯明显。