[求助]如何求多边形最小外接矩形
<p>已知凸多边形的各个顶点，如何求得该多边形的最小外接矩形？</p><p>不是最上，最下，最左，最右的点所组成的矩形</p><p></p> 最小是指什么最小？面积、周长还是其它？ 本帖最后由 作者 于 2009-1-7 22:26:14 编辑 <br /><br /> <p>呵呵 面积 </p><p>现在我的办法是让多边形绕着某一点旋转0~180度，分别求出在任意一角度时上、下、左、右点所组成的最小面积矩形</p><p>然后求这组数据的最小值，当旋转角度很小时，精度可以很高，但同时运算速度也减慢，不知道有没有好的方法？</p> <p>:)</p><p>这是一个有趣的计算几何问题。</p><p>我的思路倒是比较简单，就是如此处</p><p><a href="http://cgm.cs.mcgill.ca/~orm/mper.html">http://cgm.cs.mcgill.ca/~orm/mper.html</a></p><p>它的中文翻译在此</p><p><a href="http://blog.csdn.net/ACMaker/archive/2008/10/30/3188177.aspx">http://blog.csdn.net/ACMaker/archive/2008/10/30/3188177.aspx</a></p><p>其大概意思就是，最小外接矩形 必通过凸多边形的一边。</p><p>具体证明可以看</p><h2 class="Article">一个求解多边形最小面积外接矩形的算法</h2><p><a href="http://scholar.ilib.cn/A-ISSN~1003-0158(2008)01-0122-05.html">http://scholar.ilib.cn/A-ISSN~1003-0158(2008)01-0122-05.html</a></p><p>此篇文章我有，放在了这里</p><p><a href="http://ifile.it/3eha0wn">http://ifile.it/3eha0wn</a></p><p>（下载的时候，点击一下 Request Download Ticket ，接着就可以按 <a id="req_btn" href="http://dl1.s23.ifile.it/apfwkc38/an_algorithm_for_computing_the_minimum_area_bounding_rectangle_of_an_arbitrary_polygon" target="_blank" name="req_btn">Download</a> 键进行下载了）</p><p>一些相关的文章有</p><p>求多边形最小包容矩形的遗传算法<br/>The Genetic Algorithm for Finding Minimum Containment Rectangle of Polygon<br/><<南昌航空工业学院学报(自然科学版)>>2003年 第17卷 第03期<br/>作者: 王洪发, 周铭, <br/>简单多边形的最小外接矩形算法<br/>An Algorithm for Minimal Circumscribed Rectangle of a Simple Polygon<br/><<哈尔滨理工大学学报>>2008年 第13卷 第02期<br/>作者: 刘玉珍, 刘润涛,<br/>针对钢板在数控切割过程中存在热变形,导致加工工件变形不可用的问题,采用对工件进行矩形切割,从而使热变形达到最小的方法,给出了一种求解简单多边形的最小外接矩形算法.并在此基础上分析了其具有的复杂度O(κ2)(其中κ是简单多边形的顶点个数).<br/>但这两篇反而不是很好。</p> <p>最小外接矩形 必通过凸多边形的一边。</p><p>这个定理真不错，用程序运行了一下，效果很好。</p><p>谢谢qjchen ,提供了这么好的资料。</p><p></p>
页:
[1]