22

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

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

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

最小的四边形 在此处输入图像描述

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

编辑：

最小的多边形是指覆盖最小区域的多边形，尽管我不确定最小的周长是否会产生不同的结果。

我在其中一个答案中添加了另外两张示例图片，不幸的是这些图片似乎不适用于“删除边缘”方法

一些背景资料：

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

模糊的角落

4

2 回答 2

17

您需要在问题中定义“最小”的概念。无论您如何定义，计算几何文献中都对这个问题进行了深入研究。关键搜索短语是最小的封闭 k-gon：

  • Mictchell 等人：“Minimum-Perimeter Enclosure k-gon”2006（CiteSeer 链接）
  • Aggarwal 等人：“最小面积外接多边形”1985（CiteSeer 链接）
  • O'Rourke 等人：“寻找最小封闭三角形的最佳算法”，1986 年，Algorithmica（ACM 链接）

一般算法并不简单（尽管最小面积三角形或矩形的算法很简单）。根据您的目标，您可能不得不放弃任何“最小”的数学概念并采用启发式方法。

于 2012-07-22T18:20:25.333 回答
0 
While number of edges > N do
  remove the shortest edge by replacing its endpoints 
  with the intersection point of the adjacent edges
于 2012-07-22T17:31:30.303 回答