找到包含给定点数的最小包含凸多边形

Question

给定一个凸polgyon和一个数字N,我如何找到最小的多边形

1. 包含原始多边形中的每个点
2. 正好有N个角点

例如,假设我有一组点并计算它们的凸包(绿色).现在我想找到包含所有点的最小四边形(红色)

很容易看出任何其他具有4个角的多边形要么更大,要么不能包含所有点.但是如何在一般情况下找到这个多边形呢？

---

编辑:

最小的多边形是指覆盖最小区域的多边形,但我不确定最小的圆周是否会产生不同的结果.

我添加了另外两个示例图片,遗憾的是,在其中一个答案中似乎没有使用"删除边缘"方法

---

一些背景资料:

目标是通过图像识别准确地确定形状.例如拍摄一个长方体的照片.2D照片中框内的所有点都将包含在6角凸多边形中.然而,由于真实世界的形状没有完美的角落,并且相机增加了一些模糊,因此该多边形的边缘将是圆形的.请参阅问题从凸点获取角落的附图

Answer 1

您需要在问题中定义"最小"的概念.无论你的定义是什么,这个问题都在计算几何文献中得到了深入的研究.关键搜索短语是最小的封闭k-gon:

• Mictchell等人:"最小周长封闭k-gon"2006(CiteSeer链接)
• Aggarwal等人:"最小面积环绕多边形"1985(CiteSeer链接)
• O'Rourke等人:"最小算法用于最小封闭三角形"1986,Algorithmica(ACM link)

一般算法并不简单(尽管最小区域三角形或矩形的算法很简单).根据您的目标,您可能不得不放弃任何"最小"的数学概念并前往启发式.