一种计算带有圆弧曲边多边形最小封装矩形的方法

王楚奇(香港城市大学，香港　999077)Method for Calculating Minimum Enclosing Rectangle of Polygons with Arc EdgeWANG Chuqi

一种计算带有圆弧曲边多边形最小封装矩形的方法

王楚奇(香港城市大学，香港999077)Method for Calculating Minimum Enclosing Rectangle of Polygons with Arc EdgeWANG Chuqi

摘要在大型铁路或公路钢桁架桥梁中，其杆件和节点主要由不同形状和尺寸的平面钢板采用焊接或高强螺栓等方式拼接而成。在完成桥梁的BIM三维模型后，工程师需要计算钢板的最小外包尺寸以形成BOM表。常用的三维建模软件如Solidworks本身不具备这样的功能，需要进行二次开发。针对该需求，提出一种用于计算带有曲边(曲边为圆弧)的多边形(下略称曲边多边形)的最小封装矩形的方法。由于输入数据具有规则性，该方法将输入的曲边以一定规则离散化，化为离散点集后以快包法(Akl-Toussaint启发式)或格雷厄姆法与旋转卡壳算法求得最小封装矩形的4个顶点坐标，随后求得矩形的长和宽。

关键词钢板零件二次开发弧边多边形离散化最小封装矩形

1概述

在工程零件的设计中，经常会遇到需要计算目标零件的最小封装矩形的问题。对散点集合以及直边凸、凹多边形的最小封装矩形的计算，已经有了成熟的算法[1]，其基本思想在于先求出图形的最小凸壳，再根据该凸包求得最小面积的封装矩形。然而，这些算法都没有应对带有曲边，尤其是外凸曲边的多边形方法[2]。若是不对图形进行处理，直接使用旋转法进行计算，则会陷入每次旋转角度过大而不够精确，或是每次旋转角度过小从而导致计算时间大增的矛盾中[3]。再者，由于零件的正、反两面形状可能会有一定的区别，需要先对两面的图形进行并集计算再求最小封装矩形，这些算法同样无法应对这些情况。

通常情况下，零件的曲边可视为圆弧，且其端点位置及拱高是比较容易获得与控制的数据。针对以上问题，提出将曲边以一定规则离散化后求并，再以传统方法求得最小封装矩形的方法。

2方法的提出与改进

2.1　曲边的预处理

要将圆弧曲边离散化，首先要对曲边进行预处理，包括判断圆弧的凹凸性，求圆弧半径以及圆心坐标。圆弧曲边多边形的每一条边都包括3组数据：两端点的直角坐标以及拱高，而拱高即是判断圆弧凹凸性的依据。输入的值为正，表示圆弧向多边形外部凸出，为负表示向多边形内部凹陷，为零则表示该边为直线段。由于多边形在离散为点集后还要进行凸壳计算，故可将向内凹陷的曲边作为直线段来处理。假设两端点的坐标分别为A(xa，ya)与B(xb，yb)拱高为h，半径为r，弦长为l，有

(1)

以及

(2)

由式(2)易得

(3)

因为由式(1)很难求得圆心坐标，即使解出方程组也会产生大量的除法和根式运算，所以改用向量法。由A、B点坐标可以求出线段AB的法向量

(4)

单位化后得到单位法向量

(5)

由弦心距

(6)

及弦的中点坐标

拥有自信，能让自身的智慧的灵光得以闪亮，创造出许多自己也意想不到的奇迹。小仲马在自己艰难的创作中并没有困为一时的挫折而放弃，而是凭借着自己的信心和才能去闯出了一番天地。巴鲁玛面临唾手可得的成功放弃了，选择了一条与大相径庭的充满挑战的道路勇敢的走下去，是心烛点亮了她的锦绣人生；也是心烛使她骄傲地面对人生。

(7)

可得圆心P的两个可能坐标，满足条件

(8)

2.2　圆心位置的判断

无论是解方程组还是用以上方法计算，得出的圆心坐标都有两组，分别位于弦的两侧，且其中只有一个是这一段弧线的圆心，需要判断坐标的真伪。先将输入边的数据进行一次梳理，使得点的输入顺序与边的输入顺序保持一致(比如，两条边AB和BC，在输入过程中可能会出现输入BA和CB的情况，这里即是将其梳理为AB和BC)。之后需要判断以输入顺序构建多边形的方向(顺时针或逆时针)与该段弧线圆心P-点A-点B的旋转方向以及h与r的大小关系。由于向量AB与向量vun满足逆时针关系，即2D平面上AB×vun>0，当h

而当h>r时，若多边形方向与PAB同向则说明圆心P位置错误，若反向，则圆心位置正确(如图2)。

2.3　圆弧曲边的离散化

计算圆弧上的离散点需要圆弧的圆心角，根据上文易知，可根据h与r的大小关系来判断弧线是优弧还是劣弧，然后由余弦定理求得圆心角。利用起点角度和终点角度计算圆弧曲边的离散点坐标会产生大量的除法和反三角函数运算，从而导致计算效率低。所以本文使用旋转法依次计算出每个离散点的位置。假设计算得出的圆心角为θ，具体计算如下：

(9)

计算得出第一个离散点D1(此处假设多边形方向为逆时针，若为顺时针则将α替换为-α)

(10)

(11)

对正整数i取值2到n，有

(12)

旋转终点Dn即是点B。

2.4　误差控制

由双精度浮点数表达的直线边多边形的最小封装矩形的计算，误差通常可以保持在10-16个最大单位以下。对于曲边多边形，由于要将曲边离散为折线边，会产生一定的误差，需要将该误差控制在加工精度范围内。

如：若每次旋转角度为α，该角度对应圆弧段的拱高为h，则有

(13)

且

(14)

解得

(15)

拱高h即是产生较大误差的原因所在。为限制误差的大小，只能增大离散点的密集程度，通过限制α来达到限制误差的目的，有

(16)

2.5　封装矩形计算

由上文的方法可以得到某曲边多边形的离散点集，而每个零件都存在有些微区别的正反两面，故本文方法的最后一步就是将两面求得的点集求并，然后以快包法(Akl-Toussaint启发式)求得点集的最小凸壳，再用旋转卡壳法求得凸壳的最小封装矩形，由此获得完整零件的最小封装矩形。

3实验结果及结论

在VS 2013，CGAL4.6.1，Boost 1.58.0环境下实现本文提出的最小封装矩形的计算方法。为了验证该方法的有效性和高效性，用sketchpad 5.0软件进行精密绘图测试。运行环境为Intel® CoreTMi7-3630QM 2.40 GHz处理器，8GB内存，64位Windows8.1操作系统

3.1　有效性

如图3(极限情况)，将边的端点以及拱高精确控制并输入后，画出对应图形。将数据输入程序进行计算，将封装矩形4个顶点坐标的计算结果输入画板(左上角)。确定圆弧圆心后，从圆心向可能相切的矩形边做垂线与圆弧交于点Ei，随后测量该点到对应矩形边的距离(右下角)。此距离应小于输入数据中的最大误差限制(图3(a)的误差限制为0.000 01 cm，图3(b)的误差限制为0.001 cm，定义坐标系的单位长度是1 cm)，由此可见本文算法正确有效。

3.2　算法效率

根据软件使用者的体验，在一般情况下，对于零件的数学计算处理要求是200个左右的零件需要在5 s内处理完成，即1 000个零件的处理时间需要控制在25 s以内。表1给出了各个精度要求下的如图3和图4所示的1 000个零件的计算时间总和。从表1可以看出，本文的计算方法时间性能完全符合要求。

4结论

提出一种计算零件的最小封装矩形的方法，充分利用已有算法的特性，将带有曲边的多边形离散为散点集后进行计算。该方法能对任意零件的正反两面进行并集计算，从而获取零件最小封装矩形的规格，并且具有令人满意的精确度和效率。

参考文献

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

[2]薛迎春，须文波，孙俊.基于遗传模拟退火混合算法的矩形包络求解[J].计算机工程与设计，2007，28(22):5457-5460.

[3]卢蓉，范勇，陈念年，等.一种提取目标图像最小外接矩形的快速算法[J].计算机工程，2010，36(21):178-180.

中图分类号：U442； TB21

文献标识码：A

文章编号：1672-7479(2015)06-0082-03

作者简介：王楚奇(1993—)，男，香港城市大学科学及工程学院电子工程系信息工程专业。

收稿日期：2015-11-12