给定平面中的一组点,找到包含它们的最小区域的(不一定是凸的)多边形

Question

给定平面中的一组点,我想找到包含所有点的最小多边形.更确切地说,该多边形的顶点必须是原始点集的子集.

最简单的方法是找到凸包,可以使用格雷厄姆的扫描算法在O(N log(N))时间内计算,但我理想的是要放弃多边形为凸的要求.对此有任何标准方法吗？我认为这个问题有点难度,因为在我看来并不能保证是一个独特的解决方案.

Answer 1

您需要绝对最小面积的解决方案还是只需要"相当不错"的解决方案.如果是后者那么一种可能的算法是:1)计算所有点的凸包 - 所有这些点必须是最终解的顶点.2)计算剩余点的凸包 - 重复此过程直到没有剩余点.最终会得到n个不相交的凸包.3)通过在相邻船体中的相邻点之间添加线对并去除船体中的线来确定(可能通过贪婪算法)在何处连接这些船体以在所有点之间形成单个连续路径.

这可能不是最小的区域,但应该是一个相当不错的解决方案.

补充评论:从最外层船体到下一个内层船体的贪婪移除应该是通过移除分隔两者的最大区域区域.从第二个船体到下一个内部的贪婪移除应该是"移除"(实际上是保留)分隔船体的最小区域......依此类推,在最大和最小区域之间进行交换......

图片添加解释比我的100字更好.