怎样求包含在多边形内的最大矩形？

Question

已知一多边形（可为凹或凸），求包含在这一多边形内的最大矩形？
誰能提供算法？谢谢！

Answer 1

我需要的是对任意给定的多边形都通用的算法啊，
而不是象平时做的几何题那样针对个别案例呀！
先像做几何题那样解出来再说吧－－－－－－－－－－－－－－－－－－
 Wyhshp(阿呆) 
 扫描线法。－－－能细说一下吗？

Answer 2

我以前做过求任意封闭区域最小外接矩形的算法。不过你这个是求最大内接矩形，难度大很多。建议你到中国期刊网上搜索相关算法。
   我求最小外接矩形是用了旋转边界点的方法，我想应该也能求出最大内接矩形，不过运算量会很大。
   我的方法是一种近似算法，精确度很高（因为屏幕上的点是离散的）。
   基本思想：每次以◎角旋转边界点，旋转后求出一个面积最大的正内包含矩形（记录下来）。直到一共转过90度，这样可得到90/◎个正内包含矩形，其中最大的就是该封闭区域的最大内包矩形。 
   正内包含矩形是指由水平和垂直线段构成的内包含矩形。
   问题的最大难点就是：要求出每次旋转后的最大的正内包含矩形。一个简单想法：每隔M点取出一点，求出N/M（N为总点数）个正内包含矩形取最大的那个。
   这样做就很近似了。
   求一个点的正内包含矩形应该不难。
   以上内容仅供参考，我只做过最小外接矩形,其简单之处在于每次旋转后正外接矩形有且只有一个。