algorithm - 找到具有给定点数的最小包含凸多边形

Question

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

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

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

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

---

编辑:

最小的多边形是指覆盖最小面积的多边形，尽管我不确定最小的周长是否会给出不同的结果。

我添加了另外两个示例图片，遗憾的是它们似乎不适用于其中一个答案中的“删除边缘”方法

---

一些背景信息:

目标是通过图像识别准确确定形状。例如，拍摄一张长方体的照片。 2D 照片中框内的所有点都将包含在一个 6 角凸多边形中。然而，由于现实世界的形状没有完美的角，并且相机添加了一些模糊，因此该多边形的边缘将变圆。 请参阅问题 Getting corners from convex points 中的附图

Answer 1

您需要在问题中定义“最小”的概念。不管你怎么定义， 这个问题已经在计算几何文献中进行了大量研究。 关键搜索短语是最小封闭 k-gon:

• Mictchell 等人:“Minimum-Perimeter Enclosing k-gon” 2006 ( CiteSeer link )
• Aggarwal 等人:“最小面积外切多边形”1985 (CiteSeer link)
• O'Rourke 等人:“寻找最小封闭三角形的最佳算法”，1986 年，Algorithmica ( ACM link )

一般的算法都不简单 (尽管最小面积三角形或矩形的算法很简单)。 根据你的目标，你可能不得不放弃任何数学概念 “最小”并进行启发式。