algorithm - 多边形的最小边界矩形

Question

假设我们有一个类/结构点

class Point
{
 int x;
int y;
}

和一个包含点列表的多边形类

class Polygon
{
  List<Point> points;

  Path(List<Point> points)
  {
  //some implementation
  }
}

我有兴趣找到多边形的最小边界矩形点（https://en.wikipedia.org/wiki/Minimum_bounding_rectangle）。找到的最小边界矩形边可能不平行于两个轴，所以我试图找到一种用 Java、C#、C++ 编写的算法。任何人都可以提出或链接这样的解决方案，谢谢！

标签： algorithm

Answer 1

可以使用旋转卡尺方法构建最小边界框（最小面积和最小周长）。

您可以在此返回存档页面找到说明

包围凸多边形 P 的最小面积矩形的边与多边形的边共线。

上述结果极大地限制了可能的矩形范围。不仅不需要检查所有方向，而且只需检查多边形的边数即可。

说明上述结果：四条支撑线（红色）与一条边重合，确定封闭矩形（蓝色）。

一个简单的算法是为每条边计算与其共线的相应矩形。但是这个矩形的构造将意味着为每条边计算多边形的极值点，这个过程需要 O(n) 时间（对于 n 条边）。整个算法将具有二次时间复杂度。

可以找到更有效的算法。可以使用旋转卡尺在恒定时间内更新它们，而不是重新计算极值点。实际上，考虑一个凸多边形，有两对支撑线穿过 x 和 y 方向上的所有四个常见极值点。这四行已经确定了多边形的封闭矩形。但除非多边形有水平或垂直边，否则这个矩形不是最小面积的候选。但是，可以旋转线条直到满足上述条件。此过程是以下算法的核心。假设输入是一个凸多边形，其中 n 个顶点按顺时针顺序给出。

计算多边形的所有四个极值点，并将它们称为 xminP、xmaxP、yminP ymaxP。

通过所有四个点为 P 构建四条支撑线。这些决定了两组“卡尺”。

如果一条（或多条）线与一条边重合，则计算由四条线确定的矩形面积，并保持最小。否则，认为当前最小面积是无限的。

顺时针旋转线条，直到其中之一与其多边形的边缘重合。

计算新矩形的面积，并将其与当前最小面积进行比较。如有必要，更新最小值，跟踪确定最小值的矩形。

重复步骤 4 和 5，直到线条旋转大于 90 度的角度。输出包围矩形的最小面积。因为两对“卡尺”确定了一个封闭矩形，所以该算法考虑了所有可能具有最小面积的矩形。此外，除了初始化之外，算法的主循环中只有与顶点一样多的步骤。因此该算法具有线性时间复杂度。