分解为凸多边形

这个问题有点牵扯.我编写了一个将简单多边形分解为凸子多边形的算法,但现在我无法证明它不是最优的(即使用Steiner点(添加顶点)的最小凸多边形数).我的教授坚持认为它不能用这样的贪婪算法来完成,但我想不出一个反例.

所以,如果有人能证明我的算法不是最理想的(或最优的),我会很感激.

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

我的算法所做的是将点线周围的线段延伸到相反的边缘上的点.

如果此范围内没有顶点,则会创建一个新的顶点(红点)并连接到该顶点:

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

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

但是,在某些情况下,这还不够.看到这个图:

用ac替换ab和cd会产生更好的解决方案.但在这种情况下,没有边缘可以移除,因此这会产生问题.在这种情况下,我建议一个偏好顺序:当决定将反射顶点连接到哪个顶点时,它应该选择具有最高优先级的顶点:

最低的)最近的顶点

med)最接近的反射顶点

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

在这个图中,我们可以看到反射顶点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(rn log n).

我整理了一个网站,松散地描述了我的发现.我倾向于移动东西,所以在它很热的时候拿它.