一种求解graph的最小外接矩形的算法

王秋娇 秦春桃 帅玉琳

摘要：

为解决工程应用中曲边图形的最小外接矩形的计算问题，介绍了现有的几种算法，分析了其优缺点。提出一种时间复杂度为O（n）的离散迭代算法，该算法以曲边图形轮廓上的一点为基准，旋转切线获得切线与曲边轮廓的交点，以过该交点的切线为一条边作外接矩形。每次迭代得到局部最小外接矩形，逐次迭代达到所要求的精度。使用Qt程序框架验证了该算法，分析了该算法的可行性和可靠性。结果表明，该算法可以快速高效地获得给定曲边图形的最小外接矩形。

关键词：曲边图形；最小外接矩形；离散迭代算法

中图分类号：O241；TP391文献标志码：A

文章编号：2095-5383（2019）01-0041-04

An Algorithm for Solving the Minimum Circumscribed Rectangle

of Curved Edges Graphs

WANG Qiujiao1， QIN Chuntao1， SHUAI Yulin2

（1. Basic Department， Southwest Jiaotong University Hope College， Chengdu 61

0400， China；2. School of Mathematics， Southwest Jiaotong University， Chengdu 611756， China）

Abstract：

In order to solve the problem of calculating the minimum circumscribed rectangle of curved edge graphs in engineering application， several existing algorithms were introduced， and their advantages and disadvantages were analyzed. A discrete iterative algorithm with time complexity of O（n） was proposed. The algorithm takes the point on the contour of a curved edge graphs as the benchmark and rotates the tangent line to get the intersection point between the tangent line and the curved edge. The tangent line passing through the intersection point was taken as a side of an external rectangle. A local minimum circumscribed rectangle is obtained in every iteration process and the required accuracy is achieved by successive iterations. The Qt program framework was used to verify the algorithm， and the feasibility and reliability of the algorithm were analyzed. The results show that the algorithm can quickly obtain the minimum circumscribed rectangle of the given curved edge graph.

Keywords：

curved edge graph； minimum circumscribed rectangle； discrete iterative algorithm

一個平面几何图形的最小外接矩形是指将该图形完全包括在内并且面积最小的矩形。最小外接矩形计算被广泛应用于航空航天、数字图像显示、计算机图形图像、地理信息系统及材料加工等众多工程领域[1-5]。

文献[6-7]提出了一种求解多边形的最小外接矩形的算法，其首先证明多边形最小外接矩形必然通过该多边形的一条边，然后依次遍历每条边所在外接矩形，寻找最小外接矩形。文献[8]将其成功运用于二维码的检测中。但该算法的时间复杂度为O（n2），并且不适用于平滑几何图形，存在较大的局限性。

文献[9]提出一种利用重心原理寻找图像的水平主轴与垂直主轴，在两主轴构成的锐角区域内旋转外接矩形，以5%为误差极限获取最小外接矩形。该算法在寻优过程中的旋转次数较少，但每次旋转所需的计算量较大。

文献[10]提出一种几何对象群的最小外接矩形的算法，首先获取几何对象的边界点集合的凸壳，然后采用几何计算方法直接得到矩形的4个顶点坐标，避免了大量旋转角度计算和坐标变换运算，从而降低了算法的计算量。但该算法在几何对象群转凸方面复杂度较高。

上述研究均是在多边形领域求解最小外接矩形，尚未有学者公开有关曲边图形的最小外接矩形的算法。本文首先提取曲边图形的曲线边界，提出一种离散迭代算法求解曲边图形最小外接矩形的算法；并仿真计算，验证了该算法的可靠性。

1相关基础

11算法约定

为更详细地叙述核心算法，本文给出以下约定：

1）若一段曲线的曲率线在其包围图形的内部，则其曲率为负，如图1的曲线的S段；若曲率线在其包围图形的外部，则其曲率为正；正负曲率交接点的曲率为零。

2）若闭合样条曲线的任意一段曲率均不为负，则称其为凸样条线，如圆及椭圆；否则称其为凹样条线，如梭形图轮廓线。

3）该算法主体将迭代n（n≥2）次以得到较精确的结果，每次迭代将产生多个外接矩形，其中面积最小的外接矩形为局部最小外接矩形Smin（n）。

12B样条线

样条线是指近似地表示一组离散点坐标之间函数关系的一条或一组曲线。B样条曲线是样条线的一种，曲线经过每个型值点，但不经过控制点，其具有多项式的次数可独立于控制点数目并且允许局部控制等优点。本文采用二次B样条拟合曲边图形的边界。

2算法设计

21算法流程

步骤1：得到一条闭合样条线后，检测其曲率。凸样条线边界曲线的凸壳就是其本身。对于凹样条线，做切线包围所有凹陷部分（本文称这些切线为“包裹切线”），将其转为凸壳，如图1所示。设定精确度σ及初始角θ，执行步骤2。

步骤2：得到图像的凸壳后，过凸壳上任意一点做该点的切线l11，以其中一条包裹切线的切点为起始点，如图2的点A；作凸壳的另外3条切线l12、l13及l14，使切线l13与切线l11平行、切线l12及l14与切线l11垂直；求取切线l11、l12、l13及l14的交点后即获得了过切点A的外接矩形S11，如图2中的虚线框矩形。

步骤3：以切点A为基准，将切线l11沿顺时针或逆时针旋转角度θ1作凸壳的割线，交样条线于另一点B，如图2所示，其中图2沿逆时针旋转，并且θ1=30°。以点B为基准点作凸壳的4条切线l21、l22、l23及l24，从而求取过点B的外接矩形S12，如图2中的实线框矩形。在获取割线交点时，作以下判断：若割线交于包裹切线，并且该切线不是该循环中已得到的所有外接矩形的任意一条边，则以该切线作为外接矩形的一条边。

步骤4：以切点B为基准，将切线l21旋转角度θ1交凸壳于点C，进而获取过点C的外接矩形S13，如图2中的点画线框矩形。

步骤5：重复步骤2—4，当割线的交点越过起始点，即对凸壳遍历了一周时，停止上述步骤。假设此时共有n1个外接矩形S11、S12、S13…、S1（n1），从中选择该次循环的最小的外接矩形Smin（1）。

步骤6：减小θ1为θ2，重复步骤2—5，得到第2次遍历的n2个外接矩形S21、S22、S23…、S2（n2）以及局部最小外接矩形Smin（2），若此时精度在误差范围之内，即存在

Smin（2）-Smin（1）Smin（1）<σ，

则Smin（2）即为误差为σ的闭合样线条的最小外接矩形。若不满足精度σ，则执行步骤7。

步骤7：重复步骤6，得到第i+1次遍历的局部最小外接矩形Smin（i+1），其中i≥1。若存在

Smin（i+1）-Smin（i）Smin（i）<σ，

则Smin（i）为误差为σ的闭合样线条的最小外接矩形。

22算法流程图

抽象的算法流程图如图3所示，其中图3a为总流程图，图3b为子流程“获取第i次迭代的最小外接矩形Smin（i）”的流程图。

3算法实验与分析

31实验

在Qt程序框架下实现了该算法，随机取3幅平面图形，使用该算法求解图形的最小外接矩形，效果如图4所示。

更一般地，随机绘制曲线后，迭代次数与精度及初始角的关系如表1所示。由表可知，该算法一般迭代2～5次即可达到所需精度范围内的最小外接矩形。

32算法分析

根据极限思想，当旋转角θ取极小值时，割线与对应弧线近似等价，即满足

lim θ→0 lAB=AB。

因此，当取旋转角θ取较小值时，每次循环得到的局部最小外接矩形接近于实际

最小外接矩形，之后的数次迭代则保证了上一次得到的局部最小外接矩形与实际最小外接矩形之间不会有太大的偏差。而输入参数“精度”既保证了结果的精度在工程所需范围，又保证了算法主体的迭代次数在可控范围内。以旋转角θ=5°为例，最坏情况是循环360°/5°=72次。

考虑到曲边图形的不规则性以及凹样条线的存在，循环体一般循环20次左右即完成一次迭代，故该算法执行速度较快。

本算法既适用于曲边图形，也适用于不规则多边形，即把多边形所有的边当作包裹切线来处理，即适用于除单个点和单条直线外的所有平面图形。

4结论

提出一种算法复杂度为O（n）的曲边图形的最小外接矩形算法，通过逐次迭代达到工程所需精度，该算法同时适用于所有具有包围面积的平面图形。使用Qt程序框架实现了该算法，经实验验证，该算法可快速准确地求解工程所需参数的最小外接矩形。参考文献：

[1]吴舟舟， 李树广. 基于分级边缘间距的实时车牌检测[J]. 中国图象图形学报， 2007，12（2）：315321.

[2]刘志超. 基于像素累加值比较和最小外接矩形的车牌识别研究[D]. 太原：太原理工大学， 2015.

[3]BAO Q， LI Z， TONG X， et al. The transform of the national geographic grids for China based on the axial minimum enclosing rectangle[M]// Knowledge Discovery and Data Mining. Springer Berlin Heidelberg， 2012：8591.

[4]KWAK E， HABIB A. Automatic representation and reconstruction of DBM from LiDAR data using Recursive Minimum Bounding Rectangle[J]. ISPRS Journal of Photogrammetry and Remote Sensing， 2014， 93：171191.

[5]KWAK E， ALDURGHAM M， HABIB A. Automatic 3d building model generation from LIDAR and image data using sequential minimum bounding rectangle[J]. ISPRSInternational Archives of the Photogrammetry， Remote Sensing and Spatial Information Sciences， 2012，XXXIXB3：285290.

[6]程鵬飞， 闫浩文， 韩振辉. 一个求解多边形最小面积外接矩形的算法[J]. 图学学报， 2008，29（1）：122126.

[7]YANG W. On automatic computation of minimumarea encasing rectangles of arbitrary polygons[C]// International Congress on Image & Signal Processing， 2009.

[8]张勇， 杨傲雷. 基于凸包及最小面积外接矩形的QR码定位[J]. 电子测量技术， 2017，40（4）：152156.

[9]张法全， 王国富， 曾庆宁， 等. 利用重心原理的图像目标最小外接矩形快速算法[J]. 红外与激光工程， 2013，42（5）：13821387.

[10]郭庆胜， 冯代鹏， 刘远刚， 等. 一种解算空间几何对象的最小外接矩形算法[J]. 武汉大学学报（信息科学版）， 2014，39（2）：177180.