凸多边形的分解

Question

这个问题有点牵扯。我编写了一个将简单多边形分解成凸子多边形的算法，但现在我很难证明它不是最优的(即使用Steiner点(增加的顶点)的凸多边形的最小数目)。我的教授坚持认为这种贪婪的算法是做不到的，但我想不出一个反例。

因此，如果有人能证明我的算法是次优(或最优)，我将感激它。

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

​

​

我的算法所做的是，将线段扩展到我所穿过的点周围，直到到达相反边缘的一个点为止。

如果在此范围内没有顶点，则会创建一个新的顶点(红色点)并连接到该区域：

​

​

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

​

​

然而，在某些情况下，它可能会失败-在下面的数字，如果它碰巧连接中间的绿色线，这将创建一个额外的不必要的多边形。对此，我建议对我们添加的所有边(对角线)进行双重检查，并检查它们是否都是必要的。否则，将其移除：

​

​

然而，在某些情况下，这还不够。见下图：

​

​

用and代替and和and会得到更好的解决方案。但是，在这种情况下，没有需要删除的边缘，因此这会带来问题。在这种情况下，我建议一个优先顺序:在决定将反射顶点连接到哪个顶点时，它应该选择优先级最高的顶点：

(最低)最近顶点

(医学)最近的反射顶点

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

在这个数字中，我们可以看到反射顶点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 )如果我优化它是正确的。

我把网站放在一起，松散地描述了我的发现。我喜欢到处移动东西，所以趁热打铁。

Answer 1

我相信普通的五点星(例如，具有共线段的交点)是你所寻找的反例。

编辑回应评论

根据我修正后的理解，修改后的答案是:尝试一颗锐利的五尖星(例如，一颗手臂足够窄的恒星，只有构成你工作的反射点对面的手臂的三个点在被认为是“良好反射点”的范围内)。至少从纸面上看，它似乎提供了比最优更多的东西。然而，对您的代码进行最后的阅读时，我想知道：“最近”(也就是最接近什么)是什么意思？

Note

虽然我的答案被接受了，但这并不是我们最初认为的反例。正如@Mark在评论中指出的那样，它与最优的时间完全相同，从4到5。

触发器，触发器

再想一想，我想我还是对的。通过简单地保证一对臂具有共线边，四的最优界可以保留在一颗锐利的恒星中。但是算法找到了五个，即使修补程序也是如此。

我明白了：

删除死ImageShack链路

当最优情况是：

删除死ImageShack链路

Answer 2

但是顶点5应该被优先考虑，因为9在4-5和6-5的范围内。

如果4-5和6-5更凸，使9不在它们的范围之内，你会怎么做？那么按照你的规则，正确的做法是将9到12连接起来，因为12是最接近的反射顶点，这将是次优的。

Answer 3

发现了:(它们其实很明显。

*死亡imageshack img*

如果允许施泰纳点的话，四叶三叶草将不是最佳选择.红色顶点可能是连在一起的。

*死亡imageshack img*

如果没有施泰纳点，这甚至都不是最优的..。5可以连接到14，消除了3-14，3-12和5-12的需要。这可能是两个更好的多边形！唉哟!