周 鑫， 赖晓阳， 孟祥群， 王 堃， 唐厚君

(1. 上海交通大学 电气工程系，上海 200240； 2. 上海方菱计算机软件有限公司，上海 200241)

临界多边形这一概念由Adamowicz等[1]提出，广泛应用于CAD、图像图形学等领域.临界多边形最重要的应用为排料问题[2]的相交校验.排料问题可概括为如何在有限的空间内装下最多指定形状的物体[3].排料问题需要测试待排料位置中能否放下指定形状的物体，此时需要判断待排料工件是否与已排料的工件相交，这个过程称为相交校验.临界多边形是排料问题相交校验计算的重要工具.研究临界多边形对工业生产具有重要的学术价值和实用价值.

国内外学者对临界多边形进行了许多研究，提出了多种临界多边形的计算方法[4-5].这些算法包括蚁群算法[6]、元启发算法[7]、移动碰撞法[8]、模拟退火算法[9]、遗传算法[10]、重力临界多边形算法[11]及轨迹线算法[12-13].

以上算法有一个共同的局限：算法仅能对多边形的排样进行求解.实际工业环境中，待排样的物体并非严格的多边形.一种方法是用多边形对其轮廓进行拟合，这样在精度上势必有所损失.一种基于移动碰撞法的临界多边形算法[14]可以计算由包含圆弧和线段的临界多边形，解决了精度损失问题，但其计算速度有待提高.

本文在分析了临界多边形的多种计算方法后，研究了计算速度较快的轨迹线算法，并将其加以拓展，使其能够计算包含圆弧和线段的临界多边形，解决了精度损失问题，同时保证了计算的效率.在冲床自动送料机的排样中对算法进行了测试和实验，并将其与基于移动碰撞法的临界多边形算法和普通的相交校验算法加以比较，验证了算法的效率和精度.

1 临界多边形的定义

定义1临界多边形.给定多边形A与多边形B，固定多边形A，令多边形B作不旋转的刚体运动绕多边形A运动一周，绕行过程中，保证A与B边界上至少有一点互相靠接，且A、B不重叠.在B上任取一参考点M，在绕行过程中M的运动轨迹为一闭合的多边形，此多边形就是B相对于A的临界多边形，记作NFPAB，如图1所示.

图1 临界多边形NFPAB的定义Fig.1 Definition of No Fit Polygon NFPAB

按上述方式构造出来的临界多边形NFPAB有着明确的物理意义，当多边形B的参考点M落在NFPAB以内时，多边形A与多边形B互相重合.M落在NFPAB边界上时，A与B刚好相互靠接.当点M落在NFPAB边界以外时，A与B不重合.基于这样的物理性质，求解出临界多边形后，可以方便地判断出任意相对位置下多边形A、B是否重叠.

在求解排料问题的过程中，需要频繁地判断待排料的工件是否与边界或者已排料的物体重叠，即待排料的物体位置是否合法，此过程被称为相交校验.由临界多边形的定义可知，判断多边形A与B是否重叠的问题可以转化为判断B上的参考点M是否在NFPAB内部的问题，并且只需计算一次临界多边形，即可对任意相对位置下多边形A与多边形B的相交校验进行计算.理论和实践都证明，在排料问题中使用临界多边形能够大大节省相交校验的用时.

2 算法整体流程和思想

计算临界多边形的轨迹线算法思想可以描述如下：临界多边形是两个多边形靠接绕行过程中的轨迹，绕行过程中都是多边形A与B仅有两种状态，A的顶点与B的边靠接或者B的顶点与A的边靠接.顶点在边上靠接并滑动的过程会生成一条轨迹线.若枚举所有的顶点与边，求解相应状态下的轨迹线，则待求的临界多边形为这些轨迹线组成集合S的一个子集.由临界多边形的定义可知，S内轨迹线围成的最大多边形即为待求的临界多边形.

轨迹线算法的核心是如何快速计算轨迹线的集合S，并根据S求解对应临界多边形.本文改进了原有轨迹线算法的轨迹生成策略以及临界多边形求解算法，使其能够求解包含圆弧的物体间的临界多边形.下文将详细介绍引入圆弧后轨迹线的求取以及如何从轨迹线集合中提取对应的临界多边形.

为了方便起见，指定两物体的轮廓线方向，轮廓线首尾顺次连接，沿逆时针方向绕物体一周，并将大于180°的圆弧拆分成相连的两段等长圆弧，保证每段圆弧对应的圆心角小于180°.

2.1 轨迹线的求取

由轨迹线的定义可知，所有物体可能的靠接方式都将形成轨迹线.复杂物体形成的轨迹线的数量相当巨大，为了简化计算，需要对靠接方式进行简单的校验，排除部分不可能的靠接方式，减少轨迹线的数量.

下面给出顶点张角和轮廓线法向量的定义.

定义2顶点的张角.对顶点P，求P点两侧轮廓线在顶点P处的切向量α1、α2.其中α1对应的轮廓线在前，由向量α1、α2构成的角∠P1P2P3记作顶点P的张角，其中P1P2对应向量α1，P2P3对应向量α2.图2、3分别为P点两侧为线段、P点两侧有圆弧边时，P点张角的示意图.

图4 凸角凹角的示意图Fig.4 Diagram of convex angle and concave angle

图5 轮廓线的法向量定义Fig.5 Definition of normal vector of contour

图2 P两侧均为线段时顶点P的张角Fig.2 Expanding angle of P when both sides of P are segments

图3 P两侧有圆弧时顶点P的张角Fig.3 Expanding angle of P when either side of P is arc

定义3角的凹凸性.对组成几何图形的某一顶点P，求取P点的张角∠P1P2P3，若P1位于射线P2P3的顺时针方向，则点P2处顶角为凸角，否则点P2处顶角为凹角，如图4所示.

定义4轮廓线的法向量.以图5所示的多边形V1V2V3为例，对于线段边V1V2，将其方向向量逆时针旋转90° 即可得到其法向量n.对圆弧边V2V3，圆弧上任意一点P′均有相应的法向量，为该点切线方向向量逆时针旋转90° 的向量，这些法向量的集合为圆弧的法向量.因此，线段的法向量方向为一定值，圆弧的法向量方向为一个角度区间.

圆弧线可以分为外凸圆弧和内凹圆弧.由于轮廓线是按照逆时针方向排列的，则轮廓内部始终位于轮廓线方向左侧，根据此性质可以简单求出圆弧的凹凸性.下面给出圆弧的外凸与内凹的判定方法：若圆弧A1相对于圆心O以逆时针方向旋转，则A1为外凸圆弧，否则A1为内凹圆弧.

引入圆弧后，物体轮廓将包含线段与圆弧两种边.此时的靠接状态可以分为三种：一多边形的顶点与另一多边形的边相互靠接、一多边形的圆弧边与另一多边形的线段边相互靠接以及两多边形的圆弧边相互靠接.以图6所示的两个物体为例，分析物体相互靠接的情况.

图6 轮廓示意图Fig.6 Diagram of contour

2.1.1顶点与边的靠接 对于外接NFP而言，若顶点P2为凹角，则该点不可能与边靠接.

若顶点P2不为凹角：

情况1当边为线段时，以A的顶点P靠接B的L1边为例，将边L1的法向量n逆时针旋转90° 后得到向量β，则且仅当β位于张角∠P1P2P3内部时，顶点P与边L1可能靠接，如图7所示.

图7 顶点与线段靠接Fig.7 Vertex touch segment

图8 顶点与圆弧靠接Fig.8 Vertex touch arc

图9 线段与圆弧靠接Fig.9 Segment touch arc

2.1.2线段与圆弧边相互靠接 若边L1和圆弧A1靠接，此时L1必定与圆弧A1相切，且A1为外凸圆弧.如图9所示，求取A1上一点P′，使P′的法向量n2和L1的法向量方向n1相反.若点P′存在且A1外凸，边L1和圆弧A1可以靠接，靠接点为P′.

2.1.3圆弧与圆弧相互靠接 此时的靠接情况分为3种：外凸圆弧与外凸圆弧相互靠接、外凸圆弧与内凹圆弧相互靠接以及两段内凹圆弧相互靠接.两段内凹圆弧不可能相互靠接，不纳入讨论范围，故实际的靠接情况仅有2种.

情况1当两段圆弧都是外凸圆弧时.如图10所示，两段圆弧A1、A2均为外凸圆弧.分别求取A1与A2的法向量，并将A2的法向量逆时针旋转180°.若这两段法向量的角度存在交集，A1与A2可能相互靠接.

图10 两段外凸圆弧靠接Fig.10 Two convex arc touch

图11 外凸圆弧与内凹圆弧靠接Fig.11 Convex arc touch concave arc

以上是所有可能靠接的轨迹线情况.综上，轨迹线集合S可以用以下算法求取：

对轮廓A、B的所有顶点，计算其张角，对所有的边，计算其法向量方向(对于圆弧线求取其法向量范围).

(1) 遍历轮廓A、B的所有顶点，对每个顶点P，求其张角∠P1P2P3，并判断其凹凸性，舍弃其中的凹角.再求取A、B中所有边的法向量.

(2) 对于(1)中求取的每个张角∠P1P2P3，遍历轮廓B的所有边L，将(1)中求取的法向量逆时针旋转90°，得到向量或向量集合β.若β的方向落入∠P1P2P3内，说明轮廓B的边L和轮廓A的顶点P可能靠接，将靠接得到的轨迹线加入集合S.

(3) 对于轮廓B的所有顶点P，重复步骤(1)、(2)，计算轮廓B顶点靠接轮廓A的边形成的轨迹线集合.

(4) 轮廓A任取一条边L1，轮廓B任取一条边L2，遍历所有这样的边组合(L1，L2).对每一个组合进行如下操作：

(a) 若L1、L2均为线段，不作任何操作，计算下一个组合.

(b) 若L1、L2其中有一条边为线段，另一条边为圆弧，将线段边的法向量n1旋转180° 后得到向量n2，若n2落在圆弧的法向量范围内，说明两条边可能靠接.靠接点的法向量与n2重合.计算L1、L2相互靠接的轨迹线，加入集合S.

(c) 若L1、L2均为圆弧，判断L1、L2的凹凸性，若L1、L2均内凹，计算下一个组合.若L1、L2均外凸，将L2的法向量旋转180°.若旋转后L1与L2法向量范围有所重合，说明L1、L2可能相交，计算L1、L2相互靠接的轨迹线，加入集合S.若L1、L2一个外凸一个内凹，当外凸的圆弧半径小于内凹圆弧时，将L2的法向量旋转180°.若旋转后L1与L2法向量范围有所重合，说明L1、L2可能相互靠接，计算L1、L2相互靠接的轨迹线，加入集合S.

2.2 从轨迹线集合中求取临界多边形

由临界多边形的定义可知，当参考点P落在临界多边形上时，待校验的两物体刚好相互靠接.由轮廓线的定义可知，当参考点P落在轮廓线上时，待校验的两个物体至少有一个交点，故而轮廓线集合中所有点均在临界多边形内部或边上.故只需要寻找轮廓线集合的最小包络轮廓，此轮廓即为待求的临界多边形.

临界多边形N求取的算法步骤如下：

(1) 将轮廓线集合置于平面直角坐标系中，计算轮廓线集合S内部所有交点，以及圆弧Y值最小的点，组成点集V.

(2)取V中Y值最小的点，作为轮廓起始点PS，选取过PS且与X轴夹角最小的边作为起始边.

(3)计算与当前边可能相交的所有点，取离当前点最近的交点作为截断点，将当前点与截断点之间的边L部分加入外围轮廓N中.

(4)计算当前边在截断点处的切线向量α，并计算过截断点的其他边在截断点处的切线向量，取与α右侧夹角最小的向量所在边为下一个当前边.

(5)重复步骤(3)～(4)，直至截断点与PS重合.此时外围轮廓N即为临界多边形.

3 算法复杂度分析

假定多边形A是由m条边构成，多边形B是由n条边构成，采用轨迹线算法可以生成k条轨迹线，最终生成的临界多边形有l条边.对于某个排料问题，需要在p个不同的相对位置上对两多边形作相交校验.

对比移动碰撞法和轨迹线算法两种临界多边形算法，根据文献[12]，移动碰撞法的时间复杂度为O(lmn)，轨迹线算法的时间复杂度为O(lk)，由轨迹线的求取方式可知k≤mn，故而两算法最大时间复杂度相同.但轨迹线算法根据法向量方向事先排除了大量轨迹线，实际的轨迹线算法时间复杂度远小于O(lmn).故而轨迹线算法的效率会明显高于移动碰撞法.

对比临界多边形算法和常规相交校验算法.常规的相交校验是判断多边形B内任意一点是否落在多边形A内.若是，则两多边形重叠；若不是，则将多边形A的每一条边与多边形B的每一条边分别作相交校验.如有相交，说明A、B互相重叠，若均无相交，则两多边形不重合.采用常规相交校验算法，进行一次套料的时间复杂度为O(pmn).

若使用临界多边形进行校验，一次套料的时间复杂度为O(pl+lmn).两个校验时间相比较，可以发现使用临界多边形进行校验，会在生成临界多边形本身产生额外的开销，但在多个位置进行重叠校验时由于可以直接重复利用NFP的信息，节省重复计算的时间.当p≫mn时，使用临界多边形进行校验能够极大地节省装载问题的计算开销.

实际生产过程中，工件与板材形状往往不会过度复杂，但为了最大程度地提高利用效率，装载问题算法会计算大量的排料位置以寻求最优解.以冲床自动送料机的加工为例，一次套料中，p的数量级在104左右，而工件边数一般少于60，满足p≫mn这个条件.因此采用临界多边形算法可以极大地提高运算速度.

4 实验结果与分析

本文对冲床送料机常用零件库中的60种不同工件进行了临界多边形计算，总共测试了330种不同的组合.其运行平台为PC机，其处理器为 i7-7700HQ，2.81 GHz， 8 GB内存，Windows 10操作系统.经过测试，算法能够生成正确的临界多边形，通过临界多边形进行的相交校验计算与传统的相交校验计算结果一致，验证了算法的正确性.

图12为几组不规则工件生成的临界多边形.表1对比了基于轨迹线的临界多边形算法和基于移动碰撞的临界多边形算法的效率.

图12 几组不规则工件生成的临界多边形Fig.12 Critical polygons generated by several groups of irregular workpieces

表1 两种临界多边形算法计算效率的对比Tab.1 Comparisons of computational efficiency of two critical polygon algorithms

由表1可知，基于轨迹线的临界多边形算法在计算效率上优于基于移动碰撞的临界多边形算法，且工件形状越复杂，其计算效率提高的效果越明显.

下面以冲床自动送料机为实际场景，对算法进行测试，将基于轨迹线的临界多边形算法和常规相交校验算法效率进行对比分析.冲床自动送料机使用的工控机处理器为i7-4900MQ, 2.8 GHz, 8 GB内存.图13为一份典型的冲床自动送料机加工样例，加工的工件为灰色的五角星形工件.

图13 冲床自动送料机加工样例Fig.13 Processing example of punch automatic feeding machine

表2给出了冲床自动送料机在加工不同形状板材时，采用两种算法的效率对比，测试的板材为眼子料(即常规钢板被加工后剩余的边角料)和板料(分为窄与宽两种)，测试工件相同，均为扳手形工件(见表1序号3).

由表2可知，与原有的相交校验算法相比，使用临界多边形算法显著可以提高算法效率，测试用例中，算法效率提高了约30%～55%左右.效率提升的幅度随着排料区域的扩大而提升.由理论分析可知，临界多边形的生成相当耗时，但生成临界多边形之后进行相交判断相比常规算法更为迅速.当排料区域变大时，排料算法对相同工件的相交判断会更为频繁，使得临界多边形算法的优势得以扩大，效率提升更为明显.表2结果与理论分析相符.

表2 采用临界多边形算法前后冲床套料用时对比

5 结语

本文在基于轨迹线的临界多边形算法基础上，将算法加以改进，拓展了算法的应用范围.改进后的算法能够正确计算包含圆弧的物体所形成的临界多边形，解决了使用多边形拟合曲线带来的精度损失问题.对比现有的基于移动碰撞法的临界多边形算法，该算法显著提高了计算速度，在计算复杂物体临界多边形的情况下，该算法平均能够提升40%左右的效率.在冲床自动送料机上的测试结果验证了本文算法的可行性和有效性.