[求助]如何求多边形最小外接矩形

zongsheng131

已知凸多边形的各个顶点，如何求得该多边形的最小外接矩形？

不是最上，最下，最左，最右的点所组成的矩形

hejoseph

最小是指什么最小？面积、周长还是其它？

zongsheng131

呵呵 面积

现在我的办法是让多边形绕着某一点旋转0~180度，分别求出在任意一角度时上、下、左、右点所组成的最小面积矩形

然后求这组数据的最小值，当旋转角度很小时，精度可以很高，但同时运算速度也减慢，不知道有没有好的方法？

qjchen

:)

这是一个有趣的计算几何问题。

我的思路倒是比较简单，就是如此处

http://cgm.cs.mcgill.ca/~orm/mper.html

它的中文翻译在此

http://blog.csdn.net/ACMaker/archive/2008/10/30/3188177.aspx

其大概意思就是，最小外接矩形 必通过凸多边形的一边。

具体证明可以看

一个求解多边形最小面积外接矩形的算法

http://scholar.ilib.cn/A-ISSN~1003-0158(2008)01-0122-05.html

此篇文章我有，放在了这里

http://ifile.it/3eha0wn

（下载的时候，点击一下 Request Download Ticket ，接着就可以按 Download 键进行下载了）

一些相关的文章有

求多边形最小包容矩形的遗传算法
The Genetic Algorithm for Finding Minimum Containment Rectangle of Polygon
<<南昌航空工业学院学报(自然科学版)>>2003年 第17卷 第03期
作者: 王洪发, 周铭,
简单多边形的最小外接矩形算法
An Algorithm for Minimal Circumscribed Rectangle of a Simple Polygon
<<哈尔滨理工大学学报>>2008年 第13卷 第02期
作者: 刘玉珍, 刘润涛,
针对钢板在数控切割过程中存在热变形,导致加工工件变形不可用的问题,采用对工件进行矩形切割,从而使热变形达到最小的方法,给出了一种求解简单多边形的最小外接矩形算法.并在此基础上分析了其具有的复杂度O(κ2)(其中κ是简单多边形的顶点个数).
但这两篇反而不是很好。

zongsheng131

最小外接矩形 必通过凸多边形的一边。

这个定理真不错，用程序运行了一下，效果很好。

谢谢qjchen ,提供了这么好的资料。