geometry - 分解为凸多边形

Question

这个问题有点牵强。我写了一个算法来分解 simple polygon到凸子多边形中，但现在我无法证明它不是最佳的(即使用斯坦纳点(添加的顶点)的凸多边形数量最少)。我的教授坚持认为不能用像这个这样的贪婪算法来完成，但我想不出反例。

所以，如果有人能证明我的算法是次优的(或最优的)，我将不胜感激。

用图片解释我的算法的最简单方法(这些来自较旧的次优版本)



我的算法所做的是围绕点 i 延伸线段，直到它碰到对边上的一个点。

如果这个范围内没有顶点，它会创建一个新的(红点)并连接到它:



如果范围内有一个或多个顶点，它会连接到最近的顶点。这通常会产生具有最少凸多边形数量的分解:



然而，在某些情况下它可能会失败——在下图中，如果它碰巧先连接中间的绿线，这将创建一个额外的不需要的多边形。为此，我建议仔细检查我们添加的所有边(对角线)，并检查它们是否仍然是必要的。如果没有，请将其删除:



然而，在某些情况下，这还不够。看这个图:



用 a-c 替换 a-b 和 c-d 会产生更好的解决方案。但是，在这种情况下，没有要移除的边缘，因此这会带来问题。在这种情况下，我建议优先顺序:在决定将反射顶点连接到哪个顶点时，它应该选择具有最高优先级的顶点:

最低)最近的顶点

med) 最近的反射顶点

最高)在向后工作时也在范围内的最近反射(难以解释)-

在 this figure ，我们可以看到反射顶点 9 选择连接到 12(因为它最接近)，当连接到 5 时会更好。顶点 5 和 12 都在由延长线段 10- 定义的范围内9 和 8-9，但应优先考虑顶点 5，因为 9 在 4-5 和 6-5 给出的范围内，但不在 13-12 和 11-12 给出的范围内。即边 9-12 消除了 9 处的反射顶点，但不会消除 12 处的反射顶点，但它可以消除 5 处的反射顶点，因此应优先考虑 5。

使用此修改版本时，边缘 5-12 可能仍然存在，但可以在后处理过程中将其删除。

有没有我错过的案例？

伪代码(由 John Feminella 请求)——这缺少图 3 和图 5 下的位

assume vertices in `poly` are given in CCW order
let 'good reflex' (better term??) mean that if poly[i] is being compared with poly[j], then poly[i] is in the range given by the rays poly[j-1], poly[j] and poly[j+1], poly[j]

for each vertex poly[i]
    if poly[i] is reflex
        find the closest point of intersection given by the ray starting at poly[i-1] and extending in the direction of poly[i] (call this lower bound)
        repeat for the ray given by poly[i+1], poly[i] (call this upper bound)

        if there are no vertices along boundary of the polygon in the range given by the upper and lower bounds
            create a new vertex exactly half way between the lower and upper bound points (lower and upper will lie on the same edge)
            connect poly[i] to this new point
        else
            iterate along the vertices in the range given by the lower and upper bounds, for each vertex poly[j]
                if poly[j] is a 'good reflex'
                    if no other good reflexes have been found
                        save it (overwrite any other vertex found)
                    else
                        if it is closer then the other good reflexes vertices, save it
                else
                    if no good reflexes have been found and it is closer than the other vertices found, save it
            connect poly[i] to the best candidate
        repeat entire algorithm for both halves of the polygon that was just split
// no reflex vertices found, then `poly` is convex
save poly

原来还有一种我没有预料到的情况:[图 5]

我的算法将尝试连接顶点 1 到 4，除非我添加另一个检查以确保它可以。因此，我建议使用我上面提到的优先级方案将“范围内”的所有内容填充到优先级队列中，然后取最高优先级的一个，检查它是否可以连接，如果不能，将其弹出并使用下一个。我认为如果我优化它，这会使我的算法 O(r n log n)。

我已经整理好了 a website这粗略地描述了我的发现。我喜欢搬东西，所以趁热拿。

Answer 1

我相信常规的五角星(例如具有共线段的交替点)是您寻求的反例。

回复评论编辑

根据我修改后的理解，修改后的答案:尝试锐角五角星(例如， ARM 足够窄，只有与您正在处理的反射点相对的 ARM 的三个点在被认为是“良好的反射点”的范围内)。至少在纸上完成它似乎提供了比最佳效果更多的东西。然而，最后阅读你的代码让我想知道:“最接近”(即最接近什么)是什么意思？

备注

尽管我的回答被接受了，但这并不是我们最初认为的反例。正如@Mark 在评论中指出的那样，它在与最佳状态完全相同的时间从 4 变为 5。

人字拖、人字拖

进一步反射(reflection)，我认为我毕竟是对的。通过简单地确保一对臂具有共线边缘，可以在锐角星中保留四个的最佳界限。但是算法找到了五个，即使打了补丁。

我明白了:

删除无效的 ImageShack 链接

当最佳是这样的:

删除无效的 ImageShack 链接