论文部分内容阅读
二维零件的优化排样技术广泛的应用于制造工业、服装、皮革以及建筑行业中，同时也是一个具有最高计算复杂度的NP完全问题。长期以来，一直是自动化领域的研究热点之一。 任意形状优化排样问题集中体现了两个关键性问题：①．确定参与排样零件之间的位置关系以及最优排放位置。②．确定一个优化的排样序列。本文结合国内外的研究现状和排样问题的自身特点，针对任意形状的二维不规则零件排样问题的关键算法进行了深入的研究，提出了一系列解决优化排样问题的算法。本文的主要研究包括以下内容： 临界多边形是判别两个多边形相互关系的一个非常有效的方法。但是由于直接求解两个凹多边形的临界多边形比较困难，长期以来限制了它的应用。本文提出了多边形凸化分割的方法，将求解两个凹多边形的NFP问题转化为求解两个凸多边形的NFP问题，并加以理论证明，成功地解决了这一问题。 研究了多边形的各种分割方法：三角形化、无Steiner点分割、有Steiner点分割。并且在角平分线分割法的基础上，提出了延长线分割法。 基于CGAL的平面图，讨论了多边形合并算法：排列合并算法、增量合并算法以及divide与conquer算法。 讨论了排样过程中的其它关键性算法，包括曲线的离散化算法、多边形的合成算法、以及多边形的面积算法。 采用遗传算法来优化排样过程的零件调度问题，以材料的利用率为目标函数，产生一个优化的零件排样序列。 论文的算法基于计算几何算法库CGAL(Computational Geometry Algorithms Library)，在Visual C++平台上开发完成。本论文中使用的临界多边形算法不但为排样系统的进一步研究提供了很好的工具，同时对计算机辅助装配、机器人路径规划等研究都有很好的参考价值。