基于橡皮筋拟比算法的二维紧凑布局设计

紧凑布局优化设计是在考虑空间约束和性能约束条件下，如何在有限空间下合理布置待布物体，这被证明是NP-hard问题。Rudolf 副在二维装填问题布局上采用线性逼近算法和遗传算法对布局算法有了进-步的研究，Andrea Lodi 针对三维箱体布局问题构造了基于禁忌搜索的启发式算法，邱英汉 用二叉树结构来表示三维实体布局问题，求得实体初始合理摆放位置的算法，戴佐等 提出了-种八叉树结构可解决在集装箱布局问题中三维矩形物体布局，Zhan-wei Liu等采用人机协作的方式将人的经验和智力以及计算机技术结合的算法解决了航天器仓拈的布局问题剐。

以上研究中，遗传算法或其他算法被用来作为布局优化的近似解，然而NP-hard问题是穷尽的搜索，精确解很难找到。

本文提出用橡皮筋的物理学方法拟比2D产品布局过程 ，利用缠绕在-系列待布物体上的橡皮筋的弹性收缩能力模拟紧凑布局过程 ，能展示-种直觉的行为，可以保证最优布局结果。

1 橡皮筋拟比模型橡皮筋拟比模型采用凸壳橡皮筋构建-个模拟真实零部件布局的类比模型来优化布局，如图1所示。假设有n个待布物体，每-个待布物体由m个凸壳点组成，则每个待布物体上的点集为MiPli，P2j，QI，Pmj，其中，il，2，，n，橡皮筋凸壳模型将由n个点集集合而成，若有q个点，则表达为HHl，H ，，Hn)P。，P2，-.，Pq)，其中H ∈M ，可能为-个点，可能为两个点，也可能为空，这些凸壳点为橡皮筋的受力点，待布物体在弹性力下产生平移旋转，滑移的过程，最终达到紧凑的结果。其凸壳与橡皮筋布局优化算法模型为：minF(X，S)i-1t∑∑ ，S )∑ ，S )0/1 ，l 扛 Igl( ，S )≤0三6 C图1 橡皮筋拟比布局模型图设计变量只是组件的位置和方向，目标表示系统性能，S 表示可变形组件的初始形状∩变形组件的形状在系统层优化中不改变，也就是S：.c是固定的≌间约束要求在两个组件0 (X，S )之间以及组件与外围之间C；(x，S )不重叠，n代表组件数量。约束 g (X，S )是功能约束 (组件的装配性能约束关系)。Lb和Ub是组件位置和方向的边界。

收稿日期：2012-11-28基金项目：国家自然科学基金资助项目 (51265002)作者简介：马俊燕 (1977-)，女，安徽桐城人，讲师，博士生，研究方向为CAD/CAM及优化设计。

第35卷 第3期 2013-03(上) [131] I 匐 似建立橡皮筋拟比算法：第-步：基于产品配置的待布物体的初始布局，构造各待布物体的二维凸壳模型，首先建立结构变量Convex-Points记录凸壳点的信息。获得每-个凸壳对象的点数据并存储在链表Convex中；Struct Conve) oints/，数据Cpoint pt；int N Points；/点所在的二维对象凸壳号BOOL In Convex；/是否为橡皮筋凸壳点//LinkStruct ConvexPoints next；)；Struct Convex Points Convex；Struct Conve) oints Convex- Rubber；第二步：由这些二维凸壳模型构造橡皮筋凸壳模型 ”，构造集合H，并存储在链表Conve)Rubber中；第三步：根据初始布局计算橡皮筋的初始长度，根据最理想的紧凑状态估算橡皮筋的最短长度，选取-个合适的橡皮筋初始长度。

第四步：计算橡皮筋的弹性力F，并计算合力FHi，得出待布物体的平移力；第五步：物体在平移力的作用下将向弹性势能减少的方向移动，同时以时间为节拍，每移动- 节拍做干涉检测，如有干涉转下-步；否则转第四步：第六步：在此时间节拍内对仿真时间进行采样，对各采样点依次判断物体是否发生干涉，直至找到碰撞的第-时刻。碰撞前为平移运动，碰撞后为旋转滑移运动，如图2所示；第七步：移动物体相对另-个物体在碰撞点做力矩计算，进行旋转运动，直至与其边平行(公差带范围外碰撞)；第八步：物体的距离都在公差带范围，没有可移动空间，运动停止。

- 图2 物体的旋转和滑移运动2 弹性力计算为获得-个合适的弹性力，橡皮筋在最长和I1321 第35卷 第3期 2013-03(上)最短时都有张力，需对布局的初始状态和最终状态做个估计来获得-个合适的橡皮筋原始长度。

橡皮筋的最长伸长状态为布局的初始状态，可以通过橡皮筋凸壳的长度获得，集合H是有顺序的序列凸壳点组成， (x y ) ，此时橡皮筋长度l可表达为式(1)。

毫 - l (1)布局最紧凑时可获得布局总面积最小，最理想状态下是所有待布二维凸壳的面积和，如式(2)，用此最小面积作为圆面积，用此圆的周长估算橡皮筋的最短长度如式 (3)，实际长度肯定比这长，可保证张力存在。

∑(∑ × (2)il 1 /2)lmi 2 ： 2～ (3)取lmin为橡皮 筋原始长 度 ，初始 弹性力Fk(1max-lmin)，每个待布物体的弹性力的合力计算如图3所示，首先从链表Convex-Rubber中存储的点信息判断该待布物体有几个凸壳点，再根据与周边凸壳点的方向矢量计算合力，如式 (4)。

图3 弹性力矢量合成图： (4)i13 碰撞检测橡皮筋拟比算法中，碰撞检测是模拟运动的效率和关键，其每步运动节拍下都要判断是否碰撞，如果碰撞，还要具体计算何时发生碰撞，以模拟碰撞前的平移运动和碰撞后的旋转滑移运动，这是动态碰撞检测问题，可以采用重复碰撞检测技术，在仿真时间内进行采样，获取碰撞点和碰撞时间。因此对模型要求比较精确，可将待布物体进行三角形网格划分，物体的碰撞转换为三角形面片的碰撞检测问题，本文研究了-种基于计算几何的方法判断三角形面片的关系。

假定二维空间两个物体为Mj和M是由N。和N个三角形面片组成，物体M 和M 及面片Ti 和 。由公式(5)和(6)表达，其中Vik(k1，2，3)和 Vj (11，2，3)务l造 匐 出面片的顶点坐标。

0 ， (5)T，k 。， ：， 3jⅣ 2Mj U，..Tjt，、 (6) ，l Ihl ， ： ， ，j物体间的碰撞检测可以转换为这些面片的碰撞，如果两个面片碰撞，将有两种情况产生，T的-点在T。内，或Tj。的-点在TikN，如图4所示，为判断点是否在三角形面片内，又可以分成四种情况，图6(a)点在三角形内，图6(b)点在三角形的左上，图6(c)点在三角形的右上，图6(d)点在三角形下，因此可以转换为点与直线的关系，可以采用计算几何的方法来解决，如图5所示，为判断点P在P-Z的左边还是右边，为可计算向量的叉乘算法如公式(7)。

VV Vikl(a) (b)图4 三角形面片的关系图Pb上，1图5 点与直线的计算几何关系× ： - ： I- I (7) - ( -XaYb)-bXa如果 顺时针旋转到占，计算结果>O；如果 逆时针旋转到云，计算结果<0。

根据这样的计算几何定理，点是否在三角形内，图6(a)中如果 a1 x

顺时针 a2顺时针逆时针 a2顺时针(b1(c) (d)图6 点与三角形面片的位置关系图4 案例橡皮筋布局模拟系统由Visual C开发，案例采用了5个二维CAD物体，橡皮筋缠绕在物体上，给定弹性系统和时间步长后，模拟过程将逐步进行，经过12步迭代，最后达到紧凑，如图1所示。

橡皮筋围绕的最初面积为1893mm ，最终优化后面积为 1056 rlrl2。

5 结论本文采用了-种新颖的橡皮筋拟比算法进行紧凑布局设计，对其运动过程的模拟采用时间为步长，并详细进行了橡皮筋长度的选娶弹性力的计算和碰撞检测过程的分析，用开发的模拟平台布局了5个二维物体，其布局后的面积明显减小，证明橡皮筋拟比方法可以实现，为紧凑布局优化模型提供了可行的物理建模算法。