临界多边形法在二维不规则零件排样中的研究与实现

【作者】 白瑞斌；

【导师】 魏生民；

【作者基本信息】 西北工业大学 ， 航空宇航制造工程， 2002， 硕士

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

【Abstract】 Two-dimensional irregular shape nesting system is widely used in manufacturing industry, garment, leather and architecture industry. It is a one of the NP-complete problem and has been a hot research area for a long time.Irregular shape nesting problem concerns two key problems: (1). Deciding the relative position of two polygons and calculating the optimal position to place the part. (2). Calculating the optimal nesting sequence. This article, based on the current research status and characteristic of nesting problem, made a profound research in the nesting algorithms and brought out a set of algorithms to solve nesting problem. Specifically, the research contained: No-Fit Polygon is an effective method to judge the relative position of two polygons. However, the difficulty to derive the No-Fit Polygon of two non-convex polygons limited its application. In this thesis, I simplified this problem into the problem to calculate the NFP of two convex polygons by decomposing the non-convex polygon into convex polygon. Many polygon decomposition methods are discussed in this thesis: triangulation, decomposition without Steiner point, decomposition with Steiner point. The thesis also brought forward a new method, "edge extending decomposition". Discussing the polygon union algorithms on the CGAL and Planar Map platform. They are Arrangement Algorithm, Incremental Union Algorithm and Divide and Conquer Algorithm. Discussing other key algorithms which are used in the nesting process, such as curve digitization algorithm, polygon joining algorithm and polygon area algorithm. The article employed genetic algorithm to optimize nesting sequence so as to maximize the stock usage efficiency.Algorithms in this thesis, based on CGAL(Computational Geometry Algorithms Library), are realized on the Visual C++ platform. The method to construct No-Fit Polygon in this thesis is not only a very good tool to make further research in the nesting problem but also a valuable addition to the researches of Computer Aided Assembly, robot path planning, etc.更多还原