在下图中，数字是拟合矩形的面积。如图所示，期望的矩形可以在每个维度上变化并且可以在任何角度。
编辑：
我们没有明确的主意如何处理提到的问题，所以我们在这里问。尽管如此，我们猜测最大面积矩形
可能是其中一个边缘对齐（当然不一定是相同长度的边缘）在多边形边缘上的边缘之一。
#1 楼
一些注释过大而无法注释（尽管这并不代表一种明显的算法）：标记（编辑）：最大面积矩形的至少两个顶点必须位于边界上多边形的边（即沿边或在顶点处）。如果最大面积的矩形不是正方形，则多边形的边界上必须至少有三个顶点。我通过四个步骤向我证明了这一点：
注意＃1：最大面积矩形的至少一个顶点将始终位于多边形的边界上。这是很明显的，但是一个证明可能会这样（由于矛盾）：假设您有一个“最大”矩形，该多边形的边界上没有顶点。这意味着每个顶点周围至少要有一点空间。因此，您可以稍微扩展矩形，这与矩形的最大值相反。
注＃2：最大面积矩形的至少两个顶点将始终位于多边形的边界上。一个证明可能是这样的（再次是矛盾的）：假设您有一个“最大”矩形，边界上只有一个顶点（由注释1保证）。考虑不与该顶点相邻的两个边。由于它们的端点不在边界上，因此每个端点周围都有一点空间。因此，可以将这些边缘中的任何一个“挤出”一点，以扩展多边形的面积并使其最大值相矛盾。多边形的（我们从注释2中知道，至少有两个，但不一定是彼此对面的。）但又是矛盾的，如果只有两个边界顶点是相邻的，则相反的边（两个顶点都不在边界上）可以挤出一点，从而增加矩形的面积并与矩形的最大值相矛盾。
注意4 ：（已编辑）如果最大面积矩形不是正方形，则其三个顶点将位于多边形的边界上。最大面积矩形不是正方形，但只有两个顶点在多边形的边界上。我将展示如何构造与最大值相反的更大的矩形。
调用矩形的顶点
A，B，C和D。在不失一般性的前提下，假设B和D是多边形边界上的两个。由于A和C位于多边形的内部，因此它们周围有一些摆动空间（在下图中以A和C周围的圆圈表示）。现在，在矩形周围绘制一个圆，并将点A和C围绕该圆稍微滑动相同的量（使A'和C'如下图所示），以使新矩形A'BC'D比原始矩形更方形。此过程将创建一个新的矩形，该矩形也位于原始多边形内，并具有较大的面积。这是一个矛盾，所以证明就成立了。它变成“更大的正方形”（即，边长之间的差异变小）。您还需要将多边形设为凸面，以便所有新线都在其中。可能还有其他一些小细节被掩盖了，但是我很确定它们都能解决。评论
注意＃4是可疑的，因为“摆动”其他两个顶点将创建非矩形。
– hu
13-10-3在14:25
真正。但是，第4个示例的可视化效果不太理想（如果2个顶点在多边形边界上，则无法进一步拉伸）。我虽然找不到确切的解释方法（试图写评论，但是太混乱了），但是我相信你是对的。
–萨里克
13-10-3在14:32
我相信有一些反例来说明＃4。不过，我发现的结果需要一些涉及的计算才能显示出来；最简单的是对不规则六边形（一个带有两个相对角的正方形略去掉）的摄动。
– hu
13-10-3在15:05
同意注释4可疑。今天晚上我会仔细看一下，然后修复或删除它。
–csd
13-10-3在15:08
+1这是难度的不错解决方案。感谢您的编辑！
– hu
13-10-3在20:49
#2 楼
关于问题中的绿色音符，我已经做了一个非常快速和令人毛骨悚然的草图。我无法将其发布为评论，所以即使不是一个答案，我也必须写一个答案。在Paint上给出一个想法），我认为您找不到更大的一个，它可以与黑胶边的边界具有相同的一面...但是我可能是错的，在这种情况下，您道歉
评论
好点（+1）。但是，有一个更简单的反例：考虑在正八边形内刻出最大面积矩形的问题。很容易看到（并且很容易通过首先找到八角形外接圆的最大正方形来证明）解的角与八角形的交替顶点重合，并且该解实质上大于任何边缘对齐的内接矩形。
– hu
13-10-3在14:21
实际上（我现在有一个很大的疑问），此多边形的外部最小矩形（此帖子中的矩形）与边之一的方向不同，对吗？ （我会看到与红色矩形相同的方向）
–萨里克
2013年10月3日14:43
顺便说一下，那个多边形不是凸的。最初的问题确实限于凸多边形。
–csd
13年10月3日，14：55
@csd很好，但是如我的反例所示，Saryk仍然正确。 Saryk，最小面积边界矩形没有问题：很容易（严格地）证明它必须包含凸包的一侧。我相信（凸多边形的）最大内切矩形仅需要两个顶点接触边界。
– hu
13年10月3日在15:03
#3 楼
多数其他算法会找到凸多边形上内接的最大面积直线矩形，其复杂度为O(log n)。我不认为您猜测最大面积多边形与边之一对齐是正确的，因为您所要做的就是旋转多边形n次，导致O(n log n)的复杂性，在我的简要研究中，我无法然而，Knauer等人的论文《凸多边形中最大的内接矩形》一文却没有。等人描述了一种近似算法，可以使您接近正确的答案。
据我所知，该算法建立在已知的轴对齐最大面积多边形之一的基础上，然后在polyon空间中对点进行随机采样，从这些随机采样中生成多个轴，在这些轴上进行迭代，并对每个轴应用轴对齐算法，然后返回该集中最大的矩形。
评论
第一句话中可能有错字吗？不可能有O（log（n））算法，因为仅读取坐标就是O（n）操作！
– hu
2013年9月30日14:18在
链接已死
–dangerousdave
18年6月6日在16:55
@dangerousdave-找到了一个替代链接，不管它持续多久...。
–莱尔德
18年6月11日19:00
评论
您能指定使用什么软件吗？另外，将您的工作发布到现在为止，或者将您发布出来的通用方法来解决此问题。也许有人可以改善您已经完成的工作。以我的经验，这将带来比仅发布“突如其来的问题”更为有用的答案。密切相关：gis.stackexchange.com/questions/22895/…。
@Martin软件：如果需要，则可以使用Fortran在Python中进行编程。我们有一个猜测，基于上面我们在前面的文章中也提到过，whuber可能是一个矩形，该矩形的边缘与多边形相同。
您的问题是一个非常有趣的问题，我想我在这里和这里都能找到一种求解算法。
@nickves感谢您的链接。您能否将这些信息作为答案并给出一些算法解释？这将是一个很好的答案。