Critical Polygon Method In Two-dimensional Irregular Parts Nesting And Implementation

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.