多边形零件排样技术研究及软件开发

论文摘要

排样在汽车、机械、服装及皮革等领域有着广泛的应用。传统的排样方法和结果主要依赖于操作人员的经验与熟练程度。随着计算机技术的发展,计算机自动排样系统在各个领域得到应用,大大减轻了脑力和体力劳动强度,缩短了排样时间,材料利用率也大为提高。多边形零件的排样是排样问题中的一个难点,本文对多边形零件排样问题进行了深入研究,所做工作总结如下:通过求取最小包络矩形的方式,将多边形排样问题转化为已有成熟解决方案的矩形件排样问题。经过对多种矩形件排样算法的对比,研究实现了最低轮廓线最佳匹配算法。用该方法对多边形零件进行排样,计算复杂度低,运算速度较快,适用于与矩形件形状接近的多边形零件。研究了基于碰撞算法的多边形排样方法。通过对零件碰撞距离、边界合成等研究,将碰撞算法有效运用于多边形排样和单一零件排样中,能够得到排放紧凑的排样结果。研究了基于临界多边形法的排样问题。在前人研究的基础上,采用倾斜图法获取两个多边形的NFP（No-Fit-Polygon,临界多边形）。该算法可以有效利用零件与零件之间的排样间隙,从而提高排样的材料利用率。研究了蚁群算法,将蚁群算法引入排样算法中,以矩形件排样算法为例,给出蚁群算法的实现方法和步骤。通过大量的实验,进行比较。结果表明,蚁群算法是解决矩形件排样问题的有效方法,相同条件下效率优于模拟退火算法,排放效果好于遗传算法。在上述研究成果的基础上,开发了排样软件。该软件主要有图形输入、图形组合、优化排样、图形输出、人机交互处理等模块。软件提供单一零件排样,矩形件排样,多边形排样等不同排样方式的选择,以满足实际应用中的不同需求。数据读取与保存采用DXF格式,使得本软件能够与其他CAD软件进行数据交换。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 排样概述
• 1.2 二维零件排样的研究现状
• 1.2.1 国外研究现状
• 1.2.2 国内研究现状
• 1.2.3 排样软件概述
• 1.2.4 排样系统的研究趋势
• 1.3 本文选题背景及研究内容
• 第二章 基于矩形的多边形零件排样
• 2.1 引言
• 2.2 最小包络矩形的求取
• 2.3 矩形件排样
• 2.3.1 定序矩形件排放策略
• 2.3.2 最低轮廓线最佳匹配排样算法
• 2.4 基于矩形的多边形排样
• 2.5 本章小结
• 第三章 基于碰撞法的多边形求解算法
• 3.1 碰撞法概述
• 3.2 一般多边形的平移碰撞算法
• 3.3 碰撞距离的求解
• 3.4 碰撞算法在单一零件排样中的应用
• 3.4.1 多边形的水平移动距离的计算
• 3.4.2 多边形的二维移动
• 3.4.3 普通单排的具体实现
• 3.4.4 材料利用率的计算
• 3.5 基于碰撞算法的多边形排样
• 3.5.1 基于碰撞算法的多边形排样基本流程
• 3.5.2 碰撞边的合成
• 3.5.3 零件向下移动与碰撞边碰撞的移动距离
• 3.5.4 基于碰撞的多边形排样实现流程
• 3.6 本章小结
• 第四章 基于临界多边形的多边形排样
• AB 的概念'>4.1 临界多边形NFP_AB的概念
• 4.2 临界多边形的几何意义
• 4.3 临界多边形NFP 的求解概述
• 4.4 利用MINKOWSKI SUM 和斜率图来求NFP
• 4.4.1 用Minkowski Sum 求解NFP 的思路
• 4.4.2 用斜率图（slope diagrams）确定NFP 边的连接顺序
• 4.5 多边形NFP 生成算法及实现
• 4.5.1 基本定义
• 4.5.2 NFP 基本生成算法
• 4.6 NFP 生成优化算法
• 4.7 两个凹多边形的临界多边形（NFP）的求法
• 4.7.1 思路
• 4.7.2 算法
• 4.7.3 实例及说明
• 4.8 复杂多边形优化（求外边界）
• 4.8.1 背景
• 4.8.2 基本思路
• 4.8.3 实现过程
• 4.9 基于NFP 的多边形排放策略
• 4.9.1 多边形的定位约束条件
• 4.9.2 点与多边形位置的判断
• 4.9.3 两个多边形的位置判断
• 4.9.4 基于合成多边形的NFP 排样策略
• 4.9.5 基于完全NFP 排样策略
• 4.10 本章小结
• 第五章 多边形排样优化
• 5.1 几种优化算法的概述
• 5.2 蚁群算法
• 5.3 基于蚁群算法求解矩形件排样
• 5.4 排样算例
• 5.5 几种优化算法比较
• 5.5.1 启发式算法性能的评价方法
• 5.5.2 几种启发式算法的性能比较
• 5.6 本章小结
• 第六章 多边形排样系统设计
• 6.1 系统功能概述
• 6.2 主要功能模块具体介绍
• 6.2.1 数据处理
• 6.2.2 图形显示
• 6.2.3 零件预处理模块
• 6.2.4 单一零件排样模块
• 6.2.5 矩形件排样模块
• 6.2.6 多边形样件的排样模块
• 6.2.7 排样向导模块
• 6.2.8 交互模块
• 6.3 系统使用说明及实例
• 6.3.1 单一零件的排样模块的使用
• 6.3.2 矩形件排样模块的使用
• 6.3.3 多边形排样模块的使用
• 6.4 本章小结
• 第七章 总结与展望
• 7.1 全文工作总结
• 7.2 今后工作展望
• 参考文献
• 致谢
• 攻读硕士学位期间论文发表情况