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

Question

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

4

给定以下多边形，并根据下面所示方式将其分割成子多边形[left]，我想创建n个连续、大小相等的子多边形组[右侧，其中n=6]。子多边形没有规律的模式，但保证是相邻的且没有洞。

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

我的当前算法如下：

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;

但是在某些边缘情况下，每个可以添加的形状都会创建可用子多边形的不连续联合体。在下面的示例中，我的当前算法正在尝试将一个子多边形添加到红色组中，并检查其连通性，但无法添加任何一个：

是否有更好的算法来对子多边形进行分组？

- k-a-v

2个回答

0

我认为你可以按照以下步骤进行：

取出当前多边形周长上连续的一些子多边形（如果周长上的多边形数量小于目标组大小，就取所有多边形并从下一个周长中取出所需数量，重复此过程直到达到目标组大小）。
移除这个组，并考虑由剩余子多边形组成的新多边形。
重复以上步骤，直到剩余多边形为空。

实现方法由你决定，但这种方法应确保所有形成的组都是连续的，并且在第2步形成的剩余多边形也是连续的。

编辑：

不用理会，用户58697提出了一个很好的观点，上述算法的反例是一个呈8字形的多边形，其中一个子多边形连接了另外两个多边形。

- aeternalis1

1

排除周长可能会将多边形分割成不相交的子多边形。 - user58697

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

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

- saastn · Accepted Answer

我认为这需要多次运行才能解决。无论选择下一个多边形使用的标准是什么，它可能会在中间停顿。因此，您需要一种算法，在这种情况下返回并更改以前的决策。经典的执行此操作的算法是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: 当找到解决方案时变为true
G: 初始图形
G2: 移除所有连接到最后选择的节点的边后剩余的图形
lastGroupLen: 上一组选择的节点数
groupSize: 每个组允许的最大大小
discomp(): 返回图形的不连续组件数
removeEdgesTo(): 删除与节点连接的所有边缘

应该这样调用：

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

我希望这足够清楚。它是这样的：

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

但是，如果您像我一样对此结果不满意，还有另一种解决方案。您可以按照G2中节点的度数订购available节点集，因此在每个步骤中，首先访问那些使图形断开的机会较小的节点：

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