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

Question

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

pythonalgorithmgeometrycomputational-geometry

4

我有一组 1x1 的多边形，每个都由其边界（一组四个点）定义，我在我的代码示例中使用以下函数 area() 来创建这些。我希望将相邻的正方形合并为单个多边形，该多边形也以其边界点的形式定义。

我希望通过粗暴的方法来实现这一目标，即首先添加两个相邻的 1x1 正方形，使用下面的函数 join() 来创建一个更大的多边形，并按照此方式继续增加多边形的大小。因此，join 的第一个参数是迄今为止的多边形，第二个参数是要添加到多边形中的相邻的 1x1 正方形。返回值是新多边形的边界，current 与新的 1x1 合并。

这是我目前的想法：

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

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

谢谢！

- Baz

从您的描述中很难理解输入和所需输出是什么。请澄清。 - Roman Susi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- 6502 · Accepted Answer

我认为你的算法很难修复。例如，添加一个正方形到多边形中可能会创建多个孔：

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

例如，想象一下所有的x都是“当前多边形”，然后你再添加y...

通常，封闭区域由封闭回路的集合定义，您可以仅使用单个列表，只需使用更复杂的方法在回路之间创建零面积桥梁即可。对于我认为您正在寻找的简单方法是完全不同的：

循环每个正方形，对于每个正方形：
如果正方形内部且左侧正方形外部（或反之），则您知道需要在左侧建造墙壁
如果正方形内部且上方正方形外部（或反之），则您知道需要在上方建造墙壁
将所有边缘收集到字典中，在每个坐标对上保留所有开始或到达该边缘的所有墙壁的列表
扫描完成后，您可以通过从任何墙壁开始并继续跟随链直到回到初始点来重新构建结果回路...如果到达某一点时有多个选择可用于继续行走，则选择其中任何一个。

如果您正确收集了数据并且假设您可以在数据周围添加一个“外部”单元的边框，则保证您将获得零个或多个封闭回路的列表，因为每个点将列出偶数个墙壁。

这些循环（考虑奇偶填充规则）将定义您的初始区域。请注意，您可能会获得自相交的循环……如果要避免这种情况，则算法会稍微复杂一些。

这种方法比逐个处理边界并进行所有合并操作快得多，结果是通用的（包括非连接区域和孔）。

编辑

下面的图像是此算法的完整实现的结果，包括在周期收集过程中进行右转逻辑以避免自相交循环。不同的颜色已分配给输出多边形，并且角落已被切割以使转弯明显。

output of the cycle collection algorithm