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

收稿日期：2006-11-01基金项目：国家自然科学基金资助项目（40301037）作者简介：程鹏飞（1982-），男，河北乐亭人，硕士，主要研究方向为图形学与地图数据处理。对于多边形目标而言，用其外接矩形来近似描述其形状是地理信息系统和图形学领域的一种常用方法。多边形的外接矩形一般有两种形式，其一是最小绑定矩形（MinimumBoundingRectangle，简称MBR）[1]，即以多边形顶点中的最大、最小坐标确定的矩形；其二是最小面积外接矩形（MinimumAreaBoundingRectangle，简称MABR）。由于MBR的计算非常简单[1]，此处不再赘述。因而只专注于任意多边形的MABR的算法及其程序实现。文献[2]提出了一种计算MABR的方法。其原理是将图形在90°范围内等间隔（记间隔值为2008年工程图学学报2008第1期JOURNALOFENGINEERINGGRAPHICSNo.1一个求解多边形最小面积外接矩形的算法程鹏飞，闫浩文，韩振辉（兰州交通大学数理与软件工程学院，甘肃兰州730070）摘要：多边形最小面积外接矩形是地理信息系统和图形学领域一个极其有用的工具，但是其精确求解过程比较困难。首先证明了一个多边形的最小面积外接矩形必定过该多边形凸包的一条边，然后基于该思想提出了一个计算多边形最小面积外接矩形的算法，并对算法的效率进行了分析。最后给出了算法的实验算例，进一步说明了算法的可行性与可靠性。关键词：计算机应用；地理信息系统；多边形最小面积外接矩形；外接矩形算法中图分类号：TP391文献标识码：A文章编号：1003-0158(2008)01-0122-05AnAlgorithmforComputingtheMinimumAreaBoundingRectangleofanArbitraryPolygonCHENGPeng-fei,YANHao-wen,HANZhen-hui(SchoolofMathematics-PhysicsandSoftwareEngineering,LanzhouJiaotongUniversity,LanzhouGansu730070,China)Abstract:Theminimumareaboundingrectangle(MABR)ofanarbitrarypolygonisanimportanttoolinthegeographicinformationsystemsandcomputergraphics,buthowtopreciselycalculateitisofgreatdifficulty.Firstly,theMABRofanarbitrarypolygonsharesacommonedgewiththeconvexhullofthepolygonisproved.Secondly,analgorithmforcomputingMABRbasedonthisideaispresentedandtheefficiencyofthealgorithmisdiscussed.Finally,someexperimentsaregiventoshowthefeasibilityandreliabilityofthealgorithm.Keywords:computerapplication;geographicinformationsystems;minimumareaboundingrectangleofanarbitrarypolygon;boundingrectanglealgorithmsα，则其旋转次数为90/α）地旋转，在每次旋转之后计算并记录该位置下图形的MBR，其中面积最小的矩形就是原多边形的MABR。该方法的缺陷是一般情况下不能得到准确的MABR，因为它的结果的精确度取决于每次所选的旋转角度的大小。为了得到较精确的MABR，该方法需要将间隔值α尽可能减小；但是，很显然其旋转次数将成反比例增加，这不可避免地使得算法执行中占用了更多的系统时间。文献[3]提出了一种借助于最小二乘法求出图形的最佳拟合直线，进而来求解MABR的方法。图形的最佳拟合直线是指在能够近似代表整个物体的点位分布的直线中，偏离误差（通常用最小均方误差来度量）最小的那条直线。该算法认为MABR的主轴应该与该最佳拟合直线平行。但是通过实验发现，对于一些特殊多边形而言，该算法所求结果并不是MABR。如图1所示，当一个菱形的小夹角为60°时（设其边长为1），该算法求出的最佳拟合直线L过菱形的长对角线，与长轴方向一致的外接矩形面积为3。但是，实际上显然可以找到一个过菱形的一条边的、面积为0.753的外接矩形。可见，MABR的求解问题并未真正解决。为此，下面拟给出任意多边形MABR严格的数学求解证明，并设计其求解算法。图1菱形的MABR分析1任意多边形MABR计算的数学证明1.1两个假设假设1任意一个多边形的MABR和其凸壳的MABR是等价的；假设2凸多边形的MABR至少有一边经过该凸多边形的一边。1.2对假设1的证明凸多边形的凸壳是其本身，故凸多边形的MABR与其对应的凸壳的MABR等价是显然的。在此只需考虑凹多边形的情况。这里给出两个定义：（1）外边一条凹多边形的边如果在其对应的凸包上，则称其为外边。（2）内边一条凹多边形的边如果不在其对应的凸包上，而在凸包内部则称为内边。如图2所示，显然该情况就变成MABR不会过凹多边形的内边。由于凹多边形的任意一条内边及其延长线必将该多边形截为两个部分（图中虚线L代表多边形一条内边的延长线）。而外接矩形无法过该内边又同时包含被截的两部分。故MABR只能过多边形对应凸包的边。因此，假设1成立。1.3对假设2的证明先给出凸多边形外接矩形的定义：若矩形的每一条边与凸多边形至少有一个交点，且矩形外无多边形的点，则称此矩形为多边形的外接矩形。由以上定义，凸多边形外接矩形分为以下几种：①外接矩形与多边形有两个交点（见图3）；②外接矩形与多边形有3个交点（见图4）；③外接矩形与多边形有4个交点（见图5）；④外接矩形至少过多边形的一条边。对假设2的证明采用反证法，若假设2不成立，即最小面积外接矩形不过多边形的一条边，则外接矩形与多边形交点的情况只剩下前3种。现在只需证明前3种情况不成立。外边L图2多边形的凹边将其分为两部分内边对应的凸包60°边长为1L第1期程鹏飞等：一个求解多边形最小面积外接矩形的算法·123·（1）外接矩形与多边形有两个交点如图3所示，两个交点A、B为外接矩形的两个顶点，设AB的长度为a。设外接矩形与线段AB的小夹角为α，设β=max（∠CAB，∠ABD）。则βα≤45o，该外接矩形的面积为Area(α)=长×宽＝(a*cosα)*(a*sinα)＝a2*cosα*sinα＝0.5*a2*sin(2α)函数Area(α)在区间（β，45°）上单调递增。当α取得其极限值β时（即外接矩形过多边形的一条边），矩形仍为多边形外接矩形，此时外接矩形的面积小于任何与多边形有两个交点的矩形的面积。故多边形有两个顶点在外接矩形上的情况无法使外接矩形取得面积最小值。（2）外接矩形与多边形有3个交点如图4所示，外接矩形与多边形的3个交点为A、B、C。设线段AB和AC的长度分别为a，b。设AB与AC的夹角为γ（γ为固定值），设θ=max(∠BAD，∠CEA)。AB、AC与外接矩形边的夹角分别为α、β，这样就有γ+α+β=90o，不妨设α≤β，则α的取值范围为(θ，45o)。该外接矩形的面积为Area(α)=长×宽＝(a*cosα)*(b*cos(90°-γ-α))＝0.5ab*(sin(2α+γ)+sinγ)函数Area(α)在区间(θ，45o)上为凸函数。当α取得其极限值θ或45o时（即外接矩形过多边形的一条边），矩形仍为多边形外接矩形，此时外接矩形的面积小于任何与多边形有3个交点的矩形的面积。故多边形有3个顶点在外接矩形上的情况无法使外接矩形取得面积最小值。（3）外接矩形与多边形有4个交点如图5所示，设外接矩形与线段AC的小夹角为α，线段AC、BD的长度分别为a、b（不妨设a≥b），显然45oα≤90o。AC、BD的小夹角为γ（γ为固定值），该外接矩形的面积为Area(α)=长×宽＝(a*sinα)*(b*sin(90o-(90o-α)-(90o-γ)))=-absinα*cos(α+γ)=0.5*ab(sin(γ)-sin(2α+γ))函数Area(α)在区间(45o，90o)上为增函数。面积随α的减小而减小，当α向45o减小时，必会使矩形某条边与多边形边AH、DG、CF、BE中一条重合，此时矩形仍为多边形外接矩形，外接矩形的面积小于任何与多边形有4个交点的矩形的面积。故多边形有4个顶点在外接矩形上的情况无法使外接矩形取得面积最小值。综上通过对前3种情况的分析，可知MABR不可能在外接矩形不过多边形一边的情况下产生。所以，凸多边形的MABR至少有一边经过该凸多边形的一边。证毕2求解多边形MABR的算法设计2.1算法思路基于1.2的结论，设计求解任意多边形MABRBD图3多边形与MABR有两个交点αAC虚线表示任意多条边D虚线表示任意多条边图4多边形与MABR有3个交点ABCβαE·124·工程图学学报2008年Gα虚线表示任意多边形γADCBEHF图5多边形与MABR有4个交点的算法如下：第1步计算多边形的最小凸包。计算多边形的最小凸包的算法很多，如包括格雷厄姆算法、卷包裹法、分治算法等[5]。其中由于格雷厄姆算法的时间复杂性最低，故此处选取格雷厄姆算法。第2步选取所得凸包中一条边作为起始边并对该凸包以选中边的左端点为中心旋转使该边平行于坐标横轴，计算并保存其MBR的坐标、该边的编号及旋转角度。第3步顺序选择其他边，并按照第2步的方法计算并保存其MBR的坐标、该边的编号及其旋转角度。第4步比较所得的MBR的面积，其中面积最小者按其记录的旋转角度以该边的左端点为圆心逆向旋转即为所求的MABR。2.2算法分析对新算法的时间复杂度分析：设多边形的边数为n，在第1步求凸壳的过程中采用格雷厄姆算法，其算法复杂度为O（nlogn）[5]，其所求的凸壳的边数为m（其中m≤n）。第2步在对凸壳进行的每一次旋转都需要对m个点分别乘以一个二维矩阵[4]来完成，每次对二维矩阵的乘法时间复杂度为常数时间，而该步骤需要对凸壳m个顶点进行旋转，故该步骤需O（m）时间。第3步需要进行m-1次第2步运算，故需O（m2）时间，第4步面积比较及进行一次矩形旋转，与2、3步比可看成线性时间。故综合以上分析可知整个算法的时间复杂度为O（m2）。新算法与最佳拟合直线算法的比较：由论文中第2节可知，一个任意多边形的MABR必过与其相对应的凸包的一条边，故新算法所求得的MABR为精确解。而根据最佳拟合直线算法求出的长轴不一定与MABR的边平行，引言中关于菱形的例子也证明了这一点，故最佳拟合直线算法中认为所求长轴定与MABR的一条边平行的论断是缺乏依据的。所求解是不精确的。新算法与旋转法相比：旋转法需要进行90/α（α为间隔度，是不确定值）次旋转，每次旋转所需时间为O（m）。而由经验可知，要使旋转法所求结果达到实际需要，α的阈值通常≤0.05，因此在多边形边顶点数不超过1800个点的情况下，该算法的时间小于旋转法，而在实际应用中顶点数通常远小于1800个点，所以与旋转法相比，该算法通常占有时间优势；另外，旋转法是以α为间隔进行旋转来求最小面积外接矩形的，所以无论α取多小，所求MABR通常都会存在一定的偏差。3实验与讨论求多边形MABR的方法有多种，选择一个好的算法可以保证求MABR的效率及质量。为了验证该算法的可靠性及有用性，通过vc.net2003实现了对新算法的程序化，并在图6中给出了程序截取的部分算例及分析。图6为程序生成的在凹包、凸包、相邻以及相交情况下的MABR，以及它的MBR同时按各多边形最左侧顶点的X坐标从左至右排号。从图中可以清楚看出多边形5和多边形6的MBR的图6程序实例图