硕士论文-多边形零件排样技术研究及软件开发.pdfVIP

南京航空航天大学 硕士学位论文 多边形零件排样技术研究及软件开发 姓名：徐健华 申请学位级别：硕士 专业：航空宇航制造工程 指导教师：安鲁陵 20080101 南京航空航天大学硕士学位论文 i 摘要 排样在汽车、机械、服装及皮革等领域有着广泛的应用。传统的排样方法和 结果主要依赖于操作人员的经验与熟练程度。随着计算机技术的发展，计算机自 动排样系统在各个领域得到应用，大大减轻了脑力和体力劳动强度，缩短了排样 时间，材料利用率也大为提高。多边形零件的排样是排样问题中的一个难点，本 文对多边形零件排样问题进行了深入研究，所做工作总结如下： 通过求取最小包络矩形的方式， 将多边形排样问题转化为已有成熟解决方案 的矩形件排样问题。经过对多种矩形件排样算法的对比，研究实现了最低轮廓线 最佳匹配算法。 用该方法对多边形零件进行排样， 计算复杂度低， 运算速度较快， 适用于与矩形件形状接近的多边形零件。 研究了基于碰撞算法的多边形排样方法。通过对零件碰撞距离、边界合成等 研究，将碰撞算法有效运用于多边形排样和单一零件排样中，能够得到排放紧凑 的排样结果。 研究了基于临界多边形法的排样问题。在前人研究的基础上，采用倾斜图法 获取两个多边形的 nfp（no-fit-polygon，临界多边形） 。该算法可以有效利用零 件与零件之间的排样间隙，从而提高排样的材料利用率。 研究了蚁群算法，将蚁群算法引入排样算法中，以矩形件排样算法为例，给 出蚁群算法的实现方法和步骤。通过大量的实验，进行比较。结果表明，蚁群算 法是解决矩形件排样问题的有效方法，相同条件下效率优于模拟退火算法，排放 效果好于遗传算法。 在上述研究成果的基础上，开发了排样软件。该软件主要有图形输入、图形 组合、优化排样、图形输出、人机交互处理等模块。软件提供单一零件排样，矩 形件排样，多边形排样等不同排样方式的选择，以满足实际应用中的不同需求。 数据读取与保存采用dxf格式， 使得本软件能够与其他cad软件进行数据交换。 关键词：矩形件排样，多边形排样，包络矩形，碰撞法，临界多边形，蚁群算 法 多边形零件排样技术研究及软件开发 ii abstract irregular-shaped nesting problem is common in the field of machinery, clothing, leather and so on. in the tradition handicraft, this work is based on workers experience and skill. with the development of computer science, the automation system of packing by computer is appeared in many filed. the system can reduce the time of work and improve the use of material. researches had been done in this thesis: firstly, solve irregular-shaped nesting problem by the way of rectangle-shaped nesting after get the rectangle of irregular. the rectangular packing algorithm - lowest outline best fit algorithm has been used in this thesis, for its merit - high efficiency and time-saving, after compared with other algorithm. the method for the irregular-shaped nesting is suit to the polygon which is similar with the rectangle. there will be larger space between polygons in the result when the polygon is complex. so the utilization of the material will be reduced. secondly, after the research on the collision-distance and the composition of the polygon contour, the polygon packing and the single packing based on collision has been used in the system. the parts can be packed compactly. thirdly, research the irregular packing problem based on nfp. in this thesis, the nfp is been finded based on slope diagram. this algorithm can improve the utilization ratio by using the row apperance gap between the part and the part effectively. in this thesisan algorithm of ac was proposed. the author translated it into rectangle packing problem. to verify the meta-heuristics algorithms effect, many experiments were done with ga+losa algorithm. and the results was compared and analyszed among the three hybrid algorithm. it shows that ac is fast than sa and better for layout than ga. a packing system was developed based on the research. this packing system includes graphics inputting module, graphics combination module, packing optimization module, result saving module and post-disposal module. the packing result could also be modified manually. single packing, rectangle packing, polygon packing all can be done in this system. the datas reading and saving based on dxf, so the system can be used to exchange the data with other cad software . key words: rectangle packing, polygon packing, enclosure rectangle, colliding, no fit polygon, ant algorithm. 多边形零件排样技术研究及软件开发 vi 图清单 图 1. 1 基于 autocad 的排样系统5 图 1. 2 topdesk 开发独立的排样系统 pymng.6 图 1. 3 铺层成型流程图.7 图 2. 1 凹多边形与其凸包的最小包络矩形.11 图 2. 2 最小包络矩形的求解.12 图 2. 3 最小包络矩形求解流程.14 图 2. 4 最小包络矩形求解实例.14 图 2. 5 最低轮廓线最佳匹配算法排样示意图.15 图 2. 6 最低轮廓线最佳匹配排放算法流程图.16 图 2. 7 矩形件排样实例.17 图 2. 8 多边形的水平包络矩形.18 图 2. 9 基于矩形的多边形排样流程.18 图 2. 10 基于矩形的多边形排样实例.19 图 3. 1 多边形碰撞方式.21 图 3. 2 一般多边形的单调链.21 图 3. 3 多边形 a 和 b 碰撞22 图 3. 4 碰撞的三种情况.23 图 3. 5 普通单排.24 图 3. 6 多边形水平移动距离.25 图 3. 7 普通单排流程图.26 图 3. 8 单排实例.27 图 3. 9 多边形排放及其合成边界.29 图 3. 10 多边形最小距离示意图.30 图 3. 11 基于碰撞的多边形排样流程.33 图 3. 12 基于碰撞法的多边形排样实例.34 图 3. 13 基于碰撞法的多边形排样缺陷.35 图 4. 1 nfp 的形成机理37 图 4. 2 多边形的参考点.37 图 4. 3 临界多边形的几何意义.38 图 4. 4 两个凸多边形的临界多边形.40 南京航空航天大学硕士学位论文 vii 图 4. 5 凹多边形的矢量斜率顺序与多边形边的顺序不同 40 图 4. 6 一个等边三角形和其对应的斜率图 41 图 4. 7 通过合成斜率图来求解 ab nfp 41 图 4. 8 多边形 a，b 的斜率图及临界多边形的求解. 42 图 4. 9 bennell 算法得到 nfp 的缺陷. 44 图 4. 10 算法流程 45 图 4. 11 线段共线且反向情况. 45 图 4. 12 两条线段相交 46 图 4. 13 线段相交特殊情况及交点处理 46 图 4. 14 求解两个凹多边形的 nfp 图. 46 图 4. 15 凹陷部位有重叠的斜率图的合成 47 图 4. 16 临界多边形求解过程中凸化影响的消除 48 图 4. 17 两个凹多边行的临界界多边形的求解思路 49 图 4. 18 两个凹多边行的临界界多边形求解实例 50 图 4. 19 复杂多边形的优化在临界多边形求解中的应用 51 图 4. 20 由导入边得到导出边的思路 53 图 4. 21 由导入边得到导出边的特殊情况处理 53 图 4. 22 点与多边形位置关系一般情况 54 图 4. 23 点与多边形位置关系特殊情况 54 图 4. 24 基于合成多边形的 nfp 排样策略示意图. 58 图 4. 25 基于完全 nfp 排样策略示意图. 59 图 5. 1 25 个矩形的最优排放图（h=15）. 66 图 5. 2 用蚁群算法得到的最优图（h=16）. 67 图 5. 3 25 个矩形的最优排放图（h=45）. 67 图 5. 4 用蚁群算法得到的最优图（h=48）. 67 图 5. 5 算例 1 的试验结果 68 图 5. 6 算例 1 的试验结果 68 图 5. 7 各种算法最优解与已知最优解的百分比 72 图 5. 8 各种算法的运行时间对比 72 图 6. 1 系统使用流程 74 图 6. 2 计算机排样系统总体设计 75 图 6. 3 dwgviewx 控件初始设置界面. 77 图 6. 4 基于 dwgviewx 控件的 dxf 格式图形文件显示效果 77 多边形零件排样技术研究及软件开发 viii 图 6. 5 不同多边形组合策略.78 图 6. 6 多边形的最小包络矩形.78 图 6. 7 常用的相同零件排样方式.79 图 6. 8 外形与矩形比较接近的多边形.80 图 6. 9 形状与矩形相差比较大的多边形零件.80 图 6. 10 单一零件排样菜单.82 图 6. 11 单排参数设置界面.82 图 6. 12 单排结果图.83 图 6. 13 矩形件排样参数设置界面.84 图 6. 14 矩形件排样结果图.84 图 6. 15 基于最小包络矩形的多边形排样参数设置界面.85 图 6. 16 基于最小包络矩形的多边形排样结果图.85 图 6. 17 基于碰撞法的多边形排样参数设置界面.86 图 6. 18 基于碰撞法的多边形排样结果图.86 图 6. 19 座舱罩顶棚 20 个样片的排样效果图.87 图 6. 20 系统对大量零件进行排样的效果.87 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立 进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容 外，本学位论文的研究成果不包含任何他人享有著作权的内容。对本 论文所涉及的研究工作做出贡献的其他个人和集体， 均已在文中以明 确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件， 允 许论文被查阅和借阅,可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或其他复制手段保存论文。 (保密的学位论文在解密后适用本承诺书) 作者签名： 日 期： 南京航空航天大学硕士学位论文 1 第一章 绪论 1.1 排样概述 在工程界，所谓排样，一般是指表示零件的二维轮廓的多个相同或者不同的 几何图形在原材料平面区域上的合理布置， 使得几何图形之间不出现重叠并且材 料利用率最高。 排样问题是下料、布局问题的一种，因此可以按照零件的维数划分为：一维 排样，二维排样，三维排样。 一维排样问题，又称为线材排样问题，是指在排样时只需要考虑一个方向的 尺寸。例如，将较长的型材、管材等，分割成各种较短的毛坯。典型的应用领域 包括门窗、金属制品、机械设备、专用设备、交通运输设备、电气机械等制造行 业，这些行业所属企业在制造过程中，需要将线材切割成较短的毛坯，用于生产 产品。 二维排样问题，通常又称为板材排样问题，是指将板材分割成各种形状的毛 坯。其在工业中出现的比较普遍，比如冲裁件排样13、玻璃切割、报刊排版、 家具下料、服装裁剪46、皮革下料7 、910、造船、车辆、航空航天等工程应 用领域中都存在着大量的下料问题。 对于二维排样优化问题可以分为以下三个独立问题来考察： 1）将零件放入板材中，每块板材中零件的面积之和不大于板材的面积； 2）零件为矩形，板材为矩形，要求将零件互不重叠地放入板材，使所用板 材量最小； 3）零件具有任意复杂的平面形状，板材为矩形，要求将零件互不重叠地放 入板材，使材料利用率最高，并满足一定的工艺要求。 三维排样问题，也称三维布局问题，按是否完全装入分为三维装箱或三维背 包问题。三维布局的目标是使材料利用率和重量利用率最高。实际排放时还应考 虑：1）箱体本身的承重性；2）箱体搬运的难易性；3）最大载重量；4）稳定性； 5）某些货物之间的隔离。找到满足这些条件的最优解或近似最优解是一项极具 挑战性的工作。 多边形零件排样技术研究及软件开发 2 1.2 二维零件排样的研究现状 1.2.1 国外研究现状 国外有关排样问题的研究起步比较早，paull、eisemann、hermann 和 vajda 率先提出用线性规划（linear programming）方法解决矩形件排样问题，但材料 利用率不高。garey 和 johnson 证明数学规划（mathematical programming techniques）的方法解决二维切割问题。60 年代，gilmore 和 gomory 提出了二维 排样问题。70 年代至今，许多学者对排样问题进行了大量的研究，并且取得了 一定的成果。但排样问题属于 np（non-deterministic polynomial）完全问题12， 再加上实际的限制条件，问题会更加复杂，同时排样问题具有多样性的特点，至 今没有通用的标准方法来进行求解。 正是由于排样问题应用的广泛性与其求解难 度，吸引了众多学者进行研究。90 年以来，被 el 和 sci 收录的重要论文约 200 篇，国内发表的各类论文近千篇。1988 年的 euro ix/tims 国际会议上，专门 成立了下料问题兴趣小组 sicup (special interest group on cutting and packing problem)13。 最简单，最基本的排样问题可以概括为：在宽度为 w、长度为 l 的矩形板 料上，切出宽度为wi、长为 i l 的矩形块料1420 。 更普遍、更复杂的二维混合排样问题是指，在一块指定的宽度为 w、长度为 l 的矩形板料上排列数量相等或不等的不规则平面形状零件，这些零件互不干涉 且处于板料的边界之内，寻求一种方案使得余留的废料最少，从而达到最大的材 料利用率。 最复杂的二维零件排样问题是在不规则的封闭区域内排列不规则平面形状 的零件，主要应用在皮革制造业中。 矩形件排样目前已经比较成熟， 矩形件排样既可以解决玻璃切割等矩形件下 料问题，也可以通过提取包络矩形用于多边形排样，因此很多学者针对矩形件排 样进行了研究，提出多种切实可行的排放算法和优化算法。 对于二维不规则零件可能是多边形也可能是任意形状的， 材料可能是矩形也 可能是带有孔洞等无效区域的不规则形状。由于零件和材料均为任意形状，增加 了问题的难度。该问题的研究方法大致分为两类： 第一类是包络矩形法，求取不规则零件的包络矩形，如果零件的摆放方向不 加限制，则可以求取它的最小包络矩形，然后通过矩形件排样的方式取得不规则 零件的排样效果。 包络矩形法2124可以大为简化计算，从而大幅度提高排样速度，但是排样 南京航空航天大学硕士学位论文 3 的材料利用率并不是很高。 所以第二类研究是， 如何对不规则零件直接进行排放。 其中对多边形零件的研究是热点， 对于有曲线的零件可以通过将曲线离散成线段 的方式转化为多边形零件排样来处理。 多边形零件的直接排放方法最主要的有两种：自动碰撞法2527和临界多边 形法2833。 基于自动碰撞技术的排样算法是模拟人工往盒子里装东西， 然后再晃动使盒 子里的东西排放紧密的过程。 临界多边形的基本思想是由 art 提出的。临界多边形是数学中的重要概念， 其意义是与多边形接触但是没有重叠的邻接多边形。 排样问题的关键算法是寻找 多边形之间排列最紧密的 nfp 位置，所以对于排样问题，nfp 的概念非常重要。 第二类方式可以大幅度的提高材料的利用率，但由于计算复杂度的提高，排 样所需时间也大为增加。 排样零件的排放顺序直接影响排样的材料利用率， 所以排样零件排放顺序的 确定也是一个研究的重点。 排放顺序可以是随机产生的， 也可是按面积大小排序， 将零件按长度方向从大到小排序，或采用禁忌搜索34、神经网络方法3536、模 拟退火算法37等智能优化算法搜索解空间。也有学者采用先产生一个初始排样 (可行、但非最优，或者非可行排样)，然后再加以改进的方法。改进方法可以是 继续以产生初始排样时的方法进行改善，也可以用更好的搜索技术。如 ismail38 和 jain 分别运用了遗传算法和模拟退火法来处理排样。 han 还把人工神经网络运 用到了二维不规则零件的排样，先使用人工神经网络方法产生一个初始摆放，然 后应用模拟退火进行调整、 优化。 将多种算法综合使用也是目前研究的一个方向， 并且在某些领域取得了一定的成果。 1.2.2 国内研究现状 国内排样技术的研究始于上世纪 90 年代初，主要集中在高校，如四川大学、 华中科技大学、大连理工大学、上海交通大学、浙江大学等。应用领域主要为模 具、服装、玩具等行业。 对于矩形件排样的研究始于上世纪 90 年代，如华中科技大学的曹炬14博士 采用拟合算法，背包算法等研究了不同工艺条件下的矩形件下料方案，在他的研 究中，所给的板材尺寸固定。后来他的学生继续这方面的研究，提出了丁字尺法 等排放算法。2000 年以后，逐渐采用启发式算法进行排样顺序的优化。如四川 大学的贾志欣15 、39博士分别应用模拟退火算法和遗传算法对矩形件排样进行研 究，并提出了最低水平线排放算法。刘德全博士对 bl 算法进行改进，并与遗传 算法相结合，得到较好的矩形件排放效果。 多边形零件排样技术研究及软件开发 4 对于二维零件排样的研究，主要集中在对冲裁件的排样上。通常是通过人机 交互法、边界加密法，多边形定点算法等确定图形的排放位置。90 年代中后期 逐渐开始研究多种二维零件的排样，开始以矩形包络法为主，直到徐彦欣4041 采用基于产生式规则和图形靠接算法直接进行二维零件的排样。 后来逐渐采用移 动靠接算法，碰撞算法，临界多边形算法来求解。在陈勇42和张丽萍9研究中， 零件和原材料均是不规则的，属二维零件中较为复杂的一类问题。陈勇等采用一 系列平行线对零件和板材进行扫描， 这样排样件和板材均可以看作是由一系列水 平线段区间组成，用“脏区”表示板材的无效区域，最后采用 bl 策略对零件进 行排放，取得了较好的效果。而张则利用离散网格表示零件和毛坯，同时引进边 界约束，使排样过程与皮料和样片的几何信息无关，使用基于顺序的启发式底左 布局将样片顺次排放。但这种方法的计算时间较长，50 个左右的零件用时近 1 小时。近两年有关临界多边形的研究逐渐增多，并由此引发了基于临界多边形的 排样算法的研究。 总体来看，国内最初主要以矩形件的研究为主，90 年代后期才逐渐有人对 不规则零件进行研究，并且大多是以矩形件排样为基础进行的研究，直接进行二 维零件的排样研究是近几年才开始的，但研究内容和方法还远远达不到国际水 平，且主要是实验性研究，还不能达到商用的程度。 虽然人们对排样问题进行了大量的研究，限于 np 完全复杂性，从理论上依 然没有彻底解决的方法，它依然是研究的热点问题之一。 1.2.3 排样软件概述 由于排样问题应用领域广泛， 众多学者在对排样算法研究的同时也开发了一 些排样软件，从早期的交互排样到自动排样，排样系统也在随着排样算法研究的 深入而发展，但还没有真正意义上的商品化软件投入使用。 华中理工大学最早开发了冲裁件排样系统；曹炬推出了一维优化、矩形件排 样、异形件排样的优化排样系统软件；重庆大学的刘飞等人也开发了型材、矩形 件排样系统应用于建材行业；崔耀东43开发了矩形和圆形件排样系统。目前，一 些商品化 cad/cam 软件系统，如 solidworks 、solidedge、inventoe 等，三维 钣金件设计后，虽然提供展开功能，避免了大量的人工展开计算，但仍没有排样 功能。所以目前很多的排样软件，是在现有的 cad/cam 进行二次开发：比如基 于 catia、autocad、proe、ug 等的排样软件开发。泰兆钣金展开与智能排样， 如图 1.1，就是一款基于 autocad 开发出来的一套钣金类排样软件。当然也有采 取通用数据存取方式，比如 dxf，开发独立的排样系统。对于得到的排样结果， 采用通用数据存储方式保存， 再在其他 cad/cam 系统中使用， 比如上海云腾自 南京航空航天大学硕士学位论文 5 动化科技有限公司（topdesk）开发的排样管理系统 pymng，如图 1.2 所示。 目前的排样软件，主要都是针对某一个领域开发的软件系统，对某一行业或 者某一企业的某项产品具有较高的使用价值。 市场上目前还未出现能够满足各个 行业需求的通用性的计算机排样软件系统。 开发通用性的计算机排样软件是一个 难点也是一个未来的发展方向。 图 1. 1 基于 autocad 的排样系统 1.2.4 排样系统的研究趋势 21 世纪以后的制造业将面临着 mass-customization 的生产方式，要求企业以 批量生产的时间和成本去生产出具有个性化（客户化）的产品，排样系统必须适 应工厂应用环境及应用场合的灵活多变性，将排样问题与设计、工艺相联系，面 向制造，同时与生产管理系统密切联系。 把产品零件设计和排样联系起来： 板类零件分为两类：二维平面零件和具有立体形状的零件。立体板类零件一 般通过平面展开，然后成形。因此在设计时就应该把零件的立体信息和后续加工 信息存入特定的数据库供零件排样时使用，提高零件的生产效率和质量。 多边形零件排样技术研究及软件开发 6 图 1. 2 topdesk 开发独立的排样系统 pymng 把排样和具体的制造工艺联系起来： 要考虑不同的工艺制造问题， 如对于火焰切割问题， 需要考虑切割变形问题、 切割路径优化问题； 对于需焊接的零件， 要考虑零件坡口的形状； 对于冲压问题， 需要考虑压力中心平衡、桥宽问题。因此在排样时需要完成相关工艺咨询，进行 多工艺方案的经济性分析。综合考虑设备情况、加工成本和交货期等因素，以期 达到整体上的最优。 从系统的观点， 将排样优化系统作为整个企业信息化系统的一个有机组成部 分，排样系统不单纯提供排样功能，而且对生产、管理提供决策支持信息，实现 整体上的最优。 1.3 本文选题背景及研究内容 复合材料（composite material）是以一种材料为基体，另一种材料为增强体 组合而成的材料。各种材料在性能上互相取长补短，产生协同效应，使复合材料 的综合性能优于原组成材料而满足各种不同的要求。由于复合材料热稳定性好， 比强度、比刚度高，可用于制造飞机机翼和前机身、卫星天线及其支撑结构、太 阳能电池翼和外壳、大型运载火箭的壳体、发动机壳体、航天飞机结构件等。所 南京航空航天大学硕士学位论文 7 以，复合材料在航空航天领域得到了广泛的应用。frost float y; 多边形的表示，以动态数组的形式记录顶点数据来表示多边形信息： carray m_theselectedpolygon; 对于矩形， 定义了一个类， 用来记录其左下角顶点信息， 以及长和宽的信息： class rect float x,y; /左下角顶点坐标 float l,w; /矩形长和宽 二、多边形顶点排序的方向性判断 保存的多边形顶点，有些是按顺时针顺序排序，有些是按逆时针顺序排序。 为了便于程序上对数据点进行处理，我们需要对其排序顺序做个统一。首先必须 判断多边形数据点的排序顺序。 实际上多边形顶点的方向是与凸顶点及其相邻的 两个顶点组成的三个顶点的方向是一致的， 所以我们只需判断这三个顶点的方向 即可。一般情况下，多边形的最上点，最下点，最左点和最右点必定是凸顶点， 因此只要当多边形顶点中的 x 或 y 值有一个值是所有同类中的极值， 就能确定该 顶点是凸顶点。 顺序三个顶点的方向性判断还可以通过这三个顶点连线所得到的三角形s 的面积s来判断，s的面积s可以表示为： 南京航空航天大学硕士学位论文 11 11 11 1 1 1 2 1 ii ii ii xy sxy xy + = （2-1） 当0s时，为逆时针排序；当0s ，则 i 点为凸顶点；如果0s ）发生碰撞的必要条件为： 1） 12a yyy； 2） 12 max( ,) a xx x+ ； 即： 2211baba+ 所以碰撞点的确定可以通过以下的方式获得： 做过多边形顶点的水平线，与该顶点对面的线段相交，求取顶点与交点的距 离。重复上面的操作，求出所有顶点到对边的距离。其中距离最大的顶点即为碰 撞顶点。 南京航空航天大学硕士学位论文 25 结论：碰撞顶点到对边的距离即为多边形需要水平向右移动的步距。 图 3. 6 多边形水平移动距离 3.4.2 多边形的二维移动 在二维坐标系中， 任意点( , )px y=通过将平移距离tx，ty加到p的坐标上而 平移到( ,)px y=： xxtx=+，yyty=+ 用矩阵的方式表示： 10 01 10011 xtxx ytyy = 即： pt p= 根据点的二维平移公式我们可以很容易的推导出多边形的二维平移公式： 1212 1212 10 01 1110011 11 nn nn xxxtxx xx yyytyy yy = ll ll ll 3.4.3 普通单排的具体实现 设 定 在 宽 度 为w， 长 度 无 限 的 板 料 上 对 某 一 单 一 零 件 1122 ( ,),(,),(,) nn px yxyxy=l排样，零件个数为n。首先需要先确定几个参数的 计算方法： 多边形零件排样技术研究及软件开发 26 1）计算零件的高度h，和宽度w： 1212 max(,)min(,) nn hy yyy yy=ll； 1212 max( ,)min( ,) nn wx xxx xx=ll； 2）计算零件水平方向和竖直方向移动的步距dx，dy。采用本文3.4.1的方 法即可求得。 3）计算m个零件排成一行的宽度width： (1)widthwmdx=+ 4）计算零件排了k行后总体高度height： (1)heighthkdy=+ 普通单排的流程如图3.7所示。 开始开始 计算零件的高度计算零件的高度h，宽度，宽度w，移动的步距，移动的步距dx，dy; 令令width=0；height=0；零件个数；零件个数i=0 零件宽度小于板料宽度：零件宽度小于板料宽度：w m_polygon; /记录多边形顶点的动态数组 南京航空航天大学硕士学位论文 31 float m_distance; /碰撞距离 碰撞边界的顶点在每次碰撞后都需要插入和删减部分顶点， 从而形成新的碰 撞边。 这些特性， 采用链表的方式存储顶点数据来表示碰撞边， 便于程序的实现。 class cmylink cmypoint m_point; cmylink *prev; cmylink *next; 3.5.4.2 排样具体流程 n个多边形零件在一块宽为w，长为无限长的板材上进行排样，可以按照如 下的流程实现： 第一步：进行初始化，把所有多边形数据导入系统。所有多边形的顶点数据 按照逆时针顺序，且从最下最左的顶点开始保存的方式保存到数组中。 第二步，把所有多边形移动到板料靠最左，且足够高处，设高度为h。取板 材边界的四个顶点： 0 (0,) h ph， 00(0,0) p， 0( ,0) w pw，(,) wh pw h。把这四个顶 点保存到boundlist，这就是最原始的碰撞边界。 第三步：开始排放第(1,2, )inl个多边形 i m_polygon，以dx（/dxwk=，k 是一个正整数，代表步长精度，k越大，步距越小，排样的精度越高，材料利用 率越高，但计算量也随之提高，所以k需要取一个合适的值，在满足精度要求的 情况下，越小越好）为步距，把多边形向右移动，形成k个多边形： i,j polyon (0,1,1)jk=l。 第 四 步 ： 求 出 多 边 形 i,j polyon与 碰 撞 边 界boundlist的 碰 撞 距 离 j distance (0,1,1)jk=l。 第五步：在 j distance (0,1,1)jk=l找出最大值，如果有多个最大值，取j 最小的。此时j=m(m0,k-1). 第六步：将多边形 i m_polygon向右移动mdx，向下移动 m distance。即将 i m_polygon所有顶点的x坐标加上mdx，所有y坐标减去 m distance。得到排放 位置处的多边形 i m_polygon 第七步：多边形 i m_polygon 与boundlist碰撞，求出碰撞顶点，把 i m_polygon 中是碰撞点的顶点中的flag赋值为true 第八步：把所有碰撞顶点插入boundlist，插入规则如下： 多边形零件排样技术研究及软件开发 32 从boundlist第一个顶点开始循环，判断碰撞点p是否在相邻两个顶点所表 示的线段上。当查找到符合条件的两个相邻顶点，把碰撞点p插入到链表 boundlist这两个相邻顶点的中间位置。并且如果这两个顶点中有任一个顶点与 碰撞点等值（即重合） ，删除该顶点。 按同样的方法继续插入下一个碰撞点，直至全部插入为止。 点是否在线段上的判断，只要满足下面的公式就可。 设点为( , ) x y ，线段的两个端点为 11 ( ,)x y ， 22 (,)xy 212212 12 12 ()()()() ()()0 ()()0 yyxxxxyy xxxx yyyy = 第九步：建立新的碰撞边界链表newboundlist，把boundlist保存的顶点数 据从第一个开始依次插入newboundlist，直到碰到第一个碰撞点（flag=1）e1 时，在 i m_polygon 中查找与e1相同的顶点，从所查到的顶点之后，把遇到的顶 点依次插入newboundlist，直到遇到又一个碰撞点e2，再在boundlist中查找 与e2相同的顶点，把该顶点及该顶点之后所有的顶点插入到newboundlist。将 两个碰撞顶点的flag重新赋值为flase。 第十步：清空boundlist，把newboundlist的值拷贝到boundlist中，再清 空newboundlist。 第十一步：查看是否还有待排零件，如果有，则从第二步重新开始；如果没 有，则结束排样，输出排样结果。 具体流程如图3.11所示。 南京航空航天大学硕士学位论文 33 图 3. 11 基于碰撞的多边形排样流程 按照上述方法，本文实现了基于碰撞法的多边形排样，并给出了算例，从图 3.12可以看出，零件的排放后，相互贴合，该方法的排样效果明显优于基于矩形 开始：导入数据到系统开始：导入数据到系统 初始化多边形数据； 设置高度： 初始化多边形数据； 设置高度： h；水平平移精度；水平平移精度k; 把所有多边形全部移动到最左最上位置； 初始化碰撞边界： 把所有多边形全部移动到最左最上位置； 初始化碰撞边界：boundlist ； i=0 第第i个多边形：个多边形：m_polygon_i 以以dx为步距，向右移动，共移动为步距，向右移动，共移动k次次 m_polygon_i_0m_polygon_i_1m_polygon_i_k-1 h_0h_1h_k-1 找出最大值找出最大值 h_m，如果有多个相等的最大值，取，如果有多个相等的最大值，取m值最小的 值最小的 m_polygon_i 先右移先右移 m*dx; 再向下移动再向下移动h_m 求出所有碰撞点，把碰撞点的求出所有碰撞点，把碰撞点的flag赋值为赋值为true 更新碰撞边界更新碰撞边界boundlist i=i+1 it 进行分段，图4.17（c）中 bd4 出现 3 次， 将 st 分为 s 2 a, 2 a- 4 a和 4 a-t 三段。 步骤4：对每一段，从 b出发，先向前移动到该段与 bl 的最远交点，再折回 到该段与 br 的最远交点，最后再折回到 b点，按以下方法记录当中遇到的点： a）对当中出现 i a形式的全部记录 b）向 i b（ i b为 bl 或 br 所对应的边）移动时， i b需要记录。 j b，ji则全 多边形零件排样技术研究及软件开发 50 部忽略。 c）记录的边点的符号确定：向前移动（不一定是逆时针方向）为正，向后 为负。 4.7.3实例及说明 给定两个凹多边形a和b，如图4.18（a） （b） ，计算它们的临界多边形。先 计算出 ()aconvb nfp 的边序列为a6,b3,a0,a1,b0,a2,v0,a3,a4,-v0,a5,v0,只需替换掉 其中出现的v0和-v0即可得到 ab nfp。由图4.18（c）可得：第一个v0应替换为 b1,b2;接着出现的-v0替换为-b2,-a4,-b1,a4;最后的v0替换为b1,b2。 说明：替换时有可能虚边超出了该分段的范围，例如图4.18中，改变多边 形-b，就有可能使得-b2超出a3-a5段，而同时b2也就超出了a5-b1(即t点) 段；此时就需要将分段加以扩充，以将超出的虚边包含进去，如a3-a5段就可 变为a3-b2段；然后对每段按规则替换即可。 图 4. 18 两个凹多边行的临界界多边形求解实例 4.8 复杂多边形优化（求外边界） 4.8.1 背景 在计算临界多边形的过程中，上文图4.18（c）中的替换方法，可以得到两 个凹多边形的临界多边形的雏形，例如，对于上文中的图4.18（a） （b）所示的 多 边 形 ， 通 过 图4.18（c） 的 方 法 得 到 临 界 多 边 形 的 边 的 序 列 为 ： a6,b3,a0,a1,b0,a2,b1,b2,a3,a4,-b2,-a4,-b1,a4,a5,b1,b2.结果如图4.19（a）所示。对于 那两个凹多边形来说，此时得到的还不是真正的临界多边形，只需将此多边形优 化，求得其外边界，则此边界就是需要的临界多边形，如图4.19（b）所示。图 4.19（b）中，红线为图4.19（a）中的复杂多边形的外边界，也是所要求的临界 南京航空航天大学硕士学位论文 51 多边形；蓝线部分为静止多边形a，其中有两条边因与红线重合未能显示出来； 黑线部分为移动多边形b，图中给出了其在移动中一些特殊位置。 b3 a3 b2b1 a2 b0 a1 a0 a6 a5 a4 -b1 -a4 -b2 a4 b2 b1 (a) 复杂多边形 (b) 多边形优化结果与临界多边形图示 图 4. 19 复杂多边形的优化在临界多边形求解中的应用 4.8.2 基本思路 本算法最基本的思想就是对复杂多边形计算出多边形的边相交所形成的交 点，记录交点的导入和导出边，假如已知了某个导入边符合条件(即它在最终所 要求的临界多边形上)，我们就可利用一定的方法来得到符合条件的导出边，故 只要找到满足条件的导入边即可。而要找到满足条件的导入边，也只需要找到第 一个满足条件的导入边即可。 下面通过图4.19（a）的多边形来讲解该算法的基本思路： 假设多边形用边的序列a6,b3,a0,a1,b0,a2,b1,b2,a3,a4,-b2,-a4,-b1,a4,a5,b1,b2 进行表示，首先从第一条边a6开始遍历，找到第一个通过交点的边b1；b1即为 第一个符合条件的导入边，可由此依据某种方法求得满足条件的导出边，在图中 即为b2；继续遍历可发现b2也为通过交点的边，此时b2边也就是满足条件的 第二条导出边；由此可得到第二条满足条件的导出边b1，由此得到第三条导入 边b1，再得到第三条导出边b2，此时的边b2也就是多边形的边序列中的最后的 一条边，遍历完毕。由此可以得到两凹多边形a和b的临界多边形的最终的边 序列为：a6,b3,a0,a1,b0,a2,b1,b2,b1,b2。即为图4.19（b）中的红线部分，图4.19 （b）中未标出多边形a，b和nfp(即临界多边形)的边的编号，它可通过图4.19 （a）对比得到，在此略过。 多边形零件排样技术研究及软件开发 52 4.8.3 实现过程 上面介绍了该算法的基本思路，下面给出基本步骤： 1）求出交点 求出复杂多边形的边相交所形成的交点。对多边形的第i条边，计算它与第 0，1，i-2条边的交点，即为要求的点。当然，最后一条边即第n条边，只 要计算出它与第1，2，n-2条边交点即可。 为了减少运算量，只需从第一个转折边 （图4.19中为a2后面的边b1） 开 始即可。在此过程中还进行了两个工作：第一就是当遇到相邻的两条边p和pr 的边矢量方向相反时，对它进行了处理；而第二就是对循环可能出现边退化为点 的情况进行处理。至于工作一，消除两边，形成新边即可；工作二更简单，直接 删除该边即可。 此时得到的交点可能有重复，如a4与b2的交点就与a4与b1的交点相同， 此时只要删除相同的交点即可。 2）重新生成原来的复杂多边形的边，使得所有交点都只能在边的端点上， 此步骤是为第3步分段做准备。 图4.19（a）中多边形的两条a4均被分成了两条边a4_1和a4_2。 3）分段，并登记交点的出入边。 复杂多边形按照交点进行分段，图4.19（a）中的多边形被分成7段，分别 为：a6,b3,a0,a1,b0,a2,b1；b2；a3,a4_1；a4_2,-b2,-a4,-b1,a4_1；a4_2,a5； b1；b2。 按从做到右数，可得到三个交点的出入边：第一个交点的导入边为b1,a4_1, 导出边为b2,a4_2；第二个交点的导入边为b2,a5，导出边为a3,b1；第三个交点 的导入边为b1,a4_1，导出边为a4_2,b2。 4）给交点的出入边标记所在的段号 通过对分段序列和交点序列进行遍历即可。 5）形成外边界 从第一段a6,b3,a0,a1,b0,a2,b1开始，先得到第一个导入边，由此得到相应 交点的导出边，跳转到导出边所在的段，再得到导入边，再得导出边，依次跳转 直至跳转到最后一段b2，并记录该段即可结束。由导入边得到导出边的思路如 图4.20所示。图4.20是针对图4.19中第二个交点进行考虑，满足条件的导入边 为b2，要得到符合条件的导出边，只要计算导入边到导出边的逆时针夹角，取 夹角最小的导出边即可，图4.20中即为b1。 南京航空航天大学硕士学位论文 53 a3 b2 a5 b1 图 4. 20 由导入边得到导出边的思路 对于类似于图4.21所示情况，上述方法要进行改进。原复杂多边形的边根 据交点重新生成得到的新的边序列为b0,b1,b2_1,b2_2,b3,b4,b5,b6_1,b6_2,b7。用 上面的方法，b2_1导入边可得到b2_2导出边，由此得到b6导入边，但若对b6 导入边计算导出边时仍按上述方法进行处理，则又会得到b2_2边，如此便会进 入死循环。解决方法就是取导出边时要取夹角最小且未被取过的导出边即可。 图4.21中导入边为b6_1时，b2_2虽然夹角最小，但已被取过，舍去，故取 b6_2边。所以最终结果为b0,b1,b2_1,b2_2,b3,b4,b5,b6_1,b6_2,b7。 b0 b6 b5 b4 b3 b2 b1b7 b2_1 b2_2 b6_1 b6_2 图 4. 21 由导入边得到导出边的特殊情况处理 4.9 基于nfp的多边形排放策略 4.9.1 多边形的定位约束条件 1）待排零件与已排零件不可重叠，即满足条件：求出待排零件与已排零件 的nfp，保证待排零件的参考点不在nfp内部即可。 2）待排零件的位置不能超出板料边界，即定位后的待排零件顶点坐标满足 多边形零件排样技术研究及软件开发 54 条件：所有x坐标大于等于左边界x坐标；所有x坐标小于等于右边界x坐标； 所有y坐