将分割的多边形分组为 N 个连续的形状

Question

给定以下多边形，它被划分为子多边形，如下图 [左] 所示，我想创建 n 个连续的、大小相同的子多边形组 [右，其中 n=6]。子多边形没有规则的图案，但保证它们是连续的并且没有孔。

这不是将一个多边形分割成相等的形状，而是将其子多边形分组为相等的、连续的组。初始多边形可能没有多个可被 n 整除的子多边形，在这些情况下，大小不等的组是可以的。我拥有的唯一数据是 n、要创建的组数以及子多边形及其外部的坐标 shell（通过剪辑库生成）。

我目前的算法如下：

list sub_polygons[] # list of polygon objects

for i in range(n - 1):
    # start a new grouping
    pick random sub_polygon from list as a starting point
    remove this sub_polygon from the list
    add this sub_polygon to the current group

    while (number of shapes in group < number needed to be added):
        add a sub_polygon that the group borders to the group
        remove this sub-polygon from the sub-polygons list

add all remaining sub-shapes to the final group

然而，这会遇到连续性问题。下面说明了这个问题——如果红色多边形被添加到蓝色组，它会切断绿色多边形，这样它就不能添加到任何其他东西来创建一个连续的组。

在组中添加子多边形的时候加个勾这个很简单，比如

if removing sub-polygon from list will create non-contiguous union
   pass;

但这会遇到边缘条件，在这种情况下，可以添加的每个可能的形状都会创建可用子多边形的非连续并集。在下面，我当前的算法正在尝试向红色组添加一个子多边形，并且通过检查连续性无法添加任何：

有没有更好的子多边形分组算法？

Answer 1

我想你可以按照程序进行：

取一些位于当前多边形周长上的连续子多边形组（如果周长上的多边形数量小于该组的目标大小，则只取所有子多边形，然后取更多需要从下一个周边开始，并重复直到达到目标群体规模）。
删除该组并考虑由剩余子多边形组成的新多边形。
重复直到剩下的多边形为空。

实施由您决定，但此方法应确保所有形成的组都是连续的，并且在步骤 2 中形成的剩余多边形是连续的。

编辑：

没关系，user58697 提出了一个很好的观点，上述算法的一个反例是一个 8 字形的多边形，其中一个子多边形连接另外两个多边形。

Answer 2

我认为单次解决比较复杂运行。尽管用于选择下一个多边形的标准，它可能会在中间某处储存。因此，在这种情况下，您需要一种可以返回并更改先前决策的算法。这样做的经典算法是 BackTracking。

但在开始之前，让我们更改问题的表示。这些多边形形成这样的图形：

这是算法的伪代码：

function [ selected, stop ] = BackTrack(G, G2, selected, lastGroupLen, groupSize)
    if (length(selected) == length(G.Node))
        stop = true;
        return;
    end
    stop = false;
    if (lastGroupLen==groupSize)
        // start a new group
        lastGroupLen=0;
    end;
    // check continuity of remaining part of graph
    if (discomp(G2) > length(selected))
        return;
    end

    if (lastGroupLen==0)
        available = G.Nodes-selected;
    else
        available = []
        // find all nodes connected to current group
        for each node in last lastGroupLen selected nodes
            available = union(available, neighbors(G, node));
        end
        available = available-selected;
    end
    if (length(available)==0)
        return;
    end
    lastSelected = selected;
    for each node in available
        [selected, stop] =  BackTrack(G, removeEdgesTo(G2, node), 
            Union(lastSelected, node), lastGroupLen+1, groupSize);
        if (stop)
            break;
        end
    end
end

其中：
selected：一个有序的节点集，可以分成n个连续的组
stop：找到解决方案时变为真
G：初始图
G2: 移除最后一个选定节点的所有边后图形的剩余部分
lastGroupLen: 最后一组选择的节点数
groupSize：每个组的最大允许大小
discomp(): returns 图的不连续分量数
removeEdgesTo(): 删除连接到节点的所有边

应该这样称呼：

[ selected, stop ] = BackTrack( G, G, [], 0, groupSize);

我希望你已经足够清楚了。它是这样的：

请记住，该算法的性能可能会受到节点顺序的严重影响。加快速度的一种解决方案是按质心对多边形进行排序：

但如果你和我一样对这个结果不满意，还有另一种解决方案。您可以在 G2 中按度数对 available 节点集进行排序，因此在每个步骤中，将首先访问不太可能使图断开连接的节点：

作为一个更复杂的问题，我测试了伊朗有 262 个县的地图。我将 groupSize 设置为 20:

将分割的多边形分组为 N 个连续的形状

Group divided polygon into N contiguous shapes

algorithm

geometry

polygon