计算多边形的最小面积矩形

Question

4

我需要计算围绕多边形的最小面积矩形（最小可能的矩形）。

唯一的输入是多边形中点的数量。

我也有这些点的坐标。

- Samra

1

只有点数吗？还是你也有坐标？ - Naveen

4

这个多边形是否可以有任意方向，还是矩形必须与坐标系正交？ - Ates Goral

你需要有坐标，或者知道一条边的长度并限制所有边的长度相同。或者你可以回答：4。（矩形的点数）嘿嘿。 - moogs

是的，多边形可以处于任意方向，而对于矩形，应该尽可能以面积最小为原则。 - Samra

你自己有试过吗？ - chrips

相关问题 https://dev59.com/ZlsW5IYBdhLWcg3w4qiw - Hamed

5个回答

5

对于凸多边形，可以使用旋转卡壳算法，或者对于其他情况，使用凸包算法。当然，您需要凸多边形中点的坐标，而不仅仅是点的数量。

- p00ya

我认为这会对我有所帮助...更确切地说，我必须计算多边形的宽度和长度!!! - Samra

1

这不是问题：当您应用算法时，依次计算与每个边对齐的边界框的宽度和长度。 - p00ya

1

按照以下算法进行操作：

有关详细信息，请查看链接Minimum-Area-Rectangle

- Temp

1

首先执行 grahm-scan 并获取点集的凸包。然后您可以使用类似于此处讨论的最小矩形的东西

- cyber-monk

-1

显然，要得出答案，您需要点的坐标。如果矩形与X和Y轴对齐，则解决方案很简单。如果您想获得任意角度的最小可能矩形，则需要进行某种优化过程。

- Mark Bessey

感谢马克的评论。是的，我需要矩形在任意角度上。您能详细说明一下优化过程吗？ - Samra

已经有几个人提到了旋转卡尺算法。基本上就是这样做的。你需要进行基本的最小/最大边界框计算，但是坐标系要旋转到每条边的角度。 - Mark Bessey

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ZZ Coder · Accepted Answer

这被称为最小外接矩形，是OCR软件包中使用的最基本算法。您可以在OpenCV软件包中找到使用旋转卡尺实现的代码。获取源代码后，查看此文件。

cv/src/cvrotcalipers.cpp

你需要的方法是cvMinAreaRect2()。