多边形的最小边界矩形

Question

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

class Point
{
 int x;
int y;
}

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

class Polygon
{
  List<Point> points;

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

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

Answer 1

您可以执行以下操作：

1. 查找多边形点的convex hull。流行的方法是Graham scan。

2. 对于凸包的每个边缘，找到必须具有与该边缘重叠的一侧的最小边界矩形，以便凸包的边缘是该矩形侧的子段。

   • 通过沿着凸包的顶点走动，并将顶点投影到第一侧，并保持它们之间具有所有其他投影的两个，来找到矩形的两个垂直侧。可以以类似方式找到最后的相对侧。

3. 计算这些矩形的大小，并保留最小的矩形。

此算法的复杂度由第二步确定，它是O（n²）。